Прямокутна ковзанка

Обмеження: 3 сек., 256 МіБ

Наступного дня Зеник з Марічкою вирішили покататися на ковзанах.

На курорті є прямокутна ковзанка розміру $n \times m$. Кожна з $n \times m$ ділянок ковзанки має свій рівень небезпеки $d_{i j}$.

Ковзанка дуже велика, тому пара не хоче їздити по всій її площі, а тільки вибрати собі квадрат розміру $k \times k$ зі сторонами паралельними до сторін ковзанки і кататися на ньому.

Рівень небезпеки квадрата — це максимальний рівень небезпеки серед усіх ділянок, що йому належать.

Марічка просить вас дізнатися, який мінімальний рівень небезпеки може мати квадрат $k \times k$.

Вхідні дані

У першому рядку задано три цілих числа $n$, $m$ та $k$ — розміри ковзанки та квадрата. У наступних $n$ рядках задано по $m$ цілих чисел $d_{i j}$ — рівень небезпеки на відповідній ділянці ковзанки.

Вихідні дані

У єдиному рядку виведіть ціле число — мінімальний рівень небезпеки квадрата $k \times k$.

Обмеження

$1 \le n, m \le 1500$, $1 \le k \le min\{n, m\}$,

$1 \le d_{i j} \le 10^9$.

10 балів: $n, m \le 100$;

10 балів: $n, m \le 700$;

5 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 3 2 2 5 4 4 1 3 3 2 1	3

Примітки

У прикладі можливі такі способи вибрати квадрат $2 \times 2$:

• $\begin{matrix} 2 & 5 \\ 4 & 1 \end{matrix}$ з рівнем небезпеки 5,

• $\begin{matrix} 5 & 4 \\ 1 & 3 \end{matrix}$ з рівнем небезпеки 5,

• $\begin{matrix} 4 & 1 \\ 3 & 2 \end{matrix}$ з рівнем небезпеки 4,

• $\begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix}$ з рівнем небезпеки 3.