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

Обмеження: 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.