A. Matrix Game
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

everflame and KisuraOP are playing a game. At the start of the game, everflame provides a matrix, and KisuraOP's goal is to manipulate this matrix to achieve the highest possible score.

The matrix given by everflame is an $$$n$$$ by $$$m$$$ matrix $$$a_{i, j}$$$, where each position can initially be either $$$0$$$ or $$$1$$$. Additionally, he provides two integers $$$A$$$ and $$$B$$$.

KisuraOP can perform any number of operations (including $$$0$$$) on this matrix, where each operation can be one of the following two types:

  • Choose an $$$i \in [1, n]$$$ and flip all elements in the $$$i$$$-th row.
  • Choose a $$$j \in [1, m]$$$ and flip all elements in the $$$j$$$-th column.

Flipping an element means that if it was originally $$$1$$$, it will become $$$0$$$; conversely, if it was originally $$$0$$$, it will become $$$1$$$.

For the element $$$a_{i, j}$$$ in the $$$i$$$-th row and $$$j$$$-th column of the matrix, if $$$a_{i, j} = 1$$$, then this element will contribute $$$(A\cdot i + B \cdot j)$$$ to the score; otherwise, its contribution will be $$$0$$$. The total score of the matrix will be the sum of the scores of all $$$n\times m$$$ elements.

Please help KisuraOP determine the maximum score that can be achieved after performing certain operations on this matrix.

Input

The first line contains four integers $$$n, m, A, B$$$ ($$$1 \le n \le 10^6, 1 \le m \le 10, 0 \le |A|, |B| \le 10^6$$$).

The next $$$n$$$ lines contain strings of length $$$m$$$. The character in the $$$i$$$-th row and $$$j$$$-th column represents $$$a_{i, j}\ (a_{i, j} \in \{0, 1\})$$$.

Output

Output a single integer, which is the maximum possible score.

Examples
Input
2 2 1 1
01
10
Output
12
Input
3 3 1 -5
010
000
010
Output
-8
Input
3 3 -3 -6
011
010
100
Output
-24
Note

For the first example, first flipping the $$$1$$$-st row and then flipping the $$$2$$$-nd column can make the entire matrix $$$1$$$, achieving the maximum score. The score is $$$(1\cdot 1 + 1\cdot 1) + (1\cdot 1 + 1\cdot 2) + (1\cdot 2 + 1 \cdot 1) + (1\cdot 2 + 1\cdot 2) = 12$$$.

For the second example, only flipping the $$$2$$$-nd column achieves the maximum score, and it can be proven that there is no better solution. The score is $$$1\cdot 2 + (-5)\cdot 2 = -8$$$.