Link and Start 2

Time limit2sMemory limit512 MB

Summary

Given an N by N matrix of pair values, split N people into two non-empty teams to minimize the difference in their team sums.

Level: Medium5 of 10
Topics: Brute force, Backtracking, Recursion
Solved: No attempts yet

Problem

Today, people who work at the company gather to play soccer. The game is played on weekday afternoons, and attendance is not mandatory. A total of N people have gathered to play. The people must be split into a Start team and a Link team. The two teams do not need the same number of members, but each team must have at least one person.

The company assigns each person a number from 1 to N and surveys the ability values below. The ability value $S_{ij}$ is 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 both $S_{ij}$ and $S_{ji}$ .

Suppose 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, if persons 1 and 2 are on the Start team and persons 3 and 4 are on the Link team, the abilities are:

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

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

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

To make the game fun, the goal is to minimize the difference between the Start team ability and the Link team ability. In the case 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 ≤ 400). The next N lines each contain N integers, and the j-th number in the i-th line is $S_{ij}$ . $S_{ii}$ is always 0. Every other $S_{ij}$ is an integer from 1 to 100, inclusive.

Output

Print the minimum 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