Given a n*n matrix Cij
(1<=i,j<=n),We want to find a n*n matrix Xij
(1<=i,j<=n),which is 0 or 1.
meets the following conditions:
3.for each i (1<i<n), satisfies ∑Xki
For example, if n=4,we can get the following equality:
Now ,we want to know the minimum of ∑Cij
(1<=i,j<=n) you can get.
For sample, X12
=1,all other Xij
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 Cij
For each case, output the minimum of ∑Cij
you can get.
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2