Description

给定一个n的一个三角形路径图，从（1.1）的位置出发，每次只能向下或者向右下走，每经过一个位置就把当前位置的数字加起来（包括起点），找到走完n行以后的最大值是多少？

Input Format

第一行n,表示一共有n行（n<=20）。

后面的n行，每次输入对应个数的数字。每个值不超过10；

Output Format

一个数字，表示最大的值是多少。

3
1
1 2
1 2 3

6

Source

信奥星OJ http://127.0.0.1