beecrowd | 2785

# Pyramid

By OBI 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:

• 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
 4 45 8 3 1 1 10 5 67 4 4 3 18 10 4 7 12 62