Description

给定一个高度为 n （1 ≤ n ≤ 100）的“数字三角形”，其中第 i 行（1<=i<=n）有 i 个数。

1

2 3

4 5 6

7 8 9 10

初始时，你站在“数字三角形”的顶部，即第一行的唯一一个数上。每次移动，你可以选择移动到当前位置正下方或者当前位置右下方的位置上。即如果你在 (i,j)（表示你在第i行从左往右数第j个数上，下同），你可以选择移动到 (i+1,j) 或 (i+1,j+1)。

你想让你经过的所有位置（包括起点和终点）的数字总和最大。求这个最大值。

Input Format

第一行一个正整数 n，表示数字三角形的大小。 第 2 行到第 n+1 行，第 i+1 行为 i 个用空格隔开的非负整数，描述数字三角形的第 i 行。

Output Format

一行一个整数，表示经过路径上数的最大总和。

4
1
2 3
4 5 6
7 8 9 10​

20​

Hint

对样例解释

不停地向右下走即可。

Source

动态规划