不重叠正方形

【题目描述】

有一个N×N的网格，第i行第j列的单元格（1≤i，j≤N）包含整数 Ai，j. 给你一个整数 M.选择三个完全不重叠的M×M的正方形，使得所选正方形中整数的和最大，输出最大值。

【输入格式】

第一行两个整数N，M

接下来N行每行N个整数Ai，j

【输出格式】

【样例1输入】

7 3
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

【样例1输出】

154

【样例说明】

选择如下（加粗斜体）

3 1 4 1 5 9 2

6 5 3 5 8 9 7

9 3 2 3 8 4 6

2 6 4 3 3 8 3

2 7 9 5 0 2 8

8 4 1 9 7 1 6

9 3 9 9 3 7 5

【数据规模与约定】

1≤M≤N/2，0≤Ai,j≤10%^9

对于20%的数据N≤10

对于100%的数据N≤1000

【来源】

atcoder