AT_abc347_f [ABC347F] Non-overlapping Squares

有一个 $N\times N$ 的网格，在第 $i$ 行第 $j$ 列（$1\leq i,j\leq N$）的格子上写有整数 $A_{i,j}$。 给定整数 $M$。请从网格中选择 $3$ 个互不重叠的 $M\times M$ 的子矩阵，使得所选子矩阵内所有整数之和的最大值尽可能大。 **问题的严格定义** 当整数 $6$ 元组 $(i_1, j_1, i_2, j_2, i_3, j_3)$ 满足以下 $3$ 个条件时，称其为“好 $6$ 元组”： - $1\leq i_k\leq N-M+1\ (k=1,2,3)$ - $1\leq j_k\leq N-M+1\ (k=1,2,3)$ - 对于 $k\neq l\ (k,l\in\{1,2,3\})$，集合 $\{(i,j)\mid i_k\leq i

输入以如下格式从标准输入读入： > $N$ $M$ > $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$ > $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,N}$ > $\vdots$ > $A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$

请输出答案。

### 数据范围 - $2\leq N\leq 1000$ - $1\leq M\leq N/2$ - $0\leq A_{i,j}\leq 10^9$ - 输入均为整数 ### 样例解释 1 从给定的网格中，选择如下图所示的 $3\times3$ 的子矩阵 $3$ 个（对应 $(i_1, j_1, i_2, j_2, i_3, j_3)=(1,5,2,1,5,2)$），所选格子内的数之和为 $154$。  不存在满足题意且和大于等于 $155$ 的选法，因此输出 $154$。 ### 样例解释 2 如下图所示的选法最优。  ### 样例解释 3 如下图所示的选法最优。  由 ChatGPT 4.1 翻译