题目描述

沿河设置了 $n$ 个码头 $1, 2, \dots, n$（从上游到下游排列）。游客可以在任意码头租船，并在下游的任意码头还船。码头 $i$ 到码头 $j$（$1\le i\lt j\le n$）的单程租金为 $r_{i,j}$。请计算从码头 $1$ 到码头 $n$ 所需的最少租金。

输入格式

第一行一个正整数 $n$，表示码头数量。接下来的 $n-1$ 行是上三角半矩阵 $r_{i,j}$（$1\le i\lt j\le n$）。

输出格式

输出从码头 $1$ 到码头 $n$ 所需的最少租金。

样例

3
5 15
7

12

提示

$1\le n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。