AT_ddcc2017_qual_d.石

有一个南北方向为 $H$、东西方向为 $W$ 的网格状庭院，其中北起第 $i(1 \leq i \leq H)$ 行、西起第 $j(1 \leq j \leq W)$ 列的格子记为 $(i, j)$。

注意：$H$ 和 $W$ 均为偶数。

每个格子最多放置一块石头，且至少有一个格子放置了石头。
初始庭院的状态由字符串 $m_{i,j}$ 表示：若 $(i, j)$ 有石头，则 $m_{i,j} = \texttt{S}$；若无石头，则 $m_{i,j} = \texttt{.}$。

这些石头需要被逐一移除。移除某块石头后，若剩余石头的布局满足以下条件，则可获得相应的幸福度：

• 南北方向对称：获得 $A$ 点幸福度
• 东西方向对称：获得 $B$ 点幸福度
• 同时满足南北和东西对称：获得 $A + B$ 点幸福度

对称的定义

1. 南北对称：对于所有 $i, j(1 \leq i \leq H, 1 \leq j \leq W)$，若 $(i, j)$ 有石头，则 $(H + 1 - i, j)$ 也必须有石头；反之亦然。
2. 东西对称：对于所有 $i, j(1 \leq i \leq H, 1 \leq j \leq W)$，若 $(i, j)$ 有石头，则 $(i, W + 1 - j)$ 也必须有石头；反之亦然。

输入通过标准输入给出，格式如下：

$$H \, W \, A \, B \, m_{1,1} \ldots m_{1,W} : m_{H,1} \ldots m_{H,W}$$

输出能获得的最大幸福度 $x$。

约束条件

• $2 \leq H, W \leq 200$
• $H, W$ 为偶数
• $1 \leq A, B \leq 10000$
• $m_{i,j}$ 为 S 或 .
• 至少存在一个放置了石头的方格
• $H, W, A, B$ 以整数形式给出

---

样例解释 1

例如，按 $(3,3), (2,2), (2,3)$ 的顺序移除石头时，移除 $(3,3)$ 的石头后会形成东西方向的对称，移除 $(2,3)$ 的石头后会同时形成东西和南北方向的对称，此时获得的幸福度为 12。

---

样例解释 2

无论按何种顺序移除石头，只有在移除最后一块石头时才能获得幸福度。