009 - 縄張りの大きさ

問題

イズア地方には、東西にW本、南北にH本の木が格子状に並ぶ森がある。ただし，並んでいる木の種類は同じとは限らない。この森には奇妙な習性を持つ鳥が住んでいる。

この鳥は、東西と南北にそれぞれ同じ数だけ並んだ正方形の木の領域を縄張りとする。少なくとも$k$箇所の縄張りを確保し、それらを次々と移動する。ただし、この鳥はとてもデリケートなので、それらの縄張りはどれも同じ大きさで、その中の木の並びが同じになっていなければならない。そのような縄張りを$k$箇所以上確保できるときは、一つの縄張りが最も広くなるものを選ぶ。

たとえば、上の図のような東西に５本、南北に４本の木が格子状に並んだ森がある（英小文字は木の種類を表す）とき、縄張りを２箇所以上確保したい鳥($k=2$)は、線で囲んだ２つの縄張りの間を移動する。

鳥類学者であるあなたは、この鳥の一つの縄張りの大きさを明らかにしたいと考えている。

森の情報と鳥が確保したい縄張りの最低の個数が与えられたとき、その鳥が確保する一つの縄張りの大きさを求めるプログラムを作成せよ。ただし、縄張りの大きさは、その中に東西または南北に並んだ木の本数で表すものとする。

入力

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

$H$ $W$ $k$
$t_{1,1}$ $t_{1,2}$ ... $t_{1,W}$
$t_{2,1}$ $t_{2,2}$ ... $t_{2,W}$
  :
$t_{H,1}$ $t_{H,2}$ ... $t_{H,W}$

１行目に、森の木が南北に並んだ本数$H$ ($1 \leq H \leq 600$)、東西に並んだ本数$W$ ($1 \leq W \leq 600$)と、鳥が少なくとも確保したい縄張りの数$k$ ($2 \leq k \leq H \times W$)が与えられる。続く$H$行に、格子状に並んだ木の情報が英小文字で与えられる。ただし、$t_{1,1}$, $t_{1,W}$, $t_{H,1}$, $t_{H,W}$ はそれぞれ森の北西、北東、南西、南東の隅にある木を表す。文字の種類が木の種類に対応する。

出力

鳥が確保する一つの縄張りの中に、東西または南北に並んだ木の本数を1行に出力する。ただし、縄張りをk箇所以上確保できないときは、「 -1 」を出力する。

入出力例

入力例１

4 5 2
abbcd
aabba
aaabb
aaaaa

出力例１

3

入力例２

3 3 5
cbb
dab
aaa

出力例２

-1