10120 동아리 분반 Silver II

문제

N명의 학생을 두 개의 분반(A반, B반)으로 정확히 N/2명씩 나누어야 한다. N은 항상 짝수이다.

학생 i와 학생 j의 친밀도 F[i][j]가 주어진다. 친밀도는 대칭(F[i][j] = F[j][i])이며, F[i][i] = 0이다.

어떤 반의 화합도는 그 반에 속한 모든 학생 쌍의 친밀도의 합이다. A반의 화합도와 B반의 화합도의 차이의 절댓값을 최소화하는 분반 방법을 찾고, 그 최솟값을 구하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 18, 짝수)이 주어진다.

다음 N개의 줄에 N×N 친밀도 행렬 F가 주어진다. (0 ≤ F[i][j] ≤ 100)

출력

두 반의 화합도 차이의 최솟값을 출력한다.