Background

Source: https://hsin.hr/hio2023/.

Problem Description

Midnight is approaching, so it is time to hurry up. After Margarita successfully welcomed all guests, they sat down quietly along the long table. We label the guests by the numbers from 1 to $N$ according to the order in which they took their seats. For some unknown reason, the number of guests at Satan’s grand ball is always a power of 2.

However, Margarita now faces a problem: between any two guests there is some degree of impatience ("netrpeljivost"), which we represent by a non-negative number. The impatience between guests $i$ and $j$ is denoted by $netrp(i, j)$. It always holds that $netrp(i, j) = netrp(j, i)$ and $netrp(i, i) = 0$.

Since the guests have already (not very comfortably) settled down, Margarita cannot drastically change their order. The guests do not even know that they are actually sitting on the leaves of a huge Satanic full binary tree, commonly known as VSPBS. When $N=4$, it looks like the figure below.

(a) Figure 1: the initial tree structure, (b) Figure 2: the tree structure after an operation.

Margarita may choose any node and, in one operation, swap the left and right child of that node, thereby changing the order of the guests on the corresponding leaf nodes. The figure above shows the state of the tree (and the table) after Margarita performs one operation on the root. Margarita may perform any number of operations on any nodes.

The total impatience of the table is defined as the sum of the impatience values between every pair of adjacent seated guests. Help Margarita compute the minimum possible total impatience she can achieve.

Input Format

The first line contains a positive integer $N$, denoting the number of guests.

In the next $N$ lines, the $i$-th line (for $1 \le i \le N$) contains $N$ integers, where the $j$-th number represents $netrp(i, j)$. These values satisfy the properties mentioned above.

Output Format

Output the required value.

2
0 2
2 0

2

4
0 2 3 1
2 0 4 5
3 4 0 3
1 5 3 0

6

8
0 2 5 8 5 9 2 6
2 0 8 4 3 7 5 3
5 8 0 3 8 4 3 3
8 4 3 0 2 2 7 7
5 3 8 2 0 7 3 3
9 7 4 2 7 0 6 7
2 5 3 7 3 6 0 4
6 3 3 7 3 7 4 0

25

Hint

[Sample Explanation]

In the second example, one possible arrangement that achieves the minimum impatience is $2,1,4,3$.

[Constraints]

For all subtasks, $1 \leq N \leq 2048$, and $N$ is a power of 2, $0 \leq netrp(i,j) \leq 10^9$.

• Subtask 1 (10 points): $N \leq 16$.
• Subtask 2 (17 points): $N \leq 128$.
• Subtask 3 (32 points): $N \leq 512$.
• Subtask 4 (41 points): no additional constraints.

Translated by ChatGPT 5