AT_ddcc2017_qual_d 石

[problemUrl]: https://atcoder.jp/contests/ddcc2017-qual/tasks/ddcc2017_qual_d 南北方向に $ 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) $ に石がない。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A $ $ B $ $ m_{1,1}...m_{1,W} $ $ : $ $ m_{H,1}...m_{H,W} $

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

### 制約 - $ 2≦H,W≦200 $ - $ H,W $ は偶数 - $ 1≦A,B≦10000 $ - $ m_{i,j} $ は `S` か `.` - 石が置かれているマスは $ 1 $ つ以上存在する - $ H,W,A,B $ は整数で与えられる ### Sample Explanation 1 たとえば、 $ (3,3) $,$ (2,2) $,$ (2,3) $ の順に石を取り除くと、$ (3,3) $ の石を取り除いた時に東西方向に対称になり、 $ (2,3) $ の石を取り除いたときに東西方向と南北方向に対称になり、得られる幸福度は $ 12 $ となる。 ### Sample Explanation 2 石をどの順番で取り除いても、最後の石を取り除いたとき以外に幸福度を得られない。