Элитная нора
Элитная нора
Устав от приключений, хоббит Бильбо решил заняться строительством новой норы. Холм, на котором Бильбо планирует купить себе участок, имеет прямоугольную форму, и его можно представить в виде таблицы из n строк и m столбцов (строки и столбцы нумеруются с единицы, номер 1 имеют самая верхняя строка и самый левый столбец). Каждая клетка таблицы соответствует квадратному участку размером 1 на 1 метр. Хоббиты любят четкие и простые формы, поэтому Бильбо твердо намерен купить себе участок прямоугольной формы, со сторонами параллельными границам холма. Строго говоря он выбирает четыре числа x1
, x2
, y1
, y2
(x1
≤ x2
, y1
≤ y2
) и покупает все клетки (x, y), такие что (x1
≤ x ≤ x2
) and (y1
≤ y ≤ y2
).
Недавние приключения принесли Бильбо столько золота, что цена участков его не очень волнует, но при этом он сильно печется о своей репутации, поэтому он хочет, чтобы цена самой дешевой клетки, которую он купит, была как можно больше. Вместе с тем, нашему хоббиту крайне важен простор, поэтому площадь участка должна быть больше, либо равна k. Если существуют несколько участков с равной минимальной стоимостью клетки, Бильбо предпочтет тот, площадь которого больше.
Помогите Хоббиту выбрать наиболее подходящий для него участок.
Входные данные
В первой строке записаны три числа n, m и k, разделенные ровно одним пробелом количество строк, количество столбцов и минимальная площадь участка, на которую согласен Бильбо, соответственно. Следующие n строк содержат по m чисел каждая стоимости клеток соответствующей строки таблицы. Таким образом, число стоящее на месте j в строке i + 1, соответствует клетке с индексом (i, j). n и m натуральные и не превосходят 1000, k натуральное и не превосходит размера таблицы, все стоимости находятся в диапазоне от 1 до 109
включительно.
Выходные данные
В качестве ответа выведите два числа: сначала максимально возможную минимальную стоимость клетки участка, затем максимально возможную площадь такого участка.
3 3 3 1 1 1 1 2 2 1 2 2
2 4
1 10 5 4 3 2 5 10 7 6 5 1 100
5 5
3 5 2 5 7 5 5 5 8 5 5 7 5 8 5 8 8 8
8 3