你可能已经听说过旅行商问题（TSP）。如果是这样，你一定知道它是一个 NP-hard 问题，因为目前还没有高效的解决方案。不过，本题是这个著名问题的一个不寻常的版本！它的不寻常之处在于，这个版本实际上是可解的。

旅行商的任务是访问 $N$ 个城市，每个城市恰好访问一次。这些城市用数字 $1, 2, \dots, N$ 表示。我们已知每对城市之间的直飞航班耗时。这位高效的旅行商希望调整访问城市的顺序，使得总飞行时间尽可能短。

然而，事情并没有那么简单。此外，旅行商对访问顺序有一个奇特的限制。对于每个编号为 $K$ 的城市，必须满足以下条件之一：要么所有编号小于 $K$ 的城市都在城市 $K$ 之前被访问，要么它们都在城市 $K$ 之后被访问。换句话说，不允许出现某些编号小于 $K$ 的城市在 $K$ 之前访问，而另一些在 $K$ 之后访问的情况。

请帮助这位雄心勃勃的旅行商，计算出从任意城市出发并在任意城市结束、每个城市恰好访问一次且满足其奇特要求的最小总飞行时间。

输入格式

输入的第一行包含一个正整数 $N$ ($2 \le N \le 1500$)，表示城市的数量。

接下来的 $N$ 行，每行包含 $N$ 个范围在 $[0, 1000]$ 内的非负整数。第 $A$ 行的第 $B$ 个数字表示城市 $A$ 和城市 $B$ 之间的飞行时间；该数字等于第 $B$ 行的第 $A$ 个数字。当 $A = B$ 时，该数字为 $0$。否则，它是一个正数。

输出格式

输出的第一行也是唯一的一行，应包含所需的最小总飞行时间。

子任务

在占总分 $1/3$ 的测试数据中，$N$ 最多为 $10$。

在占总分 $1/2$ 的测试数据中，$N$ 最多为 $20$。

样例

输入样例 1

3
0 5 2
5 0 4
2 4 0

输出样例 1

7

输入样例 2

4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

输出样例 2

31

说明

样例 1 说明：最优序列为 2, 1, 3 或 3, 1, 2。序列 1, 3, 2 虽然用时更短，但不满足旅行商的条件。

样例 2 说明：最优序列为 3, 1, 2, 4 或 4, 2, 1, 3。