Two teams with the smallest ability gap

Interview

Time limit2sMemory limit512 MB

Summary

Split N people into two nonempty teams so the difference between the two teams' pairwise ability sums is minimized, and print that minimum.

Level: Medium6 of 10
Topics: Bit manipulation, Brute force, Array, Combinatorics
Solved: No attempts yet

Problem

$N$ people gather to play football. Split them into the Start team and the Link team. The two teams do not have to be the same size, but each team must hold at least one person.

The people are numbered 1 to $N$ , and an ability table $S$ is known. $S_{ij}$ is the ability added to a team when person $i$ and person $j$ are on that team together. The ability of a team is the sum of $S_{ij}$ over every ordered pair of two distinct members. $S_{ij}$ and $S_{ji}$ can differ, and when person $i$ and person $j$ are on the same team, both $S_{ij}$ and $S_{ji}$ are added to that team's ability.

Consider $N = 4$ with the table below.

$S_{ij}$	$j=1$	$j=2$	$j=3$	$j=4$
$i=1$	0	1	2	3
$i=2$	4	0	5	6
$i=3$	7	1	0	2
$i=4$	3	4	5	0

If persons 1 and 2 are the Start team and persons 3 and 4 are the Link team, the Start team's ability is $S_{12} + S_{21} = 1 + 4 = 5$ and the Link team's ability is $S_{34} + S_{43} = 2 + 5 = 7$ . If persons 1 and 3 are the Start team and persons 2 and 4 are the Link team, the Start team has $S_{13} + S_{31} = 2 + 7 = 9$ and the Link team has $S_{24} + S_{42} = 6 + 4 = 10$ .

The goal is to make the difference between the two team abilities as small as possible. For the table above, persons 1 and 4 on the Start team and persons 2 and 3 on the Link team give both teams an ability of 6, so the difference is 0, and no split does better.

Input

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

Each of the next $N$ lines holds $N$ integers describing $S$ . 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 between 1 and 100.

Output

Print the smallest possible difference between the ability of the Start team and the ability of the Link team.

Examples4

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

Example 4

Input

Expected output