题目描述

给定一个如下图所示的数字三角形。请编写程序，找出一条从顶端出发、到达底边任意位置的路径，使经过的数字之和最大。

每走一步，只能走到下一行中当前数字左下方或右下方相邻的数字。

图中路径 $7\to3\to8\to7\to5$ 的数字之和为 $30$，是这个三角形中能够取得的最大值。

输入格式

第一行一个整数 $R$，表示三角形的行数。

接下来 $R$ 行依次给出三角形中的数字，第 $i$ 行包含 $i$ 个整数。

输出格式

输出一个整数，表示从顶端到底边的路径所能取得的最大数字和。

样例输入 1

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

样例输出 1

30

样例输入 2

8
20
94 41
33 52 74
34 78 87 23
40 5 67 77 72
15 59 49 74 97 7
82 35 11 99 35 72 71
38 37 38 5 32 34 89 43

样例输出 2

588

样例输入 3

11
51
11 32
85 27 26
13 77 13 83
99 79 11 52 35
70 44 51 65 69 76
40 23 88 41 3 58 99
12 75 33 7 22 44 89 21
13 54 16 6 1 47 65 43 96
62 25 3 10 11 91 46 63 17 23
15 64 24 5 69 11 9 12 98 45 58

样例输出 3

717

说明/提示

数据范围

$1\le R\le1000$。

所有数字均为非负整数，且不大于 $100$。