ICPC で良い成績を収めるには修行が欠かせない.うさぎは ICPC で勝ちたいので,今日も修行をすることにした.
今日の修行は,流行りのパズルをすばやく解いて,瞬発力を鍛えようというものである.今日挑戦するのは,色とりどりのタイルが並んでいてそれらを上手く消していくパズルだ
初期状態では,グリッド上のいくつかのマスにタイルが置かれている.各タイルには色がついている.プレイヤーはゲーム開始後,以下の手順で示される操作を何回も行うことができる.
たとえば,以下のような状況を考えよう.タイルが置かれていないマスはピリオドで,タイルの色はアルファベット大文字で表されている.
..A....... .......B.. .......... ..B....... ..A.CC....
ここで上から 2 行目,左から 3 列目のマスを叩く操作を考える.着目することになるタイルは A , B , B の 3 枚であるから,B の 2 枚が消えて盤面は以下のようになり,2 点を得る.
..A....... .......... .......... .......... ..A.CC....
このパズルはゆっくりしていると時間切れになってしまい,盤面の一部が見えなくなりどのくらい修行が足りなかったのかがわからなくなってしまう. 各色のタイルは 2 枚ずつ置かれているが,それらをすべて消せるとは限らないので,予めプログラムに得点の最大値を計算させておきたい.
M N C1,1C1,2...C1,N C2,1C2,2...C2,N ... CM,1CM,2...CM,N
整数 M, N は盤が 縦 M × 横 N のマス目であることを表す.Ci, j はアルファベット大文字またはピリオド ( . ) であり,上から i 行目,左から j 列目のマスについて,アルファベット大文字の場合は置かれているタイルの色を表し,ピリオドの場合はこのマスにタイルが置かれていないことを表す.
1 ≤ M ≤ 500,1 ≤ N ≤ 500 を満たす.各アルファベット大文字は入力中に 0 個または 2 個現れる.
得点の最大値を 1 行に出力せよ.
5 10 ..A....... .......B.. .......... ..B....... ..A.CC....
4
3 3 ABC D.D CBA
4
5 7 NUTUBOR QT.SZRQ SANAGIP LMDGZBM KLKIODP
34