実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 600 点
問題文
南北方向に 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