Start and Link

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.

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.

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.

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

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).