题目描述

给定一个数字三角形，从顶部出发，每一步只能走到下一层的正下方或右下方，最终到达最底层。

请计算所有路径中，经过数字的最大总和。

输入格式

第一行整数h，表示三角形高度。接下来h行，第i行包含i个整数。

输出格式

输出最佳路径上数字的总和。

样例

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

30

数据范围

1≤h≤100；各数字为0至10000的整数。