問題文

南北方向に $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$ は整数で与えられる

---

入力

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

$H$ $W$ $A$ $B$ $m_{1,1}...m_{1,W}$ $:$ $m_{H,1}...m_{H,W}$

出力

得られる最大の幸福度が $x$ のとき、 $x$ を出力せよ。

---

入力例 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