单点时限: 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
徒弟下山需要花费的最少时间
5 1 3 2 4 5 6 9 1 7 8 1 1 4 5 6
11
徒弟下山花费的时间为1+3+4+1+1+1=11