问题描述

有一个南北方向为 $H$，东西方向为 $W$ 的网格状花园，第 $i(1≦i≦H)$ 行，第 $j(1≦j≦W)$ 列的格子记作 $(i,j)$。

其中，$H$ 和 $W$ 是偶数。

每个格子最多有一个石头，而且至少有一个格子有石头。

初始花园状态由字符串 $m_{i,j}$ 描述，如果格子 $(i,j)$ 有石头，则 $m_{i,j}$ = S，如果没有石头，则 $m_{i,j}$ = .。

需要一次次地移除石头。

在移除石头后，如果花园在南北方向上呈对称状态，则得到快乐度 $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 或 .
• 至少存在一个格子有石头
• $H,W,A,B$ 是给定的整数

输入

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

$H$ $W$ $A$ $B$ $m_{1,1}...m_{1,W}$ : $m_{H,1}...m_{H,W}$

输出

输出最大快乐度 $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