池塘

题目描述

AtCoder 公园的土地是一个 $N \times N$ 的网格,行按东西方向、列按南北方向排列。从北边数第 $i$ 行、从西边数第 $j$ 列的格子的高度为 $A_{i,j}$。

管理员高桥君决定在公园里建一个占据 $K \times K$ 个格子的正方形池塘。

为此,他想在公园内选择一个完全位于公园内的 $K \times K$ 正方形区域,使得该区域内格子高度的中位数最小。求这样的区域中格子高度的中位数。

这里,一个 $K \times K$ 区域内格子高度的中位数,定义为该区域内 $K^2$ 个格子中第 $\left\lfloor \frac{K^2}{2} \right\rfloor + 1$ 高的格子的高度,其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

3 2
1 7 0
5 8 11
10 4 2

4

用 $(i,j)$ 表示从北边数第 $i$ 行、从西边数第 $j$ 列的格子。 池塘可能占据的 $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$。

3 3
1 2 3
4 5 6
7 8 9

5

数据范围

• $1 \le K \le N \le 800$
• $0 \le A_{i,j} \le 10^9$
• 输入均为整数