003 - アニヲタの部屋

時間制限 1 秒 / メモリ制限 64 MB / 得点 50 / x 3 /


TLE
1sec
MLE
64MB
得点
50

問題

アニメグッズが床に散乱しているアニヲタの部屋があります。
グッズのアニメはAからZで表される。

泥棒IDAはトラックで現場に向かいます。

泥棒IDAがその部屋のグッズをすべて盗もうと計画していますが、泥棒IDAはすごく几帳面な性格をしているので、いちどに、隣接する同じアニメのグッズしか盗み出しません。
同様の理由で泥棒IDAは盗み出したグッズを毎回部屋の外のトラックに積み込みに行きます。
しかし、その部屋からトラックまでは距離があり、最速でもT分かかってしまいます。

アニヲタの部屋の情報が与えられるので、始め、トラックから降りて泥棒IDAがその部屋のグッズすべてを盗み出し、最後、トラックに戻るまでにかかる最速時間を求めて下さい。

なお、泥棒IDAは凄腕なため、部屋に入り、グッズを部屋から出す間での時間は全くかからないものとする(考えないものとする)。

入力

一行目にはアニヲタの部屋の広さH W ( 1 ≤ W H ≤ 100 ) が与えられ、
続いて、部屋の情報となるH * WからなるH行の文字列Rが与えられます。

出力

部屋のアニメグッズをすべて盗み出して、トラックに戻るまでにかかる最速時間を出力する。

入出力例

入力例1

5 5 4
YYPPG
PPPPG
GGPPY
KKKKY
KPPKK

出力例1

56

入力例2

3 6 2
PPPPPP
PPNNPP
PPPPPP

出力例2

8

備考

因みに、入力例のY P G K Nはそれぞれ
ゆるゆり
プリキュア
ごちうさ
きんモザ
のんのんびより
を意識しているが、問題には関係ない。