CF847K.Travel Cards

In the evening Polycarp decided to analyze his today's travel expenses on public transport.

The bus system in the capital of Berland is arranged in such a way that each bus runs along the route between two stops. Each bus has no intermediate stops. So each of the buses continuously runs along the route from one stop to the other and back. There is at most one bus running between a pair of stops.

Polycarp made n trips on buses. About each trip the stop where he started the trip and the the stop where he finished are known. The trips follow in the chronological order in Polycarp's notes.

It is known that one trip on any bus costs a burles. In case when passenger makes a transshipment the cost of trip decreases to b burles (b < a). A passenger makes a transshipment if the stop on which he boards the bus coincides with the stop where he left the previous bus. Obviously, the first trip can not be made with transshipment.

For example, if Polycarp made three consecutive trips: "BerBank" "University", "University" "BerMall", "University" "BerBank", then he payed a + b + a = 2_a_ + b burles. From the BerBank he arrived to the University, where he made transshipment to the other bus and departed to the BerMall. Then he walked to the University and returned to the BerBank by bus.

Also Polycarp can buy no more than k travel cards. Each travel card costs f burles. The travel card for a single bus route makes free of charge any trip by this route (in both directions). Once purchased, a travel card can be used any number of times in any direction.

What is the smallest amount of money Polycarp could have spent today if he can buy no more than k travel cards?

晚上，Polycarp 决定分析他今天乘坐公共交通工具的出行花费。

Berland 首都的公交系统设计如下：每辆公交车仅在两个站点之间沿固定路线运行，且途中无任何中间停靠站。因此，每辆公交车持续地在两个站点之间往返运行。任意一对站点之间至多只有一辆公交车运行。

Polycarp 共乘坐公交车完成了 $n$ 次行程。对每次行程，已知其出发站点与到达站点。这些行程按时间顺序记录在 Polycarp 的笔记中。

已知：乘坐任意一趟公交车的费用为 $a$ burles。若乘客进行了换乘（transshipment），则该趟行程费用降为 $b$ burles（其中 $b < a$）。当乘客上车的站点恰好等于其上一趟行程下车的站点时，即视为一次换乘。显然，第一次行程不可能是换乘。

例如，若 Polycarp 连续进行了三次行程：“BerBank” “University”，“University” “BerMall”，“University” “BerBank”，则他总共支付了 $a + b + a = 2a + b$ burles。他从 BerBank 出发抵达 University，在 University 换乘另一辆公交车前往 BerMall；随后步行回到 University，并再次乘公交车返回 BerBank。

此外，Polycarp 最多可购买 $k$ 张交通卡（travel cards），每张交通卡售价为 $f$ burles。一张针对某条公交线路的交通卡，可使乘客免费乘坐该线路的任意班次（双向均适用）。一旦购得，该交通卡可在任意方向、任意次数使用。

如果 Polycarp 最多可购买 $k$ 张交通卡，那么他今天最少可能花费多少钱？

The first line contains five integers n, a, b, k, f (1 ≤ n ≤ 300, 1 ≤ b < a ≤ 100, 0 ≤ k ≤ 300, 1 ≤ f ≤ 1000) where:

• n — the number of Polycarp trips,
• a — the cost of a regualar single trip,
• b — the cost of a trip after a transshipment,
• k — the maximum number of travel cards Polycarp can buy,
• f — the cost of a single travel card.

The following n lines describe the trips in the chronological order. Each line contains exactly two different words separated by a single space — the name of the start stop and the name of the finish stop of the trip. All names consist of uppercase and lowercase English letters and have lengths between 1 to 20 letters inclusive. Uppercase and lowercase letters should be considered different.

第一行包含五个整数 $n$、$a$、$b$、$k$、$f$（其中 $1 \leq n \leq 300$，$1 \leq b < a \leq 100$，$0 \leq k \leq 300$，$1 \leq f \leq 1000$），其含义如下：

• $n$ — Polycarp 的出行次数；
• $a$ — 普通单程票的费用；
• $b$ — 换乘后单程票的费用；
• $k$ — Polycarp 最多可购买的交通卡数量；
• $f$ — 单张交通卡的费用。

接下来的 $n$ 行按时间顺序描述各次出行。每行恰好包含两个由单个空格分隔的单词 —— 出行的起点站名和终点站名。所有站名均由英文字母（大小写均可）组成，长度为 $1$ 至 $20$ 个字母（含端点）。大小写字母被视为不同字符。

Print the smallest amount of money Polycarp could have spent today, if he can purchase no more than k travel cards.

输出 Polycarp 今天可能花费的最少金额，前提是其最多可购买 k 张交通卡。

In the first example Polycarp can buy travel card for the route "BerBank University" and spend 8 burles. Note that his second trip "University" "BerMall" was made after transshipment, so for this trip Polycarp payed 3 burles. So the minimum total sum equals to 8 + 3 = 11 burles.

In the second example it doesn't make sense to buy travel cards. Note that each of Polycarp trip (except the first) was made with transshipment. So the minimum total sum equals to 2 + 1 + 1 + 1 = 5 burles.

在第一个例子中，Polycarp 可以为路线“BerBank University”购买一张乘车卡，花费 8 burles。注意，他的第二次行程“University” “BerMall”是在换乘后进行的，因此本次行程 Polycarp 支付了 3 burles。故最小总费用为 $8 + 3 = 11$ burles。

在第二个例子中，购买乘车卡并无意义。注意，Polycarp 的每次行程（除第一次外）均涉及换乘。因此最小总费用为 $2 + 1 + 1 + 1 = 5$ burles。