题目描述

一个公园的土地是一个 $N\\times N$ 的网格，有东西方向的行和南北方向的列。从北部和西部计算，第 $i$ 行、第 $j$ 列的正方形的高度为 $A_{i,j}$。

管理者 Takahashi 打算在公园内建造一个占据 $K \\times K$ 个方格的正方形池塘。

为了实现这个目标，在公园内选择一个完全包含在公园内的 $K \\times K$ 方格的正方形区域，使得其中方格的中位数是最低的。找出这样一个区域中方格的高度的中位数。

这里，方格的中位数是指区域中 $K \\times K$ 个方格中第 $(\\left\\lfloor\\frac{K^2}{2}\\right\\rfloor +1)$ 个高度最高的方格的高度，其中 $\\lfloor x\\rfloor$ 表示不超过 $x$ 的最大整数。

约束条件

• $1 \\leq K \\leq N \\leq 800$
• $0 \\leq A_{i,j} \\leq 10^9$
• 输入的所有值均为整数。

输入

输入采用以下格式从标准输入给出：

$N$ $K$ $A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,N}$ $A_{2,1}$ $A_{2,2}$ $\\ldots$ $A_{2,N}$ $:$ $A_{N,1}$ $A_{N,2}$ $\\ldots$ $A_{N,N}$

输出

输出答案。

示例输入1

3 2
1 7 0
5 8 11
10 4 2

示例输出1

4

我们有四个候选的 $2 \\times 2$ 区域用于池塘：$\\{(1,1),(1,2),(2,1),(2,2)\\}, \\{(1,2),(1,3),(2,2),(2,3)\\}, \\{(2,1),(2,2),(3,1),(3,2)\\}, \\{(2,2),(2,3),(3,2),(3,3)\\}$。
当 $K=2$ 时，因为 $\\left\\lfloor\\frac{2^2}{2}\\right\\rfloor+1=3$，方格区域中方格高度的中位数是第 $3$ 个最高的方格的高度，分别是以上候选中的 $5$、$7$、$5$、$4$。我们应该输出最低的那个：$4$。

示例输入2

3 3
1 2 3
4 5 6
7 8 9

示例输出2

5