在 Vito 的桌子上，有 $N$ 张编号从 $1$ 到 $N$ 的红卡，以及 $M$ 张编号从 $1$ 到 $M$ 的蓝卡。每一对红卡和蓝卡 $(c, p)$（其中 $c$ 代表一张红卡，$p$ 代表一张蓝卡）都可以组成一个 COMBO 动作。

一副卡牌的强度定义为： $$strength = (\text{COMBO 动作的数量}) - X \cdot (\text{红卡数量}) - Y \cdot (\text{蓝卡数量})$$ 其中，COMBO 动作的数量是指所选卡组中满足条件的红卡 $c$ 和蓝卡 $p$ 的配对 $(c, p)$ 的数量。Vito 可以从桌上选择任意数量的卡牌放入他的卡组中。请帮助 Vito 找出他能构建的最强卡组的强度值。Vito 也可以选择不放入任何卡牌（空卡组）。

输入格式

第一行包含 4 个自然数 $N, M, X, Y$ ($1 \le N, M \le 21, 0 \le X, Y \le 30$)。

接下来的 $N$ 行中，每行包含一个长度为 $M$ 的字符序列（由 $0$ 或 $1$ 组成），其中第 $j$ 个字符表示第 $i$ 张红卡和第 $j$ 张蓝卡是否能组成一个 COMBO 动作。

输出格式

在唯一的一行中，输出 Vito 能构建的最强卡组的强度值。

子任务

样例

输入 1

2 2 0 0
11
10

输出 1

3

说明 1

Vito 将选择桌上所有的卡牌，从而产生 3 个 COMBO 动作。

输入 2

3 3 1 0
111
111
000

输出 2

4

说明 2

Vito 将选择前 2 张红卡和全部 3 张蓝卡，从而产生 6 个 COMBO 动作。卡组强度为 4，因为 Vito 选择了 2 张红卡，所以 COMBO 动作的数量（即 6）减去了 2。

输入 3

3 3 1 1
111
101
011

输出 3

1