bee 2785 - Pyramid

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:

If a box is in the pyramid, the box just below it should also be in the pyramid;
In the i-th line of boxes (line 1 is that of the top of the matrix), the pyramid must have exactly i consecutive boxes.

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.

Input

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.

Output

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

Input Samples	Output Samples
3 5 2 4 3 6 7 10 5 10	36

Input Samples

Output Samples

5 2 4

3 6 7

10 5 10

4 45 8 3 1 1 10 5 67 4 4 3 18 10 4 7 12	62

45 8 3 1

1 10 5 67

4 4 3 18

10 4 7 12