Problem Description

There is a grid-shaped garden with $H$ in the north-south direction and $W$ in the east-west direction. The cell at the $i$-th position from the north and the $j$-th position from the west is denoted as $(i,j)$.

Here, $H$ and $W$ are even numbers.

Each cell has at most one stone placed on it, and there is at least one stone placed on the cells.

The initial state of the garden is given using strings $m_{i,j}$, where $m_{i,j}$ = S if there is a stone at $(i,j)$, and $m_{i,j}$ = . if there is no stone.

We will remove these stones one by one.

Immediately after removing a stone, if the stone configuration in the garden is symmetric in the north-south direction, happiness points of $A$ are obtained; if it is symmetric in the east-west direction, happiness points of $B$ are obtained.

If it is symmetric in both directions, happiness points of $A+B$ are obtained.

Find the maximum happiness points that can be obtained when all stones are removed in any order.

Symmetry in the north-south direction means the following holds:

• For all $i,j(1≦i≦H,1≦j≦W)$, if there is a stone at $(i,j)$, there is also a stone at $(H+1-i,j)$, and if there is no stone at $(i,j)$, there is no stone at $(H+1-i,j)$.

Symmetry in the east-west direction means the following holds:

• For all $i,j(1≦i≦H,1≦j≦W)$, if there is a stone at $(i,j)$, there is also a stone at $(i,W+1-j)$, and if there is no stone at $(i,j)$, there is no stone at $(i,W+1-j)$.

Input Format

The input is given from the standard input in the following format:

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

Output Format

When the maximum happiness points obtained is $x$, output $x$.

Sample Input and Output

Sample Input #1

4 4
2 5
....
.SS.
..S.
....

Sample Output #1

12

Sample Input #2

2 2
4 7
.S
S.

Sample Output #2

11

Sample Input #3

4 8
9 13
.SS.....
.SS.....
.SS.....
.SS.....

Sample Output #3

49

Notes/Hints

Constraints

• $ 2≦H,W≦200 $
• $ H,W $ are even numbers
• $ 1≦A,B≦10000 $
• $ m_{i,j} $ is either S or .
• There is at least one cell with a stone
• $ H,W,A,B $ are given as integers

Sample Explanation 1

For example, if the stones are removed in the order of $(3,3)$, $(2,2)$, $(2,3)$, the garden becomes symmetric in the east-west direction when the stone at $(3,3)$ is removed, and becomes symmetric in both directions when the stone at $(2,3)$ is removed, resulting in a total happiness points of $12$.

Sample Explanation 2

No matter the order in which the stones are removed, happiness points can only be obtained when the last stone is removed.

见题面 Input 部分

见题面 Output 部分