Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của hình vuông là đường thẳng nối hai ô (1,1) và(n,n). Các ô nằm phía trên đường chéo chính (bao gồm cả các ô thuộc đường chéo chính) được gọi là tam giác trên của hình vuông.

Yêu cầu: Tính tổng các ô thuộc tam giác trên của hình vuông.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Kết quả:

• Ghi một số nguyên duy nhất là tổng các phần tử thuộc tam giác trên của hình vuông.

Tam giác trên màu vàng

Ví dụ:

Input

4
1 2 3 4
4 3 2 0
0 2 3 4
1 4 5 6

Output

28