CF173C Spiral Maximum

我们考虑一个 $k×k$ 的正方形，被划分成 $1×1$ 的小方格。请注意，$k \geq 3$ 且为奇数。我们将按如下顺序涂色：从左上角方格开始，首先向右移动，然后向下，再向左、向上，然后再次向右，依此类推。若满足以下任一条件，将结束当前方向的移动：一是已经到达方格的边界，二是下一个方格之后的方格已经被涂色。若无法继续向任何方向移动并进行涂色，则结束涂色过程。由被涂色方格构成的图形称为螺旋线。  上图给出了 $k=3,5,7,9$ 下螺旋线的例子。 现在有一个 $n×m$ 的表格，每个单元格中包含一个数字。我们考虑由该表格单元格构成的所有可能的螺旋线，也就是说，考虑所有不超出表格边界的任意大小的螺旋线。我们求出所有螺旋线所覆盖单元格数字之和，并找到这些和中的最大值。

第一行包含两个整数 $n$ 和 $m$（$3 \leq n,m \leq 500$），表示表格的大小。 接下来的 $n$ 行，每行包含 $m$ 个用空格分隔的整数，第 $i$ 行的第 $j$ 个数字 $a_{ij}$（$-1000 \leq a_{ij} \leq 1000$）表示表格第 $i$ 行第 $j$ 列的数字。

输出一个整数，表示所有螺旋线中单元格数字之和的最大值。

在第一个样例中，最大和的螺旋线将覆盖表格中所有的 $1$。 在第二个样例中，螺旋线最多只能覆盖 $6$ 个 $1$。 由 ChatGPT 5 翻译