問題文

南北方向に H 、東西方向に W のグリッド状の庭があり、北から i(1≦i≦H) 番目、西から j(1≦j≦W) 番目のマスを (i,j) とします。

ただし、 H と W は偶数とします。

各マスには石が高々 1 つ置かれており、また、 1 つ以上のマスに石が置かれています。

なお、最初の庭の状態は、文字列 m_{i,j} を用いて、 (i,j) に石があるなら m_{i,j} = S、石がないなら m_{i,j} = . として与えられます。

これらの石を 1 つずつ取り除いていきます。

石を取り除いた直後に、庭の石の配置が南北方向に対称なら A の幸福度、東西方向に対称なら B の幸福度が得られます。

ただし、南北方向にも東西方向にも対称のときは A+B の幸福度が得られることとします。

全ての石を自由な順番で取り除くとき、得られる最大の幸福度を求めてください。

なお、南北方向に対称とは、以下のことが成り立つ場合です。

• すべての i,j(1≦i≦H,1≦j≦W) において (i,j) に石があるなら (H+1-i,j) にも石があり、 (i,j) に石がなければ (H+1-i,j) に石がない。

また、東西方向に対称とは、以下のことが成り立つ場合です。

• すべての i,j(1≦i≦H,1≦j≦W) において (i,j) に石があるなら (i,W+1-j) にも石があり、 (i,j) に石がなければ (i,W+1-j) に石がない。

制約

• 2≦H,W≦200
• H,W は偶数
• 1≦A,B≦10000
• m_{i,j} は S か .
• 石が置かれているマスは 1 つ以上存在する
• H,W,A,B は整数で与えられる

入力例 1

4 4
2 5
....
.SS.
..S.
....

出力例 1

12

たとえば、 (3,3),(2,2),(2,3) の順に石を取り除くと、(3,3) の石を取り除いた時に東西方向に対称になり、 (2,3) の石を取り除いたときに東西方向と南北方向に対称になり、得られる幸福度は 12 となる。

入力例 2

2 2
4 7
.S
S.

出力例 2

11

石をどの順番で取り除いても、最後の石を取り除いたとき以外に幸福度を得られない。

入力例 3

4 8
9 13
.SS.....
.SS.....
.SS.....
.SS.....

出力例 3

49