2258: enhanced triangle

小杨做了初级 dp 后，觉得数字三角形太简单，所以加强了一下。

蜗牛小笨(BEN)遇到一个类似这样的迷宫：

1

1 2

2 1 1

这个迷宫是一个等腰直角三角形，每个点上都有一个数字，蜗牛有一次使用魔法的机会。

蜗牛行进的方式：

1、行走：蜗牛进行行走，可以走到下一行、同一列或者下一行、右边一列。

2、魔法：只能使用一次，可以从第 x 行飞到第 x + 1 行的任意一列。

要求：蜗牛所经之路的数字和最大。

第 1 行是一个数n，代表这个三角形的腰的长度。

第 2 行到第n+ 1行中，第m行有m − 1 个数，代表这些数字。（1≤各数字≤2¹⁶− 1）；

输出共一行一个整数：最大的数字和。

3 
1 
1 2 
2 1 1

5

对于 100%的数据：1 ≤ n ≤ 1,000；1 ≤ a[i][j] ≤ 2¹⁶ − 1。