The Shell Game

Time limit1sMemory limit256 MB

Summary

Buy interval parity hints to fix every ball position while minimizing the worst-case total price.

Level: Medium6 of 10
Topics: Minimum spanning tree, Graph
Solved: No attempts yet

Problem

Bitocy makes a living running a shell game at the fair. On a table stand $n$ cups in a row, numbered $1$ to $n$ , and a rubber ball is hidden under some of them. A customer who names exactly the cups that hide a ball wins a large teddy bear.

Bitocy sells hints. For $c_{ij}$ coins he tells you whether the number of balls hidden under cups $i$ through $j$ is even or odd.

Bajtazar came to the fair with Bajtyna and wants to win the bear for her. He will not guess while he is unsure, so he keeps buying hints until the answers he has bought fix the position of every ball.

He knows the price of every hint and wants the worst case. Find the smallest $k$ such that some strategy of asking questions locates all the balls for at most $k$ coins, whatever Bitocy answers.

Input

The first line contains the number of cups $n$ ( $1 \le n \le 2000$ ).

The next $n$ lines give the hint prices. Line $i$ of those contains $n+1-i$ integers, and the $j+1-i$ -th of them is the price $c_{ij}$ of the question about cups $i$ through $j$ ( $1 \le i \le j \le n$ , $1 \le c_{ij} \le 10^9$ ).

Output

Print one integer, the largest amount that locating all the balls costs under the optimal strategy.

Examples3

Example 1
Input
```
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
```
Expected output
```
7
```
Example 2
Input
```
1
5
```
Expected output
```
5
```
Example 3
Input
```
2
3 1
4
```
Expected output
```
4
```