Description

There are $n\times m$ snowflakes placed in an $n\times m$ matrix. Each snowflake has a beauty value. The harmony of a square is defined as the difference between the maximum beauty value and the minimum beauty value in that square. The greater the harmony value, the more harmonious the square is. Given this matrix and a non-negative integer $k$, zzs and zzy want you to tell them the smallest side length among all squares with harmony at least $k$ (that is, find the smallest side length $a$ such that there exists a square of side length $a$ whose harmony is at least $k$). If there is no solution, output $-1$.

Input Format

The first line contains two positive integers and a non-negative integer, $n, m$ and $k$. The next $n$ lines each contain $m$ non-negative integers, representing the matrix.

Output Format

If there is a solution, output a single positive integer representing the answer. If there is no solution, output $-1$.

3 5 7
3 4 2 8 7
6 5 2 4 6
3 1 4 0 9

2

Hint

Constraints

• For $20\%$ of the testdata, $1 \le n, m \le 20$.
• For $100\%$ of the testdata, $1 \le n, m \le 500$.
• For $100\%$ of the testdata, all numbers in the matrix do not exceed $100000$.

Translated by ChatGPT 5