Yulia 在叶卡捷琳堡的一家金属加工厂工作。该工厂处理在乌拉尔山脉开采的矿石，从中提取黄铜矿、铂和金等贵金属。每个月，工厂都会收到 $n$ 批未加工的矿石。Yulia 需要根据相似度将这些矿石批次分成两组。然后，每一组会被送往工厂的两座矿石加工大楼之一。

Picture from Wikimedia Commons

为了进行这种划分，Yulia 首先计算了每一对矿石批次 $1 \le i \le n$ 和 $1 \le j \le n$ 之间的数值距离 $d(i, j)$，其中距离越小，表示批次 $i$ 和 $j$ 越相似。对于矿石批次的子集 $S \subseteq \{1, \dots, n\}$，她定义该子集的差异度 $D$ 为子集中一对矿石批次之间的最大距离，即：

$$D(S) = \max_{i, j \in S} d(i, j)$$

随后，Yulia 将这些矿石批次划分为两个子集 $A$ 和 $B$，使得它们的差异度之和 $D(A) + D(B)$ 最小化。你的任务是帮助她找到这种划分方式。

输入格式

输入包含一组测试数据。第一行包含一个整数 $n$ ($1 \le n \le 200$)，表示矿石批次的数量。接下来的 $n - 1$ 行包含距离 $d(i, j)$。其中第 $i$ 行包含 $n - i$ 个整数，该行第 $j$ 个整数给出了 $d(i, i + j)$ 的值。距离是对称的，即 $d(j, i) = d(i, j)$，且矿石批次到自身的距离为 $0$。所有距离均为 $0$ 到 $10^9$ 之间的整数（包含边界值）。

输出格式

输出将矿石批次分为两组后，差异度之和的最小值。

样例

输入格式 1

5
4 5 0 2
1 3 7
2 0
4

输出格式 1

4

输入格式 2

7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3

输出格式 2

15