最大绿地方块

故事背景

城市规划部门将城市划分为网格，每个格子有绿化分值。为了新建一处公园，他们希望选择一个 k×k 的方形区域，使得总绿化分值最大。

题目描述

给定一个 n×m 的整数矩阵 a 和一个正整数 k（1 ≤ k ≤ min(n,m)）。请你找出所有 k×k 子矩形中元素和的最大值，并输出该最大值。

输入格式

• 第一行包含三个整数 n、m、k。
• 接下来 n 行，每行 m 个整数，表示矩阵 a。

输出格式

输出一行，一个整数，表示所有 k×k 子矩形的最大元素和。

输入输出样例 #1

输入 #1

3 4 2
1 2 3 4
5 6 7 8
9 10 11 12

输出 #1

38

样例解释 #1

所有 2×2 子矩形中，右下角的子矩形 {7,8;11,12} 和最大，和为 7+8+11+12=38。

说明/提示

• 数据范围示例：1 ≤ n,m ≤ 1000；-10^9 ≤ a[i][j] ≤ 10^9。
• 提示：先构建二维前缀和，再枚举每个 k×k 的右下角坐标，用 O(1) 求其和，整体 O(nm)。