공정한 토너먼트

Ayu는 ASIAN CHAMPIONSHIP FOR MIND SPORTS (ACMS) 2018에 참가했다. 이 대회는 (어쨌든) 가장 뛰어난 정신이 승리하는 대회이다. 대회는 2N명의 선수가 참가하는 토너먼트 방식으로 진행된다. 경기는 두 선수가 맞붙어 치르며, 무승부는 없다(즉, 항상 승자가 존재한다). 1라운드에서는 1번 선수와 2번 선수, 3번 선수와 4번 선수, 5번 선수와 6번 선수가 맞붙는 식으로 경기가 진행된다. 2라운드에서는 첫 경기의 승자(1번 또는 2번 선수)와 두 번째 경기의 승자(3번 또는 4번 선수)가 맞붙는 식으로 경기가 진행된다. 마지막 라운드에서는 두 선수만이 남아 서로 맞붙고, 우승자가 한 명 나온다.

말할 필요도 없이, ACMS 2018의 우승자는 Ayu이다!

Ayu를 잘 아는 Budi는 이 사실을 믿지 않는다. 그는 대회가 조작되었다고 의심한다. Budi는 다른 참가자들도 모두 알고 있으며, 그 참가자들이 부정행위를 하거나 경기를 조작하지 않는다는 것도 확신한다. 따라서 유일하게 가능한 조작은 주최 측에서 일어난 것이다.

Budi는 2N × 2N 크기의 행렬 A를 계산했다. Aij가 양수이면 i번 선수가 j번 선수와 경기할 때 Aij의 노력으로 이긴다. 반면 Aij가 음수이면 i번 선수는 j번 선수와의 경기에서 진다. 이 경우 절댓값은 아무 의미가 없다. 물론 Aii는 0이고 다른 모든 원소는 0이 아니다. i ≠ j일 때 Aij와 Aji 중 정확히 하나만 양수임이 보장된다. 선수가 토너먼트에서 우승하기 위해 소모한 총 노력은 그 선수가 모든 경기에서 소모한 노력의 합으로 정의된다.

Budi는 주최 측이 Ayu가 최소의 총 노력으로 토너먼트에서 우승하도록 1라운드의 초기 선수 및 경기 배치를 조작했다고 믿는다. M명의 선수가 참가하는 토너먼트에서 1라운드 배치는 M!가지가 가능하다는 점에 유의하라.

행렬 A가 주어졌을 때, Ayu(1번 선수)가 최소의 총 노력으로 토너먼트에서 우승하도록 선수 배치를 찾아야 한다. 총 노력만 출력하라. Ayu가 토너먼트에서 우승하는 것이 불가능하다면 대신 −1을 출력하라.

첫 줄에 정수 N (1 ≤ N ≤ 4)이 주어진다. 다음 2N개의 줄에 각각 2N개의 정수 Aij가 주어진다 (−1 ≤ Aij ≤ 10^6; Aii = 0; i ≠ j이면 Aij ≠ 0). i ≠ j일 때 Aij와 Aji 중 정확히 하나만 양수임이 보장된다. A1에 해당하는 원소들은 Ayu에 대한 것이다.

Ayu가 토너먼트에서 우승하기 위해 필요한 최소 총 노력을 한 줄에 출력한다.