Problem Description

Trees can be used to represent the evolutionary relationships between species. An "evolutionary tree" is a tree with weighted edges, where the leaf nodes represent species, and the distance between two leaf nodes represents the difference between the two species. Now, an important question is to reconstruct the corresponding "evolutionary tree" based on the distances between species.

Let $N=\{1,2,3,\cdots ,n\}$, and use a matrix $M$ on $N$ to define tree $T$. The matrix $M$ satisfies: for any $i$, $j$, $k$, $M[i,j] + M[j,k] \ge M[i,k]$. The tree $T$ satisfies:

1. The leaf nodes belong to the set $N$;
2. The edge weights are non-negative integers;
3. $d_T(i,j) = M[i,j]$, where $d_T(i,j)$ represents the shortest path length from node $i$ to node $j$ on the tree.

As shown in the figure below, matrix $M$ describes a tree.

$$M=\begin{bmatrix} 0 & 5 & 9 & 12 & 8 \\ 5 & 0 & 8 & 11 & 7 \\ 9 & 8 & 0 & 5 & 1 \\ 12 & 11 & 5 & 0 & 4 \\ 8 & 7 & 1 & 4 & 0 \\ \end{bmatrix}$$

The weight of the tree is the sum of all edge weights on the tree. For any given valid matrix $M$, the weight of the tree it represents is uniquely determined; it is impossible to find two trees with different weights that both match matrix $M$. Your task is to calculate the weight of the tree represented by the given matrix $M$. The figure below shows a tree that can be represented by the given matrix $M$, and the total weight of this tree is $15$.

Input Format

The first line is an integer $n\ (2 < n < 30)$.

The next $n-1$ lines provide the upper triangular part (excluding the diagonal) of matrix $M$, where all elements are non-negative integers not exceeding $100$. The input data guarantees the validity of the matrix.

Output Format

For each input, output a single line containing an integer, which is the weight of the tree.

Sample Input and Output

Input Sample #1

5
5 9 12 8
8 11 7
5 1
4

Output Sample #1

15

Input Sample #2

4
15 36 60
31 55
36

Output Sample #2

71

见题面 Input 部分

见题面 Output 部分