当前没有测试数据。

矩阵求和

题目描述

有一个 $N×M$ 的矩阵（ $M$ 一定是奇数），矩阵的第 $i$ 行第 $j$ 列有整数 $A_{ij}$。

在矩阵中任意的位置，只能沿着如下图所示的 $5$ 个方向向上移动（不能出矩阵的边界）。

请编程计算出，从矩阵最后一行最中间位置的正下方开始，按照上述移动规则移动到矩阵的第 $1$ 行，经过数字和的最大值是多少？

比如，有如下图所示的矩阵，从标记为 $H$ 的位置（最后一行最中间位置的正下方）出发，沿红色箭头所示的方向，经过的数字和最大。

输入

第 $1$ 行有 $2$ 个整数 $N$ 和 $M$。

接下来 $N$ 行，每行有 $M$ 个整数，用空格隔开。

输出

输出经过数字和的最大值。

样例

输入复制

6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2

输出复制

51

说明

数据范围

对于 $100$% 的数据，$1≤N,M≤200$，$−10^{5}≤A_{ij}≤10^{5}$，测试数据确保答案在$[−10^{9},10^{9}]$ 的范围内。