問題文

HHWW 列のマス目があります。

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

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

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

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

制約

  • 1H50001 \leq H \leq 5000
  • 1W101 \leq W \leq 10
  • 1KH×W1 \leq K \leq H \times W
  • 入力される数値はすべて整数

入力

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

11 行目に、HHWWKK が空白区切りで与えられる。

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

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

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

HH WW KK
S1S_1
S2S_2

SHS_H

出力

答えを出力せよ。

サンプル

入力例1
4 6 5
aab...
aa....
..abc.
.....c
出力例1
9

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

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

また、次のような長方形領域を選択する場合、あなたが獲得するクッキーは、色 a11 個、色 b11 個、色 c11 個の計 33 個なので、得る嬉しさは 3×3=93 \times 3 = 9 です。

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

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

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

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

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

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

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

入力例2
3 3 9
...
...
...
出力例2
0

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


入力例3
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
出力例3
35

入力例4
2 9 6
thank.you
good.bye.
出力例4
30

Submit


Go (1.21)