三角形谜题

在一个古老的人类遗迹里面，发现一个神殿，只有解决了神殿大门上的三角形谜题才能进入，有一个数字组成的三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？（下图为n=5时的情况)

输入格式

第1行：整数n(1≤n≤1000) 第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。

输出格式

一行：一个整数，表示所经过数字的最大和。

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

30

数据范围

时间限制: 1000ms

内存限制: 256MB