题目描述

You are doing volunteer work for a programming competition in an ancient hotel. Unfortunately, the hotel provides no phone signal or tap water since it can be dated back to the Qin Dynasty, and you have to assign the contestants to the hotel rooms manually instead of using the internet apps. Fortunately, the hotel has sufficient rooms, and you have taken a computer that lets you do some computation locally.

There are $n$ teams, each with exactly $3$ contestants. There are $2$ types of rooms in the hotel, the single room and double room, which can receive at most $1$ and $2$ contestants, respectively. To avoid embarrassing contestants, if two contestants are assigned to a double room, they must come from the same team and have the same gender.

The cost of each room of the same type is the same, but different types may have different costs. Your program needs to calculate the minimum price the host has to pay. The teams are waiting in the registration hall now, and the competition finance officer relies on you to save costs and make a fortune by the residual value. Be quick, or the finance officer will sue you for violating his reputation!

输入格式

The first line of input contains three integers $n$, $c_1$ and $c_2$ ($1 \leq n, c_1, c_2 \leq 1\,000$), denoting the number of teams, the cost of a single room and a double room respectively.

In the following $n$ lines, each line contains a string $S$ with exactly $3$ uppercase English letters. The letters in a string denote the genders of the contestants in one team and will be represented by $\texttt{A}$ to $\texttt{Z}$, respecting the diversity of human beings.

输出格式

The output should contain a single integer, denoting the minimum cost of hotel allocation for contestants.

题目大意

题目描述

你正在一个古代的酒店里为一场编程竞赛做志愿工作。酒店的历史可以追溯到秦朝，所以酒店不提供手机信号和自来水。你无法使用网络软件，不得不手动为参赛者分配房间。幸运的是，酒店拥有充足的房间，并且你有一台电脑帮你做一些计算。

共有 $n$ 个队伍，每个队伍恰有 $3$ 名选手。酒店有两种房间，单人间和双人间，分别可以容纳 $1$ 和 $2$ 名选手。为了避免使选手尴尬，如果两名选手分配到了同一个双人间，他们必须来自同一个队伍，并拥有相同的性别。

相同种类的房间的花费相同，但不同种类的房间花费可能不同。你需要计算主办方最少需要花多少钱。选手们已经在登记厅等候多时，而竞赛财务经理依靠你来节省开支，私吞剩下来的钱发大财。你需要尽快完成任务，否则财务经理将起诉你侵犯了他的名誉权！

$1\leq n, c_1, c_2\leq 1000$。

输入格式

第一行三个整数 $n, c_1, c_2$，分别表示队伍数量，单人间单价和双人间单价。

接下来的 $n$ 行，每行一个长度为 $3$ 的字符串 $S$ 表示一个队伍的参赛队员的性别。为了尊重人类的多样性，$S$ 可能包含从 $\texttt A$ 到 $\texttt Z$ 的所有大写字母。

输出格式

输出一行一个整数表示分配房间的最小代价。

3 1 3
MMM
MMM
FFF

9

3 3 1
ABC
DEF
GHI

9

10 438 438
WWW
SOU
PUN
ETC
OME
CFI
NAL
GOO
DHO
TEL

12264

提示

Source: The 2022 ICPC Asia Xi'an Regional Contest Problem F.

Author: fstqwq.