## 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

_{34}Now ,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