题目描述

<div class="O"> <div> 给定一个具有N层的数学三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。 </div> <div>      2 </div> <div>     6 2 </div> <div>    1 8 4 </div> <div>   1 5 6 8 </div> <div> </div> </div>

输入格式

<div class="O"> <div> 第1行，一个正整数n，表示三角形的行数 </div> <div> 第2至n+1行，照描述输入三角形 </div> <div> </div> </div>

输出格式

<div class="O"> 最小路径得分，行末有换行 </div>

样例

样例 1

输入 # 1

4
2
6 2
1 8 4
1 5 6 8

输出 # 1

10