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

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

Input

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

Output

輸出數(shù)據(jù)只有一個(gè)整數(shù)，表示計(jì)算出的最大值。

Example Input

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Example Output

30