#D. 数字三角形

    Type: Default 1000ms 64MiB

数字三角形

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

图示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。

●每一步可沿左斜线向下或右斜线向下走;

●1<三角形行数≤100;

●三角形中的数字为整数0,1,…99;

image

图示

Format

Input

第一行输入一个自然数,表示三角形的行数n; 接下来的n行,表示一个数字三角形。同一行的两个整数之间都有一个空格。

Output

输出一个整数,表示要求的最大总和。

Samples

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30

金牛周日9:00 阶段测试

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
7
Start at
2023-12-17 9:00
End at
2023-12-17 11:00
Duration
2 hour(s)
Host
Partic.
3