Description:
Given a n*n matrix C
ij (1<=i,j<=n),We want to find a n*n matrix X
ij (1<=i,j<=n),which is 0 or 1.
Besides,X
ij meets the following conditions:
1.X
12+X
13+...X
1n=1
2.X
1n+X
2n+...X
n-1n=1
3.for each i (1<i<n), satisfies ∑X
ki (1<=k<=n)=∑X
ij (1<=j<=n).
For example, if n=4,we can get the following equality:
X
12+X
13+X
14=1
X
14+X
24+X
34=1
X
12+X
22+X
32+X
42=X
21+X
22+X
23+X
24 X
13+X
23+X
33+X
43=X
31+X
32+X
33+X
34Now ,we want to know the minimum of ∑C
ij*X
ij(1<=i,j<=n) you can get.
Hint
For sample, X
12=X
24=1,all other X
ij is 0.
Input:
The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1<n<=300).
The next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is C
ij(0<=C
ij<=100000).
Output:
For each case, output the minimum of ∑C
ij*X
ij you can get.
Sample Input:
4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2
Sample Output:
3