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

问题描述

漂流是一种驾驶无动力的橡皮艇或竹筏等户外运动方式。漂流起点到终点有 N 个站点，起点为 1 号站点，终点为 N 号站点，游客可以在这些站点购票，到达下游任何一个站点。求从起点到达终点的最少费用。70q100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

共两行：第一行，一个数 N，意义如题所述。以下 N 行，各行依次编号为 1∼n−1，则第 11 行有 n−i 个数，第 i 行的第 j 个数为 c(i,j)，表示 i 号站点到 j 号站点的票价。保证 1≤i<j≤n。70q100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

一个整数，从起点到终点的最小费用。70q100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

数据样例

输入数据 1

3 
5 15 
7

输出数据 1

12

输入数据 2

4 
3 7 19 
5 13 
8 

输出数据 2

15

数据范围

• N≤2000
• c(i,j)≤1000000