한쪽으로 치우친 팀 구성

동료 Sergey와 함께, 당신은 작은 회사의 동료들을 위한 흥미진진한 당구와 포켓볼 대회를 준비하고 있다. 그러나 두 사람 사이의 의사소통은 원활하지 않았다. 당신과 Sergey가 같은 생각을 하는지 확신할 수 없지만, 당신이 보기에는 이 대회가 팀워크를 다질 좋은 기회다. 실제 상금은 의미가 없지만, 팀 결속이라는 면에서 얻을 것이 많을 수 있다. 당신은 결과를 최대화하고 싶다.

팀 관리에 관한 의사과학 서적을 읽기 시작하고, 조사 끝에 팀 결속에 좋은 두 가지 방법이 있다는 결론을 내린다. 사람들은 압도적인 승리 후에도, 참담한 패배 후에도 서로 더 가깝게 느낀다. 여기서 좋은 아이디어가 떠오른다. 동료들을 실력 차이가 최대한 큰 두 그룹으로 나누면 두 팀 모두 결속력이 향상된다! 따라서 팀을 최대한 불균형하게 만드는 것이 최적이라고 생각한다. 다만 두 팀의 크기는 같아야 한다.

약간의 고민 끝에 팀의 강도를 나타내는 좋은 모델을 떠올린다. 팀의 강도는 주로 두 선수가 얼마나 잘 어울려 플레이하는지, 서로를 격려하고 상대의 약점을 보완해 주는지에 달려 있다고 본다. 두 선수 $i$와 $j$가 같은 팀에 있으면 팀 점수가 정수 $c_{i,j}$만큼 증가한다. 따라서 팀의 총점은 팀에 속한 모든 비순서쌍 $(i, j)$에 대한 $c_{i,j}$의 합과 같다.

입력은 다음과 같다.

• 짝수 정수 $n$ ($2\leq n\leq 1000$)이 있는 한 줄. 이는 전체 선수 수다.
• $n$개의 줄. $i$번째 줄에는 $n$개의 정수 $c_{i,1}, c_{i,2}, \dots, c_{i, n}$이 있다 ($-10^6 \leq c_{i,j} \leq 10^6$). 모든 $i$와 $j$에 대해 $c_{i,i} = 0$이고 $c_{i,j} = c_{j,i}$임이 보장된다.

크기가 같은 두 팀 사이의 강도 차이로 가능한 최댓값을 출력한다.