H - マス目のカット Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 行 M 列のマス目が与えられます。それぞれのマスには数字が書かれており、上から i 行目、左から j 列目のマスには s_{i,j} が書かれています。 あなたは整数 n を選んで、どのマスにも同じ数字が書かれているように元のマス目から n 行 n 列の正方形状のマス目を切り出す仕事をしています。

K 個以下のマスを選んで書かれている数字を変えることができるとき、n の値は最大でいくつになりますか？

制約

  • 1 \leq N,M \leq 30
  • 0 \leq K \leq NM
  • s_i (1 \leq i \leq N) の長さは M
  • s_{i,j} は 0123456789 のいずれか

入力

入力は以下の形式で標準入力から与えられる。

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

出力

K 個以下のマスを選んで書かれている数字を変えることができるときの n の値としてありうる値の最大値を出力せよ。

入力例 1

3 4 3
1123
1214
1810

出力例 1

3
  • 上から i 行目、左から j 列目のマスを (i,j) と書くことにします。
  • マス (1,3),(2,2),(3,2) に書かれた数字を 1 に書き換えると、3 行 3 列のマス目のどのマスにも 1 が書かれているようにすることができます。

入力例 2

8 6 40
846444
790187
264253
967004
578258
204367
681998
034243

出力例 2

6

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a grid of squares with N rows and M columns. Each square has a digit written on it; the digit written on the square at the i-th row from the top and j-th column from the left is s_{i,j}. Your work is to choose an integer n and cut out a square-shaped grid of squares with n rows and n columns where all squares have the same digit written on them.

What is the maximum possible value of n when you can choose at most K squares and change the digits written on those squares?

Constraints

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

Input

Input is given from 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

Print the maximum possible value of n when you can choose at most K squares and change the digits written on those squares.

Sample Input 1

3 4 3
1123
1214
1810

Sample Output 1

3
  • Let (i,j) denotes the square at the i-th row from the top and j-th column from the left.
  • If you change the digits written on (1,3), (2,2), and (3,2), there will be a subgrid with 3 rows and 3 columns where all squares have 1 written on them.

Sample Input 2

8 6 40
846444
790187
264253
967004
578258
204367
681998
034243

Sample Output 2

6