题目描述

给定 $n\times n$ 个整数组成一个方阵 $a_{i,j}$，请找一个 $k\times k$ 的子方阵，使得子方阵内的数字之和达到最大，输出这个最大值。

输入格式

• 第一行：两个整数 $n$ 与 $k$
• 第二行到第 $n+1$ 行：每行 $n$ 个整数表示 $a_{i,j}$

输出格式

单个整数：表示最大的 $k\times k$ 的子方阵的数字之和。

数据范围

• $30\%$ 的数据，$1\leq k\leq n\leq 30$
• $60\%$ 的数据，$1\leq k\leq n\leq 300$
• $100\%$ 的数据，$1\leq k\leq n\leq 2500$
• $0\leq a_{i,j}\leq 1,000,000$

样例数据

输入:

3 2
1 2 3
3 1 2
0 2 4

输出:

9

说明:

右下角最大