← 返回题目列表

Codeforces · 847/K

K. 旅行卡

中文机器翻译题面 查看原题

晚上,波利卡普决定分析他今天的公共交通出行费用。

贝尔兰首都的公交系统的布置方式是每辆公交车都沿着两个站点之间的路线运行。每辆巴士均无中间站。因此,每辆公交车都沿着路线从一站到另一站并返回。两个站点之间最多有一辆公共汽车运行。

Polycarp 乘坐公共汽车 n 次。关于每次行程,他开始行程的站点和结束行程的站点都是已知的。这些旅行按照波利卡普笔记中的时间顺序进行。

众所周知,乘坐任何公交车一次都要花费 1 英镑。如果乘客进行转运,旅行成本将减少至 b burles (b < a)。如果乘客上车的站点与他离开前一班车的站点一致,则该乘客进行转运。显然,首程不能采用转运方式。

例如,如果 Polycarp 连续三趟:“BerBank”$$\rightarrow$$“大学”、“大学”$$\rightarrow$$“BerMall”、“大学”$$\rightarrow$$“BerBank”,那么他支付了 a + b + a = 2a + b burles。他从 BerBank 到达大学,在那里换乘另一辆巴士前往 BerMall。然后他步行到大学,然后乘公共汽车返回 BerBank。

此外,Polycarp 最多可以购买 k 张旅行卡。每张旅行卡的价格为 f burles。单一巴士路线的旅行卡可以免费乘坐该路线的任何行程(双向)。购买后,旅行卡可以在任何方向使用任意次数。

如果波利卡普今天能购买不超过 k 张旅行卡,他最少可以花多少钱?

输入

第一行包含五个整数 n、a、b、k、f (1 ≤ n ≤ 300, 1 ≤ b < a ≤ 100, 0 ≤ k ≤ 300, 1 ≤ f ≤ 1000),其中:

- n — Polycarp 行程次数,
- a — 定期单程旅行的费用,
- b — 转运后的行程费用,
- k — Polycarp 可以购买的旅行卡的最大数量,
- f — 单张旅行卡的费用。

以下 n 行按时间顺序描述行程。每行包含两个不同的单词,并用一个空格分隔 - 行程的起点站名称和终点站名称。所有名称均由大小写英文字母组成,长度为 1 至 20 个字母(含)。大写和小写字母应被视为不同。

输出

打印 Polycarp 今天可以花费的最少金额(如果他可以购买不超过 k 个旅行卡)。

示例

输入 #1

3 5 3 1 8
BerBank University
University BerMall
University BerBank

输出 #1

11

输入 #2

4 2 1 300 1000
a A
A aa
aa AA
AA a

输出 #2

5

注意

在第一个示例中,Polycarp 可以购买路线“BerBank $$\leftarrow$$ University”的旅行卡并花费 8 burles。请注意,他的第二次旅行“大学”$$\rightarrow$$“BerMall”是在转运后进行的,因此波利卡普在这次旅行中支付了 3 burles。所以最小总和等于 8 + 3 = 11 burles。

在第二个示例中,购买旅行卡没有意义。请注意,波利卡普的每次旅行(第一次除外)都是通过转运进行的。所以最小总和等于 2 + 1 + 1 + 1 = 5 burles。