题目描述

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$ 以下の最大の整数を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

$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}$

输出格式

答えを出力せよ。

题目大意

题目大意

给定一个 $n\times n$ 的矩阵 $A$，再给定一个数 $k$，求矩阵中所有大小为 $k\times k$ 的子矩阵的中位数的最小值。

一个 $k\times k$ 的矩阵的中位数被定义为将矩阵中的所有数从大到小排序后的第 $\lfloor\frac{k^2}{2}\rfloor+1$ 个数。

输入格式

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

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

输出格式

输出一行一个数，表示中位数的最小值。

说明/提示

$1\le k\le n\le 800,0\le A_{i,j}\le 10^9$。

Translated by _Ponder_

3 2
1 7 0
5 8 11
10 4 2

4

3 3
1 2 3
4 5 6
7 8 9

5

提示

制約

• $1\ \leq\ K\ \leq\ N\ \leq\ 800$
• $0\ \leq\ A_{i,j}\ \leq\ 10^9$
• 入力は全て整数である。

Sample Explanation 1

北から $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$ を出力します。