시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Ayu was participating in Asian Championship for Mind Sports (ACMS) 2018, a competition where the (supposedly) best mind triumphs. This competition uses a knockout-tournament system with 2N players. A match is played by two opposing players and its result cannot be a tie (i.e. there’s always a winner). In the first round, the 1st player will compete against the 2nd player, the 3rd player will compete against the 4th player, the 5th player will compete against the 6th player, and so on. On the second round, the winner of the first match (1st or 2nd player) will compete against the winner of the second match (3rd or 4th player), and so on. At the last/final round, there will be only two players competing against each other, and there will be one champion.

Needless to say, the ACMS 2018’s champion is Ayu!

Budi, who knows Ayu pretty well, doesn’t believe this fact. He suspects the competition was rigged. Budi also knows all other contestants, and he’s pretty sure these contestants will not cheat or fix any match. So, the only possible set-up is on the organizer side.

Budi has computed a matrix A of 2N ×2N. If Aij is positive, then the ith player will win against the jth with an effort of Aij, if they have a match. On the other hand, if Aij is negative, then the ith player will lose against the jth player in a match; in this case, the absolute value means nothing. Of course, Aii will be zero while all other elements are non-zero. It is guaranteed that exactly one of Aij and Aji will be positive for i ≠ j. The total effort of a player to win the tournament is defined as the sum of all efforts he/she spent in all of his/her matches.

Budi believes that the organizer fixed the initial players/matches arrangement for the first round such that Ayu will win the tournament with the minimum total effort spent. Notice that for a tournament with M player, there are M! arrangements can be made for the first round.

Given the matrix A, your task is to find the players arrangement such that Ayu (the 1st player) wins the tournament with the minimum possible total effort. Output only the total effort. If it’s not possible for Ayu to win the tournament, output −1 instead.

입력

Input begins with an integer N (1 ≤ N ≤ 4) in a line. The next 2N lines, each contains 2N integers: Aij (−1 ≤ Aij ≤ 106; Aii = 0; i ≠ j =⇒ Aij ≠ 0). It is guaranteed that exactly one of Aij and Aji will be positive for i ≠ j. The entries for A1 correspond to Ayu.

출력

Output in a line the minimum total effort needed by Ayu to win the tournament.

예제 입력 1

2
0 1 7 2
-1 0 4 2
-1 -1 0 3
-1 -1 -1 0

예제 출력 1

3

There are 4! = 24 initial arrangements can be made for the first round. Some of them are:

  • (1, 2, 3, 4). Ayu wins against the 2nd player with an effort of 1. The 3rd player wins against the 4th player with an effort of 3. On the final round, Ayu wins against the 3rd player with an effort of 7. The total effort spent by Ayu is 1 + 7 = 8.
  • (3, 1, 2, 4). Ayu wins against the 3rd player with an effort of 7. The 2nd player wins against the 4th player with an effort of 2. On the final round, Ayu wins against the 2nd player with an effort of 1. The total effort spent by Ayu is 7 + 1 = 8.
  • (2, 3, 1, 4). The 2nd player wins against the 3rd player with an effort of 4. Ayu wins against the 4th player with an effort of 2. On the final round, Ayu wins against the 2nd player with an effort of 1. The total effort spent by Ayu is 2 + 1 = 3.
  • . . .

Among all possible permutations for the first round, the minimum possible for Ayu’s total effort to win the tournament is 3.

예제 입력 2

1
0 -1
3 0

예제 출력 2

-1

There is no way Ayu can win the tournament.