UOJ Logo 小司码 Online Judge

XSMOJ

第463题   数字三角形1

Statistics

题目描述

​如下所示为一个数字三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编程计算从顶至底部某处的一条路径,使该路径所经过的数字的总和最大。约定: (1) 每一步可沿直线向下或右斜线向下走; (2) 1≤三角形行数≤100; (3) 三角形中的数字为整数 0,1,…,99。

输入格式

第一行为一个自然数,表示数字三角形的行数 n;

接下来的 n 行,表示一个数字三角形。同一行的两数之间都有一个空格。

输出格式

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

样例数据

input


5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

output


30

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$64 \text{MB}$