Migrated from Lutece 2543 送信分配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。 ——《Theme of Violet Evergarden》

在 Violet 一段时间的培训之后，Taylor 终于有能力独自送信了。因此今天 Violet 和 Taylor 一起去分别送信。

莱顿沙夫特里希国的首都莱登有 $n$ 个街区，分别编号为 $1$ 到 $n$，C·H 邮政公司的总部所在街区编号为 $1$。她们今天就要在这 $n$ 个街区中穿梭送信。

Violet 和 Taylor 会从总部出发。送信不会走回头路，所以每个人各自所到达的街区编号只能是递增的。并且在街区之间穿梭是很耗费体力的，因此在不同街区之间穿梭都有一个代价，但街区内穿梭相对简单，代价忽略不计。总得说来，对于 $i<j$，任何一个人从 $i$ 街区前往 $j$ 街区都会耗费体力值 $a_{i,j}$；如果 $i>j$，则不允许这样移动。

没有任何一封信是不必送达的，Violet 和 Taylor 必须走遍所有街区，把信送出，也就是说每个街区至少要有一个人到过才行。为了完成今天的送信任务，必须提前将每个人要到的街区和送的信件分配好，Violet 想知道，为了完成任务，两人所需花费的体力值和最小是多少。

Input

第一行一个整数 $n$，表示街区数。

接下来 $n-1$ 行，第 $i$ 行包含 $n-i$ 个整数 $a_{i,i+1},\ldots, a_{i,n}$。表示在街区间穿梭所要花费的体力值。

Output

输出一行一个整数，表示为了完成送信任务，两人所需花费的体力值和的最小值。

Samples

4
1 1 4
5 1
4

3

Constraints

$2\le n\le 2000,1\le a_{i,j}\le 10^6$

Note

对于此样例，两人可以分别在 $1$ 街区送信，送后，Violet 前往 $2$ 街区，Taylor 前往 $3$ 街区送信，分别花费 $1$ 体力，送后，Violet 花费 $1$ 体力前往 $4$ 街区送信。这样 $4$ 个街区都有人送信了。两人花费体力和也达到了最小值 $3$。

Resources

2021 UESTC ICPC Training for Dynamic Programming