數字三角形問題 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic PRoblem Description

給定一個由n行數字組成的數字三角形如下圖所示。試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。 對于給定的由n行數字組成的數字三角形，計算從三角形的頂至底的路徑經過的數字和的最大值。

Input

輸入數據的第1行是數字三角形的行數n，1≤n≤100。接下來n行是數字三角形各行中的數字。所有數字在0..99之間。

Output

輸出數據只有一個整數，表示計算出的最大值。

Example Input

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Example Output

30