11006 - 爬山

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

图片1.png

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

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

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

Input

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

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

Output

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

Examples

Input

4
1
3 2
4 10 1
4 3 2 20

Output

24

Hint

数据范围

1 \le n \le 1000

Time Limit 1000 毫秒
Memory Limit 128 MB
Stats
上一题 下一题