Problem Description

You are given a grid of $ N $ rows and $ M $ columns. Each cell contains a number, and the cell at the $ i $-th row and $ j $-th column contains $ s_{i,j} $. Your task is to choose an integer $ n $ and cut out an $n \times n$ square subgrid from the original grid such that all cells in the subgrid contain the same number.

You can change the number in up to $ K $ cells. What is the maximum value of $ n $ that can be achieved?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $s_{1,1}\cdots\ s_{1,M}$ $\vdots$ $s_{N,1}\cdots\ s_{N,M}$

Output Format

Output the maximum possible value of $ n $ when you can change the number in up to $ K $ cells.

Sample Input and Output

Sample Input #1

3 4 3
1123
1214
1810

Sample Output #1

3

Sample Input #2

8 6 40
846444
790187
264253
967004
578258
204367
681998
034243

Sample Output #2

6

Notes/Hints

Constraints

• $1 \leq N, M \leq 30$
• $0 \leq K \leq$
• The length of $ s_i $ (for $1 \leq i \leq N$) is $ M $
• $ s_{i,j} $ is one of 0123456789

Sample Explanation 1

• Let the cell at the $ i $-th row and $ j $-th column be denoted as $ (i,j) $.
• Changing the numbers in cells $ (1,3),(2,2),(3,2) $ to 1 allows you to form a $3 \times 3$ subgrid where all cells contain 1.

见题面 Input 部分

见题面 Output 部分