Flipping Colors

You are given an undirected complete graph. Every pair of the nodes in the graph is connected by an edge, colored either red or black. Each edge is associated with an integer value called penalty.

By repeating certain operations on the given graph, a “spanning tree” should be formed with only the red edges. That is, the number of red edges should be made exactly one less than the number of nodes, and all the nodes should be made connected only via red edges, directly or indirectly. If two or more such trees can be formed, one with the least sum of penalties of red edges should be chosen.

In a single operation step, you choose one of the nodes and flip the colors of all the edges connected to it: Red ones will turn to black, and black ones to red.

For example, the leftmost graph of Fig. F-1 illustrates the first dataset of Sample Input. By flipping the colors of all the edges connected to the node 3, and then flipping all the edges connected to the node 2, you can form a spanning tree made of red edges as shown in the rightmost graph of the figure.

Input

The input consists of multiple datasets, each in the following format.

n
e_1,2 e_1,3 ... e_1,n-1 e_1,n
e_2,3 e_2,4 ... e_2,n
...
e_n-1,n

The integer n (2 ≤ n ≤ 300) is the number of nodes. The nodes are numbered from 1 to n. The integer e_i,k (1 ≤ |e_i,k| ≤ 10⁵) denotes the penalty and the initial color of the edge between the node i and the node k. Its absolute value |e_i,k| represents the penalty of the edge. e_i,k > 0 means that the edge is initially red, and e_i,k < 0 means it is black.

The end of the input is indicated by a line containing a zero. The number of datasets does not exceed 50.

Output

For each dataset, print the sum of edge penalties of the red spanning tree with the least sum of edge penalties obtained by the above-described operations. If a red spanning tree can never be made by such operations, print -1.

Sample Input

4
3 3 1
2 6
-4
3
1 -10
100
5
-2 -2 -2 -2
-1 -1 -1
-1 -1
1
4
-4 7 6
2 3
-1
0

Output for the Sample Input

7
11
-1
9

---