題目描述

給定一個由正整數組成的三角形，如下所示：

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

從頂點出發，每次可以向左下或右下走一步，直到到達底邊。求出經過的數字之和的最大值。

輸入格式

第一行包含一個正整數n，表示三角形的高度。接下來n行，每行包含i個正整數，表示第i行的數字。數字之間用空格隔開。

限制條件：1 <= n <= 100，1 <= 數字 <= 99

輸出格式

輸出一個正整數，表示經過的數字之和的最大值。

Samples

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

30

提示

動態規劃

原始資料

• Zero1 題號：b038
• Hydro 題號：Z1038
• Locale：zh_TW
• Display：open