Archivist

Тавсифи масъала

On an Archive Server in Earth's orbit, there are $N$ modules placed in a row. Each module contains an unknown integer value: $p_1, p_2, \ldots, p_N$.

Husanboy wants to learn all these values, but due to the security system, he cannot read the module contents directly. The server only provides the following paid service:

If Husanboy chooses $i$ and $j$ ($1 \le i \le j \le N$), the server tells him the sum of the values in the interval $[i, j]$: $p_i$. In return, Husanboy pays "credits".

Husanboy may make as many queries as he wants. His goal is to reconstruct all values $p_1, p_2, \ldots, p_N$ exactly, while minimizing the total cost.

Input Format

The first line contains one positive integer $N$.

The next $N$ lines describe the query costs. On line $i+1$ there are $N-i+1$ non-negative integers, in the following order: $C(i,i),\ C(i,i+1),\ \ldots,\ C(i,N)$

Constraints

$1 \le N \le 1000$

$0 \le C(i,j) \le 10^6$ for all $1 \le i \le j \le N$

Output Format

Print one integer --- the minimum total cost Husanboy must pay to determine all elements of array $p$.

Scoring

3
5 5 1
5 2
5

8