2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января
Hobbit Bilbo is very tired from his adventures and decided to build a new burrow. The hill, where he plans to buy some land, has a shape of a rectangle and it can be represented as a table consisting of n rows and m columns (rows and columns are numbered starting from 1, where 1 corresponds to the topmost row and the leftmost column). Each cell of the table corresponds to a 1 × 1 square piece. Hobbits like simple shapes, that's why Bilbo intends to buy a plot of land of a rectangular shape, with sides parallel to the sides of the hill. In other words he chooses
y2) and buys all cells (x, y), such that (
x1 ≤ x ≤
x2) and (
y1 ≤ y ≤
After all adventures he took part in, Bilbo is very rich and is not worried about the total price. However, he thinks a lot about his reputation and thus the price of the cheapest cell he will buy must be as high as possible. He also wants his new burrow to be enough to fit all of his furniture, that means the square of a rectangular plot he will buy has to have an area greater than or equal to k. If there are multiple possible plots, Bilbo chooses the one with the largest area. Bilbo asks you to nd the best plot of land for him.
The first line contains three numbers n, m and k, divided by exactly one space the number of rows, the number of columns and the minimal possible square of land plot Bilbo can live on, respectively. Each of the following n lines contains m numbers the prices of the corresponding cells. Hence, the number j in the line i + 1, corresponds to the cell (i, j). n and m are positive integers and do not exceed 1000, k is positive integer and does not exceed the total number of cells in the table, all prices belong to range from 1 to
As the answer, output two numbers separated by space. First goes the price of the cheapest cell in the resulting rectangular plot. Second is the total square of this plot.
3 3 3 1 1 1 1 2 2 1 2 2
1 10 5 4 3 2 5 10 7 6 5 1 100
3 5 2 5 7 5 5 5 8 5 5 7 5 8 5 8 8 8