题目背景

译自 COCI 2024/2025 #3 T2。$\texttt{1s,0.5G}$。满分为 $70$。

题目描述

在 Vito 的桌子上，有 $N$ 张编号分别为 $1\sim N$ 的红牌和 $M$ 张编号分别为 $1\sim M$ 的蓝牌。

将一张红牌和一张蓝牌称为「一对」，给定若干个二元组 $(c,p)$。若一对牌中，红牌编号为 $c$，蓝牌编号为 $p$，则称这对牌是好对。

一个牌堆包含若干张红牌和若干张蓝牌。定义一个牌堆的价值 $w$ 为牌堆中选出一对，使得这个对是一个好对的方案数。

令 $r$ 为牌堆中红牌的数量，$b$ 为牌堆中蓝牌的数量，定义牌堆的强度 $\mathrm{strength}$ 为：

其中 $X$ 和 $Y$ 是给定的常数。

帮助 Vito 确定：选择若干张红牌和蓝牌构成一个牌堆，这个牌堆的最大强度为多少。注意，他也可以一张牌都不选（即构成一个空的牌堆）。

输入格式

第一行，四个非负整数 $N,M,X,Y$。

接下来 $N$ 行，每行一个长度为 $M$ 的 $\texttt{01}$ 串，其中第 $i$ 行的字符串中第 $j$ 位为 $1$ 表示 $(i,j)$ 是好的，否则表示不是好的。

输出格式

输出一行一个非负整数，表示可以构成的牌堆的最大强度。

2 2 0 0
11
10

3

3 3 1 0
111
111
000

4

3 3 1 1
111
101
011

1

提示

样例解释

样例 $1$ 中，Vito 可以选择所有的卡牌，能产生 $3$ 个好对，牌堆的最大强度为 $3$。

样例 $2$ 中，Vito 可以选择编号为 $1,2$ 的红牌和所有的蓝牌，能产生 $6$ 个好对，牌堆的最大强度为 $4$（由于选择了两张红牌，所以要将好对数减去 $2X=2$ 作为牌堆的强度）。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le N,M\le 21$；
• $0\le X,Y\le 30$；
• 输入的字符串中仅包含 $0$ 和 $1$。