The Shortest Path on A Rhombic Path

Time Limit : 1 sec, Memory Limit : 65536 KB

最短経路


図1に例示するように整数(0 以上 99 以下)をひしがたに並べます。このような、ひしがたを表すデータを読み込んで、一番上からスタートして一番下まで次のルールに従って進むとき、通過する整数の和の最大値を出力するプログラムを作成してください。

  • 各ステップで、対角線上の左下か対角線上の右下に進むことができます。

例えば図1の例では、図2に示すように、7,3,8,7,5,7,8,3,7を選んで通ったとき、その和は最大の 55 (7+3+8+7+5+7+8+3+7=55) となります。

Input

入力例に示すように、カンマで区切られた整数の並びが、ひし形状に与えられます。各行に空白文字は含まれません。入力例は図1に対応しています。 データの行数は 100 行未満です。

Output

ルールに従って通過する整数の和の最大値を1行に出力します。

Sample Input

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

Sample Output

55

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
http://www.pref.fukushima.jp/pc-concours/