题目描述

给出一个$N \times N$的矩阵,然后依次枚举$k \times k$的子矩阵。

对于$k \times k$的子矩阵，一共有个$k^2$元素，找出其中的中位数。这里的中位数是子矩阵中元素从大到小排列的第$\left \lfloor \frac{k^2}{2} \right \rfloor$个元素。

问对于所有子矩阵的中位数中，最小的那个中位数是多少。

样例

样例输入1

3 2
1 7 0
5 8 11
10 4 2

样例输入2

3 3
1 2 3
4 5 6
7 8 9

样例输出1

4

样例输出2

5

数据范围与提示

$1\le k\le N\le 800$

$0 \le a_{i,j} \le 10^9$

保证输入全是整数

原码