题目描述

有一个大小为 $H×W$ 的网格状庭院，上起第 $i(1≦i≦H)$ 行，左起第 $j(1≦j≦W)$ 列的格子被标记为 $(i,j)$ 。 $H$ 和 $W$ 是偶数。

每个方格最多能放置一块石头，且至少有一个方格放置了石头。 另外，最初庭院的状态用字符串 $m_ {i,j} $表示，如果$(i,j)$位置有石头，则标记为$S$，否则标记为$.$ 。

我们需要搬走一些石头。搬走一块石头后，如果庭院中的石头位置南北方向对称，则能获得 $A$ 点幸福度，如果东西方向对称，能获得 $B$ 点幸福度。

如果南北和东西方向都对称，则能获得 $A+B$ 点幸福度。

当所有石头一一被取走后，请求出可获得的最大幸福度 $x$ 。

南北方向对称成立是指以下的情况：

• 在所有 $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。

数据限制

2≦H,W≦200。

H,W是偶数。

1≦A,B≦10000。

m i,j ​ 是"S"或"."。

至少有一个方格放置石头。

给出的H,W,A,B均为整数。