11006 - 爬山

“爬山吧，少年！”挑战活动主办方在X山设置了如下线路，人们可以从山脚不同入口上山。

为了鼓励人们运动，主办方安排人员，在山路的每个路口发礼品。当然，因为每个路口的礼品可能不一样，其价值也不等。

鑫鑫特别想参加这个活动，他通过特殊的信息技术提前获取了各个礼品发放点相应礼品的价值。现在他想知道，如果爬到山顶，他能领取到的礼品总的价值最大是多少？

举例，如果山路情况如下，那么鑫鑫能获得的最大价值就是24.

第一行一个整数 n，表示从山顶到山脚每条路线均有n个路口。

接下来 n 行数据。第 i(1\le i \le n) 行，每行有 i 个整数，表示相应的路口，发放的礼品价值。

输出一个整数，表示答案。

数据范围

1 \le n \le 1000