Start and Link 2

Interview

Time limit2sMemory limit512 MB

Summary

Split N people into two equal teams to minimize the difference between the sums of pairwise ability scores of the two teams.

Level: Medium4 of 10
Topics: Backtracking, Brute force, Combinatorics
Solved: No attempts yet

Problem

Today, people who work at the company gather to play soccer. The game is held on weekday afternoons, and attendance is not mandatory. N people gather to play, and surprisingly, N is even. Now the people must be split into a Start team and a Link team, each with N/2 people.

The company assigned each person a number from 1 to N and surveyed the abilities below. The ability $S_{ij}$ is the amount added to a team when person i and person j are on the same team. A team's ability is the sum of $S_{ij}$ over all pairs in the team. $S_{ij}$ may differ from $S_{ji}$ , and when person i and person j are on the same team, the team gains $S_{ij}$ and $S_{ji}$ .

Consider the case where N=4 and S is as follows.

i\j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

For example, when persons 1 and 2 are on the Start team and persons 3 and 4 are on the Link team, the abilities are:

Start team: S12 + S21 = 1 + 4 = 5
Link team: S34 + S43 = 2 + 5 = 7

When persons 1 and 3 are on the Start team and persons 2 and 4 are on the Link team, the abilities are:

Start team: S13 + S31 = 2 + 7 = 9
Link team: S24 + S42 = 6 + 4 = 10

To make the game fun, the goal is to minimize the difference between the Start team's ability and the Link team's ability. In the example above, if persons 1 and 4 are on the Start team and persons 2 and 3 are on the Link team, both teams have ability 6, so the difference is 0, which is the minimum.

Input

The first line contains N (4 ≤ N ≤ 100, N is even). From the second line on, N lines follow, each containing N numbers. The j-th number on the i-th line is $S_{ij}$ . $S_{ii}$ is always 0, and every other $S_{ij}$ is an integer from 1 to 100, inclusive.

Output

On the first line, print the minimum difference between the abilities of the Start team and the Link team.

Examples3

Example 1
Input
```
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
```
Expected output
```
0
```

Example 2

Input

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

Expected output

Example 3

Input

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

Expected output