2019春 程序设计能力实训第一次机考

E. 徒弟的下山之路

单点时限: 2.0 sec

内存限制: 512 MB

终于到了出师的日子,徒弟需要从山顶的纯阳宫找一条花费最少时间的下山之路。
这座山用一个三角形来表示,从山顶依次向下有n层,第i层有i个可移动的位置,出口在最下层的左边。例如有一座5层的山:
$\ \ \ \ \ \ \ \ 1$
$\ \ \ \ \ \ 3\ \ 2$
$\ \ \ \ 4\ \ 5\ \ 6$
$\ \ 9\ \ 1\ \ 7\ \ 8$
$1\ \ 1\ \ 4\ \ 5\ \ 6$
$ \ $

此示例中出口为最下层最左边的1所在位置。山上每个数字代表徒弟路过这个位置需要花费的时间,徒弟下山总时间为路径上数字之和。

徒弟每次可以往左、右、左下、右下四个方向移动,例如徒弟位于第3层的数字5时可以向左走到4,向右走到6;也可以向左下走到1,向右下走到7;
又如徒弟位于第3层的数字6时,可以向左走到5,无法向右;也可以向左下走到7,向右下走到8;

输入格式

第一行一个整数n,表示山的高度
接下来n行,第i行有i个整数,表示徒弟经过这个位置需要的时间(路过每个位置花费的时间不超过10)。

数据约束
对于20%的数据,n=4
对于60%的数据,n<=10
对于100%的数据,n<=1000

输出格式

徒弟下山需要花费的最少时间

样例

Input
5
1
3 2
4 5 6
9 1 7 8
1 1 4 5 6
Output
11

提示

徒弟下山花费的时间为1+3+4+1+1+1=11