Start and Link

Time limit2sMemory limit512 MB

Summary

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

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

Problem

Coworkers are getting together this afternoon to play football. The match is on a weekday and nobody has to join. N people showed up, and N is even. You have to split them into a Start team and a Link team of N/2 people each.

The people are numbered from 1 to N, and their ability values were measured as described below. The ability value $S_{ij}$ is added to a team when person i and person j belong to that team together. The ability of a team is the sum of $S_{ij}$ over every pair in the team. $S_{ij}$ and $S_{ji}$ can differ, and when person i and person j belong to the same team, both $S_{ij}$ and $S_{ji}$ are added to that team.

Look at the case where N is 4 and S is the table below.

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

If persons 1 and 2 belong to the Start team and persons 3 and 4 belong to the Link team, the two teams have these abilities.

Start team: $S_{12} + S_{21} = 1 + 4 = 5$
Link team: $S_{34} + S_{43} = 2 + 5 = 7$

If persons 1 and 3 belong to the Start team and persons 2 and 4 belong to the Link team, the two teams have these abilities.

Start team: $S_{13} + S_{31} = 2 + 7 = 9$
Link team: $S_{24} + S_{42} = 6 + 4 = 10$

A good match needs the difference between the ability of the Start team and the ability of the Link team to be as small as possible. In the case above, persons 1 and 4 on the Start team and persons 2 and 3 on the Link team give the Start team an ability of 6 and the Link team an ability of 6, so the difference is 0, and that is the minimum.

Input

The first line contains N ( $4 \le N \le 20$ , N is even).

Each of the next N lines describes one row of S. Each of those lines has N numbers, and 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 that is at least 1 and at most 100.

Output

Print the minimum difference between the ability of the Start team and the ability of the Link team on the first line.

Hint

The second example splits into (1, 3, 6) and (2, 4, 5). The third example splits into (1, 2, 4, 5) and (3, 6, 7, 8).

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