스타트와 링크

오늘은 회사 동료들이 모여서 축구를 하기로 했다. 축구는 평일 오후에 하고 참석은 자유다. 축구를 하려고 모인 사람은 모두 N명이고, N은 짝수다. 이제 N/2명씩 스타트 팀과 링크 팀으로 사람을 나눠야 한다.

사람에게는 1번부터 N번까지 번호를 붙였고, 아래와 같은 능력치를 조사해 두었다. 능력치 $S_{ij}$는 i번 사람과 j번 사람이 같은 팀에 속했을 때 그 팀에 더해지는 능력치다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 $S_{ij}$를 더한 값이다. $S_{ij}$와 $S_{ji}$는 서로 다를 수 있고, i번 사람과 j번 사람이 같은 팀에 속하면 팀에는 $S_{ij}$와 $S_{ji}$가 모두 더해진다.

N이 4이고 S가 아래와 같은 경우를 보자.

1번과 2번이 스타트 팀, 3번과 4번이 링크 팀에 속하면 두 팀의 능력치는 아래와 같다.

• 스타트 팀: $S_{12} + S_{21} = 1 + 4 = 5$
• 링크 팀: $S_{34} + S_{43} = 2 + 5 = 7$

1번과 3번이 스타트 팀, 2번과 4번이 링크 팀에 속하면 두 팀의 능력치는 아래와 같다.

• 스타트 팀: $S_{13} + S_{31} = 2 + 7 = 9$
• 링크 팀: $S_{24} + S_{42} = 6 + 4 = 10$

축구를 재미있게 하려면 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 가장 작게 만들어야 한다. 위 경우에는 1번과 4번이 스타트 팀, 2번과 3번이 링크 팀에 속할 때 스타트 팀의 능력치가 6, 링크 팀의 능력치가 6이 되어 차이가 0이고, 이 값이 최솟값이다.

첫째 줄에 N이 주어진다. ($4 \le N \le 20$, N은 짝수)

둘째 줄부터 N개의 줄에 걸쳐 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번째 줄의 j번째 수가 $S_{ij}$다. $S_{ii}$는 항상 0이고, 나머지 $S_{ij}$는 1보다 크거나 같고 100보다 작거나 같은 정수다.

첫째 줄에 스타트 팀의 능력치와 링크 팀의 능력치의 차이의 최솟값을 출력한다.

두 번째 예제는 (1, 3, 6)과 (2, 4, 5)로 나누면 되고, 세 번째 예제는 (1, 2, 4, 5)와 (3, 6, 7, 8)로 나누면 된다.