Background

有一个如三角形的n行数字金字塔，数塔上有若干数字。问从数塔的最高点到底部，在所有的路径中，经过的数字的和最大为多少？

如上图，是一个5行的数塔，其中7—3—8—7—5的路径经过数字和最大，为30。

Input

第一行为一个大于0的整数n，代表数塔的高度（n<100） 接下来n行，代表数塔中的数字

Output

输出从数塔的最高点到底部，在所有的路径中，经过的数字的最大和

Samples

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

30