climatechange

Problem Description

Climate change has been affecting the entirety of Guan Island recently, with Guan's slave farmers quickly losing arable land to farm to feed Guan's insatiable hunger. Guan Island can be described as a grid of N by M integers, with each integer within a grid representing the height above "sea level" at that point on Guan Island. However, the sea level has started to rise and if the height of the sea is the same or greater than the height of the land, the grid square will be flooded.

Guan's slaves are planning to build a rectangular farm and this farm must be at least of area S square units so as to satisfy Guan. Help calculate what is the maximum sea level rise that can happen for Guan's slaves to still be able to build that farm.

Input

The first line of input will contain three integers, N, M and S.
The next N lines will contain M strictly positive integers each, which describes the varying height of Guan Island.

Output

The output should contain exactly one integer, the maximum sea level rise that can happen for Guan's slaves to still be able to build that farm.

Limits

All integers in the input will be under 1 000 000 000.
Subtask 1 (14%): 1 ≤ N, M ≤ 50.
Subtask 2 (21%): 1 ≤ N ≤ 50. 1 ≤ M ≤ 1 000.
Subtask 3 (3%): 1 ≤ N, M ≤ 1 000. S = 1.
Subtask 4 (62%): 1 ≤ N, M ≤ 1 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

4 5 5
3 3 3 3 4
1 3 4 3 2
3 4 5 1 2
4 5 1 2 3

Sample Output 1

2

Sample Input 2

4 5 7
1 3 4 2 3
2 3 4 1 3
2 2 2 3 4
2 4 5 1 3

Sample Output 2

1

Submitting to 'climatechange'


You're not logged in! Click here to login


Submitting to 'climatechange'


You're not logged in! Click here to login


Submitting .cpp to 'climatechange'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 1024MB
No. of ACs: 4
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 14
2 21
3 3
4 62
5 0