Minimizing Bench Discomfort

After sunset, Margarita faced a delicate situation. Having greeted all the guests successfully, they sat on a long bench in the order of their labels from \(1\) to \(N\). Here, \(N\) is a power of two. However, there is an underlying tension among the guests quantified by a non-negative number \(netrp(i,j)\) for every pair \((i,j)\). It is guaranteed that \(netrp(i,j)=netrp(j,i)\) and \(netrp(i,i)=0\).

The guests are arranged as the leaves of a complete binary tree. Margarita, however, is allowed to perform an operation on any node: she may swap its left and right children. Such an operation effectively reverses the order of the guests in the corresponding subtree. She may perform these operations arbitrarily many times on any nodes, but she is not allowed to arbitrarily change the overall seating order.

The total bench discomfort is defined as the sum of the impatience values between each pair of adjacent guests on the bench. Formally, if the final seating order is \(a_1,a_2,\ldots,a_N\), the total discomfort is

[ \sum_{i=1}^{N-1} netrp(a_i,a_{i+1}). ]

Your task is to help Margarita determine the minimum possible total bench discomfort achievable by performing any sequence of allowed swap operations on the tree.

inputFormat

The first line contains an integer \(k\), where \(N = 2^k\) is the number of guests.

The following \(N\) lines each contain \(N\) non-negative integers. The \(j\)th integer on the \(i\)th line is \(netrp(i,j)\). It is guaranteed that \(netrp(i,j)=netrp(j,i)\) and that \(netrp(i,i)=0\).

outputFormat

Output a single integer: the minimum total discomfort achievable.

sample

1
0 1
1 0

1