题目描述

城市中有一个长宽为 $n \times n$ 的绿化带，每个格子种了一棵树，树的高度是 $A_{i,j}$ ，维护员想在绿化带中框出一片 $k \times k$ 的范围，他是一个熟悉中庸之道的人，对于框出来的区域，他会使用这片 $k \times k$ 区域中树高为区域高度中位数的树当作代表树，根据不同的选择，可以框出不同的 $k \times k$ 范围，他很好奇，在所有的选择中，代表树最矮的树是多少。

一个 $k\times k$ 的区域的区域高度中位数被定义为，将范围内所有的数从大到小排序后的第 $\lfloor\frac{k^2}{2}\rfloor+1$ 个数。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行，每行 $n$ 个数，描述了一个矩阵。

输出格式

输出一行一个数，表示代表树的最小值。

样例 #1

样例输入 #1

3 2
1 7 0
5 8 11
10 4 2

样例输出 #1

4

样例1解释：

矩阵大小为3×3，k=2，所以有4个2×2的子矩阵。

子矩阵及其排序后的元素和中位数：

左上角子矩阵$\begin{bmatrix} 1&7\\ 5&8\\ \end{bmatrix}$→ 排序后[8,7,5,1] → 第⌊4/2⌋+1=3个数是5。

右上角子矩阵$\begin{bmatrix} 7&0\\ 8&11\\ \end{bmatrix}$ → 排序后[11,8,7,0] → 第3个数是7。

左下角子矩阵$\begin{bmatrix} 5&8\\ 10&4\\ \end{bmatrix}$ → 排序后[10,8,5,4] → 第3个数是5。

右下角子矩阵$\begin{bmatrix} 8&11\\ 4&2\\ \end{bmatrix}$ → 排序后[11,8,4,2] → 第3个数是4。

所有中位数为5,7,5,4，最小值为4。

样例 #2

样例输入 #2

3 3
1 2 3
4 5 6
7 8 9

样例输出 #2

5

数据范围

对于 $100\%$ 的数据， $1\le k\le n\le 800,0\le A_{i,j}\le 10^9$。