[[原文:http://poj.org/problem?id=3176]]
----
''時間制限'':1000ミリ秒
''メモリ制限'':65536KB
&br;

*問題 [#ua5a176c]
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で最大のルートとなる。

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



*入力の例 [#m5eae7ff]
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

*出力の例 [#r8be8846]
30

*出典 [#p8da5a11]
USACO 2005 December Bronze