AT_ddcc2017_qual_d 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 无论按何种顺序移除石头，只有在移除最后一块石头时才能获得幸福度。