Description

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

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

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

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

Input Format

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

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

Output Format

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

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