16596번 - Fair Tournament 다국어

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 2^N 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 1^st player will compete against the 2^nd player, the 3^rd player will compete against the 4^th player, the 5^th player will compete against the 6^th player, and so on. On the second round, the winner of the first match (1^st or 2^nd player) will compete against the winner of the second match (3^rd or 4^th 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 2^N ×2^N. If Aij is positive, then the i_th player will win against the j^th with an effort of A_ij, if they have a match. On the other hand, if A_ij is negative, then the i^th player will lose against the j^th player in a match; in this case, the absolute value means nothing. Of course, A_ii will be zero while all other elements are non-zero. It is guaranteed that exactly one of A_ij and A_ji 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 1^st 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 2^N lines, each contains 2^N integers: A_ij (−1 ≤ A_ij ≤ 10⁶; A_ii = 0; i ≠ j =⇒ A_ij ≠ 0). It is guaranteed that exactly one of Aij and Aji will be positive for i ≠ j. The entries for A₁ correspond to Ayu.

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