Evolutionary Tree Weight

In evolutionary biology, a tree (often called an evolutionary tree) is used to represent the relationships between species. In this problem, you are given an n×n matrix M which represents the pairwise distances between species (the leaves of the tree). The distance between any two leaves i and j in the tree is exactly M[i,j]. The tree has the following properties:

• The leaf nodes are exactly the set N = {1, 2, ..., n}.
• All edge weights are non-negative integers.
• If d_T(i,j) denotes the shortest distance on the tree between leaves i and j, then d_T(i,j) = M[i,j] for all i and j.

Furthermore, the matrix M is guaranteed to satisfy the triangle inequality in the form $$M[i,j] + M[j,k] \ge M[i,k]$$ for all indices i, j, k. It turns out that for any matrix M that represents a tree metric, the total weight of the corresponding tree (i.e. the sum of all edge weights) is uniquely determined. Your task is to compute this total weight.

For example, consider the following matrix:

$$ 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} $$

This matrix represents a tree whose total weight is 15.

inputFormat

The first line contains a single integer n (2 ≤ n ≤ 200), representing the number of species (leaf nodes). The next n lines each contain n space-separated integers. The j-th integer in the i-th line is M[i,j], representing the distance between species i and j. It is guaranteed that M[i,i] = 0 for all i and that M is a valid tree metric.

outputFormat

Output a single integer, the total weight of the tree represented by the matrix M.

sample

5
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

15