Pyramid Construction

You are given an island in the form of an n × m grid. Each cell has an integer height. You want to construct a pyramid on a rectangular sub-area of the island. A pyramid of height \(h\) is defined on a square of size \((2h-1)\times(2h-1)\). In such a square, the desired height for the cell located at relative coordinates \((r, c)\) (with \(0 \le r,c < 2h-1\)) is given by:

\( H_{desired} = h - \max(|r-(h-1)|,\,|c-(h-1)|) \)

This means that the outermost layer (where \(\max(|r-(h-1)|,|c-(h-1)|)=h-1\)) should have height 1, the next inner layer should have height 2, and so on, with the center cell having height \(h\).

You are allowed to modify the terrain at most p times. In one modification, you can choose any cell and increase its height by 1 (you are not allowed to decrease any height). Determine the maximum possible pyramid height \(h\) that can be constructed on some sub-square of the island by performing no more than p modifications.

Note that the pyramid must exactly match the desired pattern and must lie completely within the island.

inputFormat

The first line contains three integers \(n\), \(m\), and \(p\) (1 ≤ n, m ≤ 100, 0 ≤ p ≤ 10^9) representing the dimensions of the island and the maximum number of modifications, respectively.

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)-th integer in the \(i\)-th line is the height of the cell in row \(i\) and column \(j\) (0 ≤ height ≤ 10^9).

outputFormat

Output a single integer: the maximum pyramid height \(h\) that can be achieved with no more than \(p\) modifications.

sample

3 3 0
1 1 1
1 2 1
1 1 1

2