说明

给定一个具有N层的数字三角形,从顶至底有多条路径，每一步都可沿左斜线或右斜线向下，路径所经过的数字之和为路径得分,求最小路径得分

输入格式

输入数据共n+1行，第1行为一个正整数n，表示三角形的行数(n<=1500)第2~n+1行，为所对应的三角形，所有数字均为小于2,000,000的整数

输出格式

输出数据为最小路径得分

样例

4
2
6 2
1 8 4
1 5 6 8

10