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