beecrowd | 2785
# Pyramid

**Timelimit: 1**

By OBI Brasil

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.

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 |

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 |