1163 The Triangle

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

問題

パスカルの三角形と同じ配置で数字がｎ行与えられる。
三角形を上から下へ辿り、下へ行くたびに右の数字左の数字とルートを選んでいきルート上にある数を合計する。
数字の合計値が最も大きくなるルートをとった時の合計値を求めよ。
三角形の段数は100まで、三角形内の数字は0以上の整数であり答えはintに収まる。

入力

一行目に三角形の段数を表す数字Nが与えられる。
２行目からは各段の数字が与えられる。

出力

最大となるルートをとった時の合計値を一行に出力せよ。

入力の例

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

出力の例

30

出典

JOI1994