3176 Cow Bowling

原文

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

問題

Cow Bowling
パスカルの三角形と同じ配置で数字が配置されている。
三角形の上からスタートして右下左下と選択しながら一段ずつ段を下りていく。
一番下の段まで到達したとき、途中通ったルートにある数字の合計が最大になるルートを通ることにする。
この時の最大値を計算せよ。
段数は350段まで、数字は全て0以上の自然数である。
数列の例

         7

       3   8

     8   1   0

   2   7   4   4

 4   5   2   6   5

Hint
例は7 3 8 7 5の順に移動すると合計30で最大のルートとなる。

入力は最初の行に段数、以下三角形の数字が一段ずつ与えられる。

入力の例

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

出力の例

30

出典

USACO 2005 December Bronze