A warehouse is an N×M meter sized rectangle, which is divided into sections of 1×1 meter. The warehouse is served by a roof-mounted crane. 1×1 meter sized containers may be stacked one atop another in each section.
A new lot of K containers of the same kind arrived to the warehouse. It was decided to place the new containers so that the sections having less containers would be filled first.
For example, let N=3, M=3, K=10 and the number of containers in each section is represented in the table below.
In this case the new containers will be sequentially placed in sections: x1, x1, x2, x1, x2, x3, x1, x2, x3, y1. After that the heights of the sections will be as follows:
Your task is to write a program, which determines the minimum height of the sections after placing new containers.
The first line contains three integer numbers N, M, K (0 < N, M ≤ 100, 0 < K ≤ 107), where N and M are dimensions of the warehouse, and K is the number of new containers.
Each of the following N lines contains M space-separated integer numbers ranging from 1 to 1000. These numbers are the heights of the corresponding sections.
Output the minimum height of the warehouse sections after the placement of new containers.
2 2 3
3 3 10
1 2 3
4 5 6
7 8 9
Автор задачи: © Sergey G. Volchenkov, 2003(firstname.lastname@example.org); Vladimir N. Pinaev, 2003(email@example.com; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (firstname.lastname@example.org).
Источник задачи: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003