beecrowd | 2785


By OBI BR Brasil

Timelimit: 1

In the deposit of the factory, leaning against a wall, there is a matrix of N lines by N columns of stacked boxes. Each box has an associated positive integer weight. The factory inspector needs to remove some boxes from the matrix so as to leave a kind of box pyramid satisfying the following restrictions:

Given the weights of all boxes in the matrix, your program must calculate the minimum total weight a pyramid might have if the inspector pulls out some boxes according to the above restrictions.


The first line of the input contains an integer N (1 ≤ N ≤ 100), indicating the dimension of the matrix. The next N lines each contain N integers representing the weights of the boxes in each row of the array of boxes.

The values ​​of the array elements are between 1 and 100, inclusive.


Your program must to produce an unique line, containing an integer, indicating the total weight that the pyramid might have.

Input Samples Output Samples


5 2 4

3 6 7

10 5 10



45 8 3 1

1 10 5 67

4 4 3 18

10 4 7 12