Problem Description

As night falls, caution is necessary. After Margarita successfully greeted all the guests, they sat down without obstruction on the benches.

We can label the guests with numbers from $1$ to $N$, exactly in the order they sit on the benches. For unknown reasons, at the grand ball in Sotoni, the number of guests is always a power of $2$. However, Margarita now faces a problem because there is a certain level of impatience between each pair of guests, which we can represent with a non-negative number. The impatience between guests can be marked as $netrp(i, j)$. There is always $netrp(i, j) = netrp(j, i)$, and $netrp(i, i) = 0$. Since the guests are already seated (un)comfortably, Margarita cannot suddenly change their order. In fact, the guests are unaware that they are in a list of a complete binary tree (velikog Sotoninog potpunog binarnog stabla, VSPBS), which is shown in the picture for the case of $N=4$.

(a) Figure 1: Initial tree structure, (b) Figure 2: Tree structure after operation

Margarita can choose a node and, in one operation, swap the left child and the right child of that node, thereby changing the order of the guests located at the corresponding leaf nodes. The figure shows the tree structure (and the state of the benches) after Margarita performs an operation on the root node of the tree. Margarita can perform operations on any node any number of times. The total impatience on the benches is defined as the sum of the impatience between all adjacent guests on the benches. Help Margarita determine the minimum possible total impatience she can achieve.

Input Format

The first line contains a natural number $N$, representing the number of guests. The next $N$ lines contain the numbers $netrp(i, j)$ in order, satisfying the above properties.

Output Format

Output the minimum impatience.

Sample Input and Output

Sample Input #1

2
0 2
2 0

Sample Output #1

2

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

25

Notes

[Sample Explanation]

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

[Data Range]

In all subtasks, it is guaranteed that $1 \leq N \leq 2048$, $N$ is a power of $2$, and $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.

见题面 Input 部分

见题面 Output 部分