共有 $n$ 个游艇出租站 $1,2,\dots ,n$。可在这些出租站租用游艇，并在下游（较当前出租站编号更大）的任何一个游艇出租站归还游艇。
游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r(i,j)(1\le i,j\le n)$。
如上述的方法，从第 $1$ 个出租站开始，通过租用游艇，直到第 $n$ 个游艇，试编写一个程序，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。
保证计算过程中的任何数值都不超过 ${10}^6$。

文件的第 $1$ 行中有 $n$ 个正整数 ，表示有 $n$ 个游艇出租站。
接下来的 $n-1$ 行是一个半矩阵，半矩阵的第 $i$ 行有 $n-i$ 个数 ,半矩阵的第 $i$ 行第 $j$ 列表示 $r(i,j+1)$。

输出仅有一行，表示从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

3
5 15
7

12