午夜将至，必须抓紧时间。在玛格丽特（Margarita）成功迎接所有客人后，他们顺利地在一张长桌旁坐下。我们可以用 $1$ 到 $N$ 的数字来标记客人，正是他们坐在桌子旁的顺序。由于未知的原因，撒旦盛大舞会上的客人数量总是 $2$ 的幂。

然而，玛格丽特现在遇到了一个问题，因为每对客人之间都存在一定的敌意，可以用一个非负整数来表示。客人 $i$ 和 $j$ 之间的敌意可以表示为 $netrp(i, j)$。始终满足 $netrp(i, j) = netrp(j, i)$ 且 $netrp(i, i) = 0$。

由于客人们已经（不）舒服地坐好了，玛格丽特不能剧烈地改变他们的顺序。客人们实际上甚至不知道他们位于一棵巨大的撒旦完美二叉树（简称 VSPBS）的叶子节点上，在 $N = 4$ 的情况下如图所示。

(a) 图 1：初始树；(b) 图 2：操作后的树

玛格丽特可以选择某个节点，并在一步操作中交换该节点的左孩子和右孩子，从而改变其对应叶子节点中客人的顺序。图中展示了玛格丽特对树根进行一次操作后，树的状态以及桌旁客人的状态。玛格丽特可以对任意节点进行任意次数的操作。

长桌的总敌意定义为桌上相邻客人之间的敌意之和。请帮助玛格丽特确定她能达到的最小可能总敌意！

输入格式

第一行包含一个自然数 $N$，表示客人的数量。

接下来的 $N$ 行中，第 $i$ 行依次包含 $N$ 个整数，表示满足上述性质的 $netrp(i, j)$。

输出格式

输出题目中要求的最小总敌意。

数据范围

在所有子任务中，满足 $1 \le N \le 2048$，且 $N$ 是 $2$ 的幂，$0 \le netrp(i, j) \le 10^9$。

样例

输入格式 1

2
0 2
2 0

输出格式 1

2

输入格式 2

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

输出格式 2

6

输入格式 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

输出格式 3

25

说明

在第二个样例中，达到最小敌意的一种可能排列是 2 1 4 3。