题目描述

一块土地被划分为 $M$ 行 $N$ 列的网格，每个格子都有一个非负整数商业价值。

现在需要在网格中选择三个互不重叠的正方形区域，每个区域都恰好包含 $K$ 行 $K$ 列。两个区域不能包含同一个格子。一个区域的商业价值等于其中所有格子的商业价值之和。

请计算三个区域的商业价值总和的最大值。

输入格式

第一行包含三个整数 $M,N,K$，分别表示网格的行数、列数和每个正方形区域的边长。

接下来 $M$ 行，每行包含 $N$ 个非负整数，表示各格子的商业价值。

输出格式

输出一个整数，表示三个区域的最大商业价值总和。

样例

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

208

5 5 2
1 2 3 4 5
16 17 18 19 20
11 12 13 14 15
6 7 8 9 10
21 22 23 24 25

196

数据范围与提示

• $1 \le K \le M,N \le 1500$。
• 每个格子的商业价值不超过 $500$。
• 保证网格中至少能够放置三个互不重叠的 $K\times K$ 正方形区域。
• 对于 $30\%$ 的数据，$M,N \le 12$。