题目描述

给你一个$N*N$大小的正方形二维数组$a$，请你找出从顶部任意处到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以走到右下方的点，即从$a_{i,j}$可以走到$a_{(i+1),(j-1)}$或$a_{(i+1),(j+1)}$。

输入格式

第一行包含一个整数$N$，表示数组的大小。

接下来的$N$行，每行包含$N$个以空格分隔的整数$a_{i,j}$，表示数组$a$中的元素大小。

输出格式

输出为一个整数，表示从顶部任意处到底部任意处可以得到的最大的和。

3
1 2 3
4 5 6
7 8 9

17

提示

【样例解释】

最大的和为$3+5+9=17$。

【数据范围】.

对于所有数据，保证：$1\leq N \leq 10^3,1\leq a_{i,j}\leq 100$。