#46. 方格取数

方格取数

样例下载

【题目描述】

有一个 N×MN × M 的方格图,每个方格中填有一个非负整数。

小明要从中选取三个 L×LL × L 的正方形区域,将其中所有的数全部取走。选取的三个区域不能有重叠。

问:他该如何选取,可以使得取走的数之和为最大。你只需要输出这个最大值。

【输入格式】

第一行:三个整数 N,M,LN, M, L

接下来是一个 N×MN × M 的非负整数矩阵 AA

【输出格式】

一行,一个正整数,表示可以取得的数之和的最大值。

【样例输入】

3 6 2
1 0 1 0 1 1 
0 1 0 1 1 1
1 2 3 4 0 0

【样例输出】

16

【数据范围】

40% 的数据:N,M≤20。N, M ≤ 20。

100% 的数据:N,M≤2000,0≤Aij≤1000N, M ≤ 2000,0 ≤ Aij ≤ 1000,数据保证存在满足条件的三个正方形区域。