ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Quarterfinal, Rybinsk, October 16 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Warehouse

Time limit: 1.0 second
Memory limit: 64 MB
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.
123
X123
Y456
Z789
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:
123
x555
y556
z789
Your task is to write a program, which determines the minimum height of the sections after placing new containers.

Input

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

Output the minimum height of the warehouse sections after the placement of new containers.

Samples

inputoutput
2 2 3
1 3
2 4
3
3 3 10
1 2 3
4 5 6
7 8 9
5
Problem Author: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Problem Source: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003
To submit the solution for this problem go to the Problem set: 1279. Warehouse