Midnight was approaching, and it was time to hurry. After Margarita successfully greeted all the guests, they sat down at a long table without any issues. We can label the guests with numbers from $1$ to $N$, exactly in the order they sat at the table. For unknown reasons, the number of guests at Satan's grand ball is always a power of $2$.

However, Margarita now faces a problem, because there is a certain animosity between every pair of guests, which we can denote with a non-negative number. The animosity between guests $i$ and $j$ can be denoted as $netrp(i, j)$. It always holds that $netrp(i, j) = netrp(j, i)$ and $netrp(i, i) = 0$.

Since the guests have already settled in (un)comfortably, Margarita must not drastically change their order. The guests actually do not even know that they are located in the leaves of a large Satanic full binary tree, popularly called VSPBS, which is shown in the figure for the case $N = 4$.

(a) Figure 1: tree at the beginning (b) Figure 2: tree after the operation

Margarita can choose any node, and in one move, swap the left and right child of that node, thereby changing the order of the guests located in the corresponding leaves. The state of the tree, and thus the table, is shown after Margarita makes one move on the root of the tree. Margarita can make an arbitrary number of moves on arbitrary nodes.

The total animosity of the table is defined as the sum of the animosities of neighbors at the table. Help Margarita determine the minimum possible animosity of the table she can achieve!

Input

The first line contains a natural number $N$, the number of guests.

In the $i$-th of the next $N$ lines, there are the numbers $netrp(i, j)$ in order, which satisfy the above properties.

Output

Print the required number from the problem.

Subtasks

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

Examples

Input 1

2
0 2
2 0

Output 1

2

Input 2

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

Output 2

6

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

Output 3

25

Note

In the second example, one of the possible arrangements that achieves the minimum animosity is 2 1 4 3.