漂流（drift）

问题描述

漂流是一种驾驶无动力的橡皮艇或竹筏等户外运动方式。漂流起点到终点有 $N$ 个站点，起点为 1 号站点，终点为 $N$ 号站点，游客可以在这些站点购票，到达下游任何一个站点。求从起点到达终点的最少费用。

输入格式

共两行：

• 第一行，一个数 $N$，意义如题所述。
• 以下 $N$ 行，各行依次编号为 $1 \sim n - 1$，则第 $i$ 行有 $n - i$ 个数，第 $i$ 行的第 $j$ 个数为 $c(i, j)$，表示 $i$ 号站点到 $j$ 号站点的票价。保证 $1 \leq i < j \leq n$。

输出格式

一个整数，从起点到终点的最小费用。

输入输出示例

• 输入 1：

3
5 15
7

• 输出 1：

12

• 输入 2：

4
3 7 19
5 13
8

• 输出 2：

15

数据范围

• $N \leq 2000$
• $c(i, j) \leq 1000000$