给定一个数组 $[1, 2, \dots, n]$，其中 $n$ 为偶数。

在一次操作中，你可以删除数组中两个相邻的元素。如果这两个元素是 $i$ 和 $j$，则该操作的代价为 $cost(i, j)$。

经过 $\frac{n}{2}$ 次操作后，所有元素都将被删除。删除整个数组的代价定义为这 $\frac{n}{2}$ 次操作中代价的最大值。

求删除整个数组的最小可能代价。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 4000, n$ 为偶数)。

我们很友善，所以不会提供不必要的输入。可以证明，在任何时候，两个奇偶性相同的数字都不可能相邻，因此我们不会提供这些数对的代价。

接下来的 $n - 1$ 行中，第 $i$ 行包含 $\frac{n-i+1}{2}$ 个整数。如果 $i$ 是偶数，这些整数依次为 $cost(i, i + 1), cost(i, i + 3), \dots, cost(i, n - 1)$。否则，它们依次为 $cost(i, i + 1), cost(i, i + 3), \dots, cost(i, n)$。

保证这些代价构成了从 $1$ 到 $(\frac{n}{2})^2$ 的一个排列。

输出格式

输出一个整数：删除整个数组的最小可能代价。

样例

样例输入 1

2
1

样例输出 1

1

样例输入 2

6
2 1 3
4 5
6 7
8
9

样例输出 2

6

样例输入 3

10
20 21 2 11 25
3 24 18 8
6 17 7 5
22 4 23
14 15 1
19 16
12 10
13
9

样例输出 3

14

说明

在第一个样例中，数组为 $[1, 2]$，且 $cost(1, 2) = 1$。因此，删除该数组的唯一方式的总代价为 $1$。

在第二个样例中，删除数组的一种方式如下：

• $[1, 2, 3, 4, 5, 6] \to [1, 2, 5, 6]$，删除代价为 $6$ 的数对 $(3, 4)$。
• $[1, 2, 5, 6] \to [1, 6]$，删除代价为 $5$ 的数对 $(2, 5)$。
• 然后删除代价为 $3$ 的数对 $(1, 6)$。

因此，总代价为 $\max(6, 5, 3) = 6$。