说明

每个点可以向下和右下两个方向移动 问从左上角走到最后一行的最大和

输入格式

第一行一个整数N(<=1000)，表示三角形总共有几行 第二至第N+1行，给出这个数字三角形

输出格式

一个整数，表示一路上所有数的最大和，结果不会超过int64

样例

4
1
3 2
4 10 1
4 3 2 20

24