让我们考虑一个 k × k 的正方形,分为单位正方形。请注意 k ≥ 3 并且为奇数。我们将从左上角的方块开始按以下顺序绘制方块:首先向右移动,然后向下,然后向左,然后向上,然后再次向右,依此类推。在以下两种情况之一中,我们完成了向某个方向的移动:要么我们已经到达了正方形的边界,要么已经到达了下一个正方形之后的下一个正方形。当我们无法向任何方向移动的时候,我们就完成了绘画,画了一个正方形。由所画的正方形组成的图形是一个螺旋线。
该图显示了 k = 3, 5, 7, 9 的螺旋示例。
你有一个 n × m 的表,它的每个单元格都包含一个数字。让我们考虑由表格单元格形成的所有可能的螺旋。这意味着我们考虑所有不超出表格边界的任何尺寸的螺旋。让我们求出形成螺旋的细胞数的总和。您必须找到所有螺旋中这些值的最大值。
输入
第一行包含两个整数 n 和 m (3 ≤ n, m ≤ 500) — 表的大小。
接下来的 n 行每行包含 m 个空格分隔的整数:第 i 行中的第 j 个数字 aij (- 1000 ≤ aij ≤ 1000) 是表格第 i 行第 j 个单元格中记录的数字。
输出
打印单个数字 — 所有螺旋中数字的最大总和。
示例
输入 #1
6 5 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1
输出 #1
17
输入 #2
3 3 1 1 1 1 0 0 1 1 1
输出 #2
6
输入 #3
6 6 -3 2 0 1 5 -1 4 -1 2 -3 0 1 -5 1 2 4 1 -2 0 -2 1 3 -1 2 3 1 4 -3 -2 0 -1 2 -1 3 1 2
输出 #3
13
注意
在第一个示例中,具有最大和的螺旋将覆盖表中的所有 1。
在第二个示例中,螺旋可能仅覆盖六个 1。