题目描述

兔子们之间也是有仇恨值的。我们可以使用一个矩阵表示兔子 i 和兔子j 之间的仇恨值，其中 aij 表示 i 和 j 之间的仇恨值，其中 aij = aji。
大灰狼希望把兔子分成两个集合来饲养，对于每一个集合，定义这个集合中的仇恨值为所
有在这个集合中的兔子两两仇恨值的最大值，即 max{aij}，其中 i 和 j 都属于这个集合。
如果集合中不到 2 只兔子（可以为空集），那么其仇恨值为 0。大灰狼希望计算将 n 个兔子
划分为两个集合之后，两个集合仇恨值之和最小是多少。

输入格式

输入包括多组测试数据，对于每组测试数据：
第一行一个整数 n，表示 n 只兔子。
接下来 n − 1 行，第 i 行有 n − i 个整数，第 j 个表示兔子i 和兔子i + j 之间的仇恨值。

输出格式

对于每组测试数据，一行一个整数，表示两个集合仇恨值之和的最小值。

样例1

输入

5
4 5 0 2
1 3 7
2 0
4
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3

输出

4
15

提示与说明

兔子 1, 2, 4 一个集合，3, 5 另外一个集合。

对于 10% 的数据，1 <= n <= 10。
对于 30% 的数据，1 <= n <= 30。
对于 50% 的数据，1 <= n <= 100。
对于 100% 的数据，1 <= n <= 200, 0 <= aij <= 109。
每个测试点最多有 10 组测试数据。