Colorful Cookie

問題文

$H$ 行 $W$ 列のマス目があります。

各マスには クッキーが $0$ または $1$ 個配置されており、各クッキーには色 a から色 z までのいずれかの色が与えられています。

あなたは $1$ 回のみ、 $K$ 個以下のマスを含む $1$ つの長方形領域を指定し、その範囲内のクッキーをすべて獲得できます。（長方形領域の各辺は行方向または列方向に平行である必要があります）

このとき得る嬉しさは、(獲得したクッキーの個数) $\times$ (獲得したクッキーの色の種類数) です。

あなたが得ることができる嬉しさの最大値を求めてください。

制約

• $1 \leq H \leq 5000$
• $1 \leq W \leq 10$
• $1 \leq K \leq H \times W$
• 入力される数値はすべて整数

入力

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

$1$ 行目に、$H$、$W$、$K$ が空白区切りで与えられる。

続く $H$ 行に、各行のクッキーの色が記された文字列 $S_i$ が与えられる。

各 $S_i$ は長さ $W$ の文字列であり、各文字は a から z、もしくは . (ドット) である。

a から z までの文字は配置されているクッキーの色を示し、. (ドット) はクッキーが配置されていないことを示す。

出力

答えを出力せよ。

サンプル

4 6 5
aab...
aa....
..abc.
.....c

9

例えば次のような長方形領域を選択する場合、あなたが獲得するクッキーは、色 a が $2$ 個、色 b が $1$ 個の計 $3$ 個なので、得る嬉しさは $3 \times 2 = 6$ です。

.##...
.##...
......
......

また、次のような長方形領域を選択する場合、あなたが獲得するクッキーは、色 a が $1$ 個、色 b が $1$ 個、色 c が $1$ 個の計 $3$ 個なので、得る嬉しさは $3 \times 3 = 9$ です。

......
......
..###.
......

$10$ 以上の嬉しさを得る長方形領域を選択することはできないため、答えは $9$ となります。

以下のような長方形領域は選択することができないことに注意してください。

NG: 長方形でない
###...
##....
......
......

NG: 長方形領域の各辺が行方向または列方向に平行でない
......
...#..
..###.
...#..

NG: 範囲内のマス数が K 個以下でない
......
..###.
..###.
......

NG: 長方形領域を2つ以上選択している
###...
....#.
....#.
......

3 3 9
...
...
...

0

クッキーが $1$ つも配置されていない場合もあります。

33 10 12
..c.e.gxxx
.....f....
a.cd..g...
.....f....
a.cd..g...
.....f....
a.cd..g...
.....f....
a.cd..g...
.b........
a..de.g...
.b........
a..de.g...
.b........
a..de.g...
.b........
a..de.gxxx
..........
a.c.......
....e.g...
a.cd......
....e.g...
a.c.......
....e.g...
a.cd...xxx
....e.g...
a.c.......
....e.g...
a.cd......
....e.g...
a.c.......
....e.g...
a.cd...xxx

35

2 9 6
thank.you
good.bye.

30