Hey, folks! Wonders in this booth! I think I've gone crazy, I'm giving away money! — Bitocy makes a living as a juggler at the fair in Bajtowa.

He invites passersby to a specific game. On a table, there are $n$ cups in a row numbered $1, 2, \dots, n$, with rubber balls hidden under some of them. If a player guesses exactly which cups have balls, they get a large teddy bear. Bitocy provides hints to the player for a fee. For $c_{ij}$ bajtogroszy, Bitocy is willing to reveal the parity of the number of balls hidden under the cups numbered $i, i+1, \dots, j$.

Bajtazar came to the fair with Bajtyna — the prettiest girl in all of Bajtowa. He would very much like to win a teddy bear for her. He does not intend to risk embarrassment by guessing without being sure of the answer. He will pay for hints until the gathered information allows him to determine with absolute certainty which cups have balls under them.

Knowing the prices of all possible hints, he is now wondering what the maximum cost will be. More precisely, he would like to know the smallest number $k$ such that there exists a strategy for asking questions that, regardless of Bitocy's answers, allows for the localization of the balls for at most $k$ bajtogroszy.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 2000$), representing the number of cups. This is followed by a description of the costs of queries for individual intervals. The $(i+1)$-th line of input (for $1 \le i \le n$) contains $n+1-i$ integers, representing the costs of individual hints.

The cost $c_{ij}$ ($1 \le i \le j \le n$, $1 \le c_{ij} \le 10^9$) of querying the interval from the $i$-th to the $j$-th cup inclusive appears in the input as the $(j+1-i)$-th number in the $(i+1)$-th line.

Output

Your program should output a single integer representing the maximum cost of determining the location of the balls for an optimal strategy of asking questions.

Examples

Input 1

5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5

Output 1

7