该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的矩阵

题目描述

徐老师给定一个 $N\times N$ 的整数网格。你要选择一个连续的 $K\times K$ 子矩阵。

把子矩阵中的 $K^2$ 个数按非递增顺序排列，第 $\lfloor K^2/2\rfloor+1$ 个数称为这个子矩阵的中位数。编号从 $1$ 开始。

请在所有连续 $K\times K$ 子矩阵中，求中位数的最大值。

输入格式

第一行输入两个整数 $N$ 和 $K$。

接下来 $N$ 行，每行输入 $N$ 个整数。第 $i$ 行第 $j$ 个整数记为 $A(i,j)$。

• $1 \le K \le N \le 800$
• $0 \le A(i,j) \le 10^9$

输出格式

输出一个整数，表示所有 $K\times K$ 子矩阵中最大的中位数。

输入输出样例 #1

输入 #1

2 1
1 2
3 4

输出 #1

4

输入输出样例 #2

输入 #2

3 2
1 7 3
4 2 8
6 5 9

输出 #2

5

说明/提示

样例 1 中，每个 $1\times1$ 子矩阵的中位数就是其中唯一的数，最大值为 $4$。

样例 2 的右下角 $2\times2$ 子矩阵包含 $2,8,5,9$，按非递增顺序排列后是 $9,8,5,2$，按题目定义中位数为 $5$。其他子矩阵的中位数都不超过 $5$。