링크와 스타트 2

시간 제한2초메모리 제한512 MB

요약

N명을 두 팀으로 나눌 때, 각 팀의 쌍별 능력치 합의 차이가 가장 작은 값을 구합니다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 백트래킹, 재귀
정답자: 아직 제출이 없습니다

문제

오늘은 회사에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 이 사람들을 스타트 팀과 링크 팀으로 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 각 팀에 한 명 이상이 있어야 한다.

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

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

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

예를 들어, 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이 되어 차이가 0이 되고, 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 400)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 $S_{ij}$ 이다. $S_{ii}$ 는 항상 0이고, 나머지 $S_{ij}$ 는 1 이상 100 이하의 정수이다.

출력

스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력한다.

예제4

예제 1
입력
```
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
```
예상 출력
```
0
```

예제 2

입력

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

예상 출력

예제 3

입력

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

예상 출력

예제 4

입력

예상 출력