给定一个 n \times n 的矩阵 a,在该矩阵中找到一个 k \times k 的子矩阵,使该子矩阵所有元素的中位数(也就是第 \left\lfloor\frac{k^2}{2}\right\rfloor +1 大的元素的值)在所有 k \times k 子矩阵中最小。输出该中位数的值。
输入
第一行两个整数 n,k \ (1 \leq k \leq n \leq 800)。
接下来 n 行每行 n 个整数,表示矩阵 a \ (0 \leq a_{i,j} \leq 10^9)。
输出
输出一个整数,表示答案。
样例
标准输入 复制文本 |
3 2 1 7 0 5 8 11 10 4 2 |
标准输出 复制文本 |
4 |
提示
有四个 k \times k(也就是 2 \times 2)的子矩阵,这四个子矩阵的中位数(也就是第 \left\lfloor\frac{2^2}{2}\right\rfloor +1=3 大的元素)分别是 5,7,5,4,所以最小值为 4。