暂无测试数据。

描述

给出一个底和高为n个数的三角形，求出从最上点到下方某一点的和最长的路径。

格式

输入

第一行，一个数n。

其后n行，第i行有i个数，表示这个数字三角形。

输出

从最上点到下方某一点的和最长的路径的和。

样例#1

输入样例#1

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

输出样例#1

30

限制

1s, 1024KiB for each test case.