Finding the Minimum Square with Sufficient Harmony

You are given an n \(\times\) m matrix that contains snowflakes. Each snowflake has a beauty value. A square submatrix's harmony is defined as the difference between the maximum and minimum beauty values inside that square. In other words, if a square submatrix has a minimum value \(m_{min}\) and a maximum value \(m_{max}\), its harmony is \(m_{max} - m_{min}\). The larger the harmony, the more "harmonious" the square.

You are also given a non-negative integer \(k\). Your task is to determine the minimum side length \(a\) of a square submatrix (i.e. a contiguous \(a \times a\) block) such that the harmony (\(m_{max} - m_{min}\)) of that square is at least \(k\). If no such square exists, output \(-1\).

Note: The squares should be contiguous and can start at any valid position in the matrix.

inputFormat

The first line of the input contains three integers: \(n\), \(m\), and \(k\) — the number of rows, the number of columns, and the required minimum harmony, respectively.

Each of the following \(n\) lines contains \(m\) integers representing the beauty values of the snowflakes in that row.

outputFormat

Output a single integer: the minimum side length \(a\) of a square whose harmony is at least \(k\). If there is no such square, output \(-1\).

sample

2 2 50
1 100
1 1

2