暂无测试数据。

长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\ldots,n$。游客可在这些游艇出租站租用游艇，并在 下游 的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r_{i,j}$（$i<j$）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入格式

第一行一个整数 $n\ (1\le n \le 200)$，表示游艇出租站的数量。

接下来的 $n-1$ 行是一个半矩阵 $r_{i,j}\ (1\le r_{i,j} \le 10000)$，表示第 $i$ 个出租站到下游每个出租站的租金。

输出格式

一个整数，表示从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

3
5 15
7

12