题目描述

有一个 $n$ 行的数字三角形。它的第 $i$（$1 \le i \le n$） 行包含 $i$ 个数字。

我们用 $a_{i, j}$ 表示数字三角形中第 $i$ 行从左往右第 $j$ 个数字。

比如，下图演示了一个 $n = 5$ 行的数字三角形的结构：

你现在需要从数字三角形的第一行往下走到第 $n$ 行。

每次移动，你只能从当前所在的位置移动到左下或右下的那个位置。也就是说：

• 如果你当前在数字 $a_{i, j}$ 位置，你一步移动只能移动到 $a_{i+1, j}$（左下）或 $a_{i+1, j+1}$（右下）。

你的得分定义为你在这个过程中到达过的 $n$ 个数字总和。

设计一个移动方案使你的得分最大。并输出最大得分。

输入格式

第一行，一个整数 $n$。

接下来的 $n$ 行：第 $i$ 行包含 $i$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,i}$，以空格分隔。

输出格式

输出一个整数，表示最大得分。

样例

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

35

说明/提示

样例 1 解释

最优移动路线如下，方括号 [ ] 标记经过的数字，箭头表示移动方向：

                    [3]
                       ↘
                 5      [2]
                           ↘
             7       1      [6]
                           ↙
         3       2      [8]      4
                           ↘
     2       5       3      [7]      6
                           ↙
 6       3       2      [9]      5       7

最优路径：3 → 2 → 6 → 8 → 7 → 9

最大得分：$3+2+6+8+7+9=\boxed{35}$

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$，$a_{i,j} \le 10$
• 对于 $40\%$ 的数据，$n \le 100$，$a_{i,j} \le 100$
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_{i,j} \le 1000$