Description
给定 <math xmlns="http://www.w3.org/1998/Math/MathML">n×n 个整数组成一个方阵 <math xmlns="http://www.w3.org/1998/Math/MathML">ai,j，请找一个 <math xmlns="http://www.w3.org/1998/Math/MathML">k×k 的子方阵，使得子方阵内的数字之和达到最大，输出这个最大值。
Input Format
-
第一行：两个整数 n 与 <math xmlns="http://www.w3.org/1998/Math/MathML">k
-
第二行到第 <math xmlns="http://www.w3.org/1998/Math/MathML">n+1 行：每行 <math xmlns="http://www.w3.org/1998/Math/MathML">n 个整数表示 <math xmlns="http://www.w3.org/1998/Math/MathML">ai,j
输入的数据量很大，请使用scanf方式读入
Output Format
单个整数：表示最大的 <math xmlns="http://www.w3.org/1998/Math/MathML">k×k 的子方阵的数字之和。
3 2
1 2 3
3 1 2
0 2 4
9
Hint
数据范围
-
<math xmlns="http://www.w3.org/1998/Math/MathML">30% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤k≤n≤30
-
<math xmlns="http://www.w3.org/1998/Math/MathML">60% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤k≤n≤300
-
<math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤k≤n≤2500
-
<math xmlns="http://www.w3.org/1998/Math/MathML">0≤ai,j≤1,000,000
Source
上海市2023年5月 动态规划 前缀和
