#5704. 「COCI 2024/2025 #3」Karte

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #3 T2「Karte」

在 Vito 的桌子上，有 $N$ 张红色的牌（编号从 $1$ 到 $N$）和 $M$ 张蓝色的牌（编号从 $1$ 到 $M$）。每一对红色牌 $c$ 和蓝色牌 $p$ 都可以创建一个 $\text{COMBO}$ 动作。

一副牌的强度定义为：

$$\text{强度} = (\text{COMBO 动作的数量}) - X \cdot (\text{红色牌的数量}) - Y \cdot (\text{蓝色牌的数量})$$

其中 $\text{COMBO}$ 动作的数量是指所选卡组中满足特定配对关系（$c, p$）的对数。Vito 可以将桌上的任意牌放入他的卡组中。请帮助 Vito 找出他能构建的最强卡组的强度值。Vito 也可以选择一副空牌组。

输入格式

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

接下来的 $N$ 行中，每行包含一个长度为 $M$ 的字符序列（$0$ 或 $1$），其中第 $j$ 个字符表示第 $i$ 张红色牌和第 $j$ 张蓝色牌是否可以创建一个 $\text{COMBO}$ 动作。

输出格式

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

样例 1

输入

2 2 0 0
11
10

输出

3

Vito 将选择桌上所有的牌，从而创建 $3$ 个 $\text{COMBO}$ 动作。

样例 2

输入

3 3 1 0
111
111
000

输出

4

Vito 将选择前 $2$ 张红色牌和全部 $3$ 张蓝色牌，从而创建 $6$ 个 $\text{COMBO}$ 动作。卡组强度为 $4$，因为 Vito 选择了 $2$ 张红色牌，$3$ 张蓝色牌，所以 $\text{COMBO}$ 动作数量（即 $6$）减去 $2$ 倍的红色牌数量（$2 \times 1 = 2$）和 $0$ 倍的蓝色牌数量，结果为 $4$。

样例 3

输入

3 3 1 1
111
101
011

输出

1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$18$	$Y=0$
$2$	$11$	$1 \leq N, M \leq 9$
$3$	$24$	$1 \leq N, M \leq 15$
$4$	$17$	无附加限制