题目描述

给定一个数字金字塔，从顶部出发，每一步可以向左下或右下移动一步，直到到达底部。请找出从顶部到底部的一条路径，使得路径上所有数字之和最大。

如下方示例，从 $7$ 到 $3$ 到 $8$ 到 $7$ 到 $5$ 的路径和为 $30$，是所有路径中的最大值。

输入格式

第一行包含整数 $R$（$1 \le R \le 1000$），表示金字塔的行数。接下来 $R$ 行，第 $i$ 行包含 $i$ 个非负整数，每个整数不超过 $100$，表示金字塔第 $i$ 行的数字。

输出格式

一行一个整数，表示从顶部到底部的最大路径和。

样例

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

30

提示

动态规划：从第二行开始，每个位置取上方两个方向的最大值累加即可。