CF173C.Spiral Maximum

Let's consider a k × k square, divided into unit squares. Please note that k ≥ 3 and is odd. We'll paint squares starting from the upper left square in the following order: first we move to the right, then down, then to the left, then up, then to the right again and so on. We finish moving in some direction in one of two cases: either we've reached the square's border or the square following after the next square is already painted. We finish painting at the moment when we cannot move in any direction and paint a square. The figure that consists of the painted squares is a spiral.

The figure shows examples of spirals for k = 3, 5, 7, 9.

You have an n × m table, each of its cells contains a number. Let's consider all possible spirals, formed by the table cells. It means that we consider all spirals of any size that don't go beyond the borders of the table. Let's find the sum of the numbers of the cells that form the spiral. You have to find the maximum of those values among all spirals.

我们考虑一个 $k \times k$ 的正方形，它被划分为若干个单位正方形。请注意：$k \geq 3$ 且为奇数。我们将从左上角的单位正方形开始依次涂色，涂色顺序如下：先向右、再向下、再向左、再向上、再向右……如此循环。在某一方向上的移动会在以下两种情况之一发生时停止：要么已到达正方形的边界，要么“下一个单位正方形之后的那个单位正方形”已被涂色（即该方向上连续两个未涂色格子之后紧邻的是已涂色格子）。当我们在任意方向上都无法继续移动并涂色时，涂色过程结束。所有被涂色的单位正方形所构成的图形称为螺旋形。

图中展示了 $k = 3,\,5,\,7,\,9$ 时对应的螺旋形示例。

现给定一个 $n \times m$ 的表格，其中每个单元格内含一个数字。我们考虑该表格中所有可能形成的螺旋形——即所有尺寸的螺旋形，只要其完全位于表格边界之内即可。对每一个这样的螺旋形，计算其所覆盖的所有单元格中的数字之和。你需要在所有可能的螺旋形中，找出该和的最大值。

The first line contains two integers n and m (3 ≤ n, m ≤ 500) — the sizes of the table.

Each of the next n lines contains m space-separated integers: the j-th number in the i-th line a__ij ( - 1000 ≤ a__ij ≤ 1000) is the number recorded in the j-th cell of the i-th row of the table.

第一行包含两个整数 $n$ 和 $m$（$3 \leq n, m \leq 500$）—— 表格的尺寸。

接下来的 $n$ 行中，每行包含 $m$ 个用空格分隔的整数：第 $i$ 行中的第 $j$ 个数 $a_{ij}$（$-1000 \leq a_{ij} \leq 1000$）表示表格第 $i$ 行第 $j$ 列单元格中记录的数值。

Print a single number — the maximum sum of numbers among all spirals.

输出一个数字——所有螺旋形中数字之和的最大值。

In the first sample the spiral with maximum sum will cover all 1's of the table.

In the second sample the spiral may cover only six 1's.

在第一个样例中，和最大的螺旋将覆盖表格中的所有 1。

在第二个样例中，螺旋最多只能覆盖六个 1。