DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選

D - 石


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 600

問題文

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

ただし、 HW は偶数とします。

各マスには石が高々 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

Submit提出する