[AdditionalFile5491.zip](file://AdditionalFile5491.zip?type=additional_file)

#5491. 「COI 2023」Netrpeljivost

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2023 T3「Netrpeljivost」

午夜临近，时间紧迫。在玛格丽特成功地迎接了所有宾客后，他们舒适地在一张长桌旁就座。我们可以按照宾客们入座的顺序，用从 $1$ 到 $N$ 的数字为他们编号。有趣的是，在撒旦的盛大舞会上，宾客的数量恰好是 $2$ 的整数次幂。

然而，玛格丽特现在遇到了麻烦，因为每对宾客之间都存在一定的反感度，我们可以用一个非负数来表示。宾客 $i$ 和 $j$ 之间的反感度可以表示为 $netrp(i, j)$。请注意，始终满足 $netrp(i, j) = netrp(j, i)$ 且 $netrp(i, i) = 0$。

由于宾客们已经（不）舒适地就座，玛格丽特不能大幅改变他们的顺序。事实上，宾客们并不知道，他们其实是一棵巨大的撒旦完全二叉树的叶子节点，这棵树通常被称为 VSPBS，在 $N=4$ 的样例图片中有所描绘。

初始状态的树和经过一次操作后的树如下：

玛格丽特可以选择一个节点，并在一次移动中交换其左右子节点，从而改变位于相应叶子节点的宾客顺序。上图展示了玛格丽特在树的根节点上进行一次操作后，树以及餐桌的状态。玛格丽特可以在任意节点上进行任意次数的移动。

餐桌的总反感度定义为餐桌上相邻宾客之间反感度的总和。请帮助玛格丽特确定她能实现的餐桌最小可能反感度！

输入格式

第一行包含整数 $N$，即宾客的数量。

接下来的 $N$ 行中，第 $i$ 行包含整数 $netrp(i, j)$，这些值满足上述条件。

输出格式

你应该输出所要求的数字。

样例 1

输入

2
0 2
2 0

输出

2

样例 2

输入

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

输出

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

输出

25

数据范围与提示

对于所有输入数据，满足 $1 \leq N \leq 2048$ 且 $N$ 是 $2$ 的整数次幂，$0 \leq netrp(i, j) \leq 10^{9}$。

详细子任务附加限制及分值如下表所示：