题目描述

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

求从起点到达终点的最少费用。

输入格式

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

输出格式

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

输入样例#1

3 
5 15 
7

输出样例#1

12

输入样例#2

4 
3 7 19 
5 13 
8

输出样例#2

15

题目说明

$N≤2000 \space c(i,j)≤1000000$