Елітна нора#7480

Елітна нора

1 секунда

64 мегабайти

Легка

Втомлений від пригод, гобіт Більбо вирішив зайнятися будівництвом нової нори. Пагорб, на якому Більбо планує придбати ділянку, має прямокутну форму і може бути представлений у вигляді таблиці з $n$ рядків і $m$ стовпців (рядки і стовпці нумеруються з одиниці: рядок $1$ — найверхніший, стовпець $1$ — найлівий). Кожна клітинка таблиці відповідає квадратній ділянці розміром $1 \times 1$ 1 \times 1 метр.

Гобіти надають перевагу чітким та простим формам, тому Більбо твердо вирішив придбати ділянку прямокутної форми, зі сторонами, паралельними межам пагорба. Формально, він обирає чотири цілі числа $x_{1}, x_{2}, y_{1}, y_{2} (x_{1} \leq x_{2}, y_{1} \leq y_{2})$ x_1, x_2, y_1, y_2~(x_1 \le x_2, y_1 \le y_2) і купує всі клітинки $(x, y)$ , що задовольняють умови $x_{1} \leq x \leq x_{2}$ x_1 \le x \le x_2 і $y_{1} \leq y \leq y_{2}$ y_1 \le y \le y_2.

Недавні пригоди принесли Більбо стільки золота, що вартість ділянки його майже не турбує. Проте він серйозно переймається своєю репутацією — тому хоче, щоб мінімальна вартість клітинки на обраній ділянці була якомога більшою. Крім того, простір для нього дуже важливий, тому площа ділянки повинна бути не меншою ніж $k$ . Якщо існує декілька ділянок з однаковим значенням мінімальної вартості клітинки, Більбо обере ту, у якої площа максимальна.

Допоможіть гобіту вибрати найвідповіднішу ділянку.

Вхідні дані

У першому рядку містяться три цілі числа $n, m$ і $k (1 \leq n, m \leq 1000$ k~(1 \le n, m \le 1000, $1 \leq k \leq n \cdot m)$ 1 \le k \le n \cdot m) — кількість рядків, кількість стовпців і мінімально допустима площа ділянки відповідно.

Наступні $n$ рядків містять по $m$ цілих чисел — вартості клітинок. Число у $j$ -й позиції $i$ -го рядка відповідає вартості клітинки з координатами $(i, j)$ . Усі вартості — цілі числа від $1$ до $1 0^{9}$ 10^9 включно.

Вихідні дані

Виведіть два цілі числа:

максимально можливу мінімальну вартість клітинки на ділянці,
максимально можливу площу такої ділянки (серед усіх ділянок, у яких мінімальна вартість клітинки збігається з максимально можливою).

Приклади

Приклад 1

Приклад 2

Приклад 3