eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Элитная нора

Элитная нора

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Устав от приключений, хоббит Бильбо решил заняться строительством новой норы. Холм, на котором Бильбо планирует купить себе участок, имеет прямоугольную форму, и его можно представить в виде таблицы из n строк и m столбцов (строки и столбцы нумеруются с единицы, номер 1 имеют самая верхняя строка и самый левый столбец). Каждая клетка таблицы соответствует квадратному участку размером 1 на 1 метр. Хоббиты любят четкие и простые формы, поэтому Бильбо твердо намерен купить себе участок прямоугольной формы, со сторонами параллельными границам холма. Строго говоря он выбирает четыре числа x[1], x[2], y[1], y[2] (x[1]x[2], y[1]y[2]) и покупает все клетки (x, y), такие что (x[1]xx[2]) and (y[1]yy[2]).

Недавние приключения принесли Бильбо столько золота, что цена участков его не очень волнует, но при этом он сильно печется о своей репутации, поэтому он хочет, чтобы цена самой дешевой клетки, которую он купит, была как можно больше. Вместе с тем, нашему хоббиту крайне важен простор, поэтому площадь участка должна быть больше, либо равна k. Если существуют несколько участков с равной минимальной стоимостью клетки, Бильбо предпочтет тот, площадь которого больше.

Помогите Хоббиту выбрать наиболее подходящий для него участок.

Входные данные

В первой строке записаны три числа n, m и k, разделенные ровно одним пробелом - количество строк, количество столбцов и минимальная площадь участка, на которую согласен Бильбо, соответственно. Следующие n строк содержат по m чисел каждая - стоимости клеток соответствующей строки таблицы. Таким образом, число стоящее на месте j в строке i + 1, соответствует клетке с индексом (i, j). n и m натуральные и не превосходят 1000, k натуральное и не превосходит размера таблицы, все стоимости находятся в диапазоне от 1 до 10^9 включительно.

Выходные данные

В качестве ответа выведите два числа: сначала максимально возможную минимальную стоимость клетки участка, затем максимально возможную площадь такого участка.

Пример

Входные данные #1
3 3 3
1 1 1
1 2 2
1 2 2
Выходные данные #1
2 4
Входные данные #2
1 10 5
4 3 2 5 10 7 6 5 1 100
Выходные данные #2
5 5
Входные данные #3
3 5 2
5 7 5 5 5
8 5 5 7 5
8 5 8 8 8
Выходные данные #3
8 3
Источник 2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января