配点 : $400$ 点

問題文

AtCoder 公園の敷地は東西南北に広がる $N\times N$ のマス目からなっており、北から $i$ 番目かつ西から $j$ 番目のマスの高さは $A_{i,j}$ で与えられます。

公園の管理者である高橋君はここに $K \times K$ の区画の池を作る事にしました。

池を作るにあたって、高橋君は AtCoder 公園の敷地内に完全に含まれる $K \times K$ の区画であってその区画に含まれるマスの高さの中央値が最も低いようなものを選ぼうと考えました。そのような区画のマスの高さの中央値を求めてください。

ここで、 $K \times K$ の区画に含まれるマスの高さの中央値とはその区画に含まれる $K^2$ 個のマスのうち $\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}$

出力

答えを出力せよ。

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)\}$ の $4$ つです。 $K=2$ のとき、各区画に含まれるマスの高さの中央値は各区画に含まれるマスのうち $\left\lfloor\frac{2^2}{2}\right\rfloor+1=3$ 番目に高いマスの高さとなるので、それぞれの区画の中央値は $5$, $7$, $5$, $4$ であり、このうち最小である $4$ を出力します。

3 3
1 2 3
4 5 6
7 8 9

5