English · Original
Chinese · Translation
Formal · Original
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?
## Input
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.
## Output
Print the smallest amount of money Polycarp could have spent today, if he can purchase no more than _k_ travel cards.
[samples]
## Note
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 决定分析他今天乘坐公共交通工具的出行费用。
Berland 首都的公交系统设计如下：每辆公交车在两个站点之间沿固定路线运行，且没有中间停靠站。因此，每辆公交车在两个站点之间往返不停歇。任意两个站点之间至多有一辆公交车运行。
Polycarp 乘坐了 #cf_span[n] 次公交车。对于每次出行，已知他上车的站点和下车的站点。这些出行按 Polycarp 笔记中的时间顺序排列。
已知乘坐任何一辆公交车的单次票价为 #cf_span[a] 卢布。如果乘客在上车站点与前一次下车站点相同，则可享受换乘优惠，票价降为 #cf_span[b] 卢布（#cf_span[b < a]）。当乘客上车的站点与前一次下车的站点相同时，即视为换乘。显然，第一次出行不可能是换乘。
例如，如果 Polycarp 连续进行了三次出行："BerBank" → "University"，"University" → "BerMall"，"University" → "BerBank"，那么他支付了 #cf_span[a + b + a = 2a + b] 卢布。他从 BerBank 到达 University，在那里换乘另一辆公交车前往 BerMall；然后他步行回到 University，再乘公交车返回 BerBank。
此外，Polycarp 可以购买不超过 #cf_span[k] 张交通卡。每张交通卡售价为 #cf_span[f] 卢布。一张交通卡可使某条公交路线（双向）的所有出行免费。一旦购买，该交通卡可无限次用于该路线的任意方向。
如果 Polycarp 最多可购买 #cf_span[k] 张交通卡，他今天最少可能花费多少钱？
第一行包含五个整数 #cf_span[n, a, b, k, f]（#cf_span[1 ≤ n ≤ 300]，#cf_span[1 ≤ b < a ≤ 100]，#cf_span[0 ≤ k ≤ 300]，#cf_span[1 ≤ f ≤ 1000]），其中：
接下来的 #cf_span[n] 行按时间顺序描述每次出行。每行包含两个由单个空格分隔的不同单词——本次出行的起点站和终点站名称。所有名称由大小写英文字母组成，长度在 #cf_span[1] 到 #cf_span[20] 个字母之间（大小写字母视为不同）。
请输出 Polycarp 今天可能花费的最小金额，前提是他最多可购买 #cf_span[k] 张交通卡。
在第一个例子中，Polycarp 可以为路线 "BerBank University" 购买一张交通卡，花费 #cf_span[8] 卢布。注意，他的第二次出行 "University" → "BerMall" 是在换乘后进行的，因此他支付了 #cf_span[3] 卢布。因此最小总花费为 #cf_span[8 + 3 = 11] 卢布。
在第二个例子中，购买交通卡没有意义。注意，Polycarp 的每次出行（除第一次外）都是在换乘后进行的。因此最小总花费为 #cf_span[2 + 1 + 1 + 1 = 5] 卢布。
## Input
第一行包含五个整数 #cf_span[n, a, b, k, f]（#cf_span[1 ≤ n ≤ 300]，#cf_span[1 ≤ b < a ≤ 100]，#cf_span[0 ≤ k ≤ 300]，#cf_span[1 ≤ f ≤ 1000]），其中：
#cf_span[n] — Polycarp 的出行次数，
#cf_span[a] — 普通单次出行的费用，
#cf_span[b] — 换乘后的出行费用，
#cf_span[k] — Polycarp 可购买的交通卡最大数量，
#cf_span[f] — 单张交通卡的费用。
接下来的 #cf_span[n] 行按时间顺序描述每次出行。每行包含两个由单个空格分隔的不同单词——本次出行的起点站和终点站名称。所有名称由大小写英文字母组成，长度在 #cf_span[1] 到 #cf_span[20] 个字母之间（大小写字母视为不同）。
## Output
请输出 Polycarp 今天可能花费的最小金额，前提是他最多可购买 #cf_span[k] 张交通卡。
[samples]
## Note
在第一个例子中，Polycarp 可以为路线 "BerBank University" 购买一张交通卡，花费 #cf_span[8] 卢布。注意，他的第二次出行 "University" → "BerMall" 是在换乘后进行的，因此他支付了 #cf_span[3] 卢布。因此最小总花费为 #cf_span[8 + 3 = 11] 卢布。
在第二个例子中，购买交通卡没有意义。注意，Polycarp 的每次出行（除第一次外）都是在换乘后进行的。因此最小总花费为 #cf_span[2 + 1 + 1 + 1 = 5] 卢布。
**Definitions**
Let $ n, a, b, k, f \in \mathbb{Z} $ be given integers with $ 1 \leq n \leq 300 $, $ 1 \leq b < a \leq 100 $, $ 0 \leq k \leq 300 $, $ 1 \leq f \leq 1000 $.
Let $ T = \{(s_i, e_i) \mid i \in \{1, \dots, n\} \} $ be the sequence of trips, where $ s_i $ and $ e_i $ are strings denoting the start and end stops of the $ i $-th trip.
**Constraints**
1. For each $ i \in \{1, \dots, n\} $, $ s_i \ne e_i $.
2. The cost of trip $ i $ is:
$$
c_i =
\begin{cases}
a & \text{if } i = 1 \text{ or } s_i \ne e_{i-1}, \\
b & \text{if } i > 1 \text{ and } s_i = e_{i-1}.
\end{cases}
$$
3. Each unordered pair $ \{s_i, e_i\} $ defines a unique bus route (undirected).
4. A travel card costs $ f $ burles and makes all trips on a single route (in both directions) free.
5. At most $ k $ travel cards may be purchased.
**Objective**
Minimize the total cost:
$$
\min_{S \subseteq R,\ |S| \leq k} \left( \sum_{i=1}^n c_i - \sum_{r \in S} \text{cost}(r) \right)
$$
where $ R $ is the set of distinct routes (i.e., unordered pairs $ \{s_i, e_i\} $), and $ \text{cost}(r) $ is the total cost of all trips on route $ r $, computed using the transshipment rule above.
API Response (JSON)
{
"problem": {
"name": "K. Travel Cards",
"description": {
"content": "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 betwe",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF847K"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In the evening Polycarp decided to analyze his today's travel expenses on public transport.\n\nThe bus system in the capital of Berland is arranged in such a way that each bus runs along the route betwe...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "晚上，Polycarp 决定分析他今天乘坐公共交通工具的出行费用。\n\nBerland 首都的公交系统设计如下：每辆公交车在两个站点之间沿固定路线运行，且没有中间停靠站。因此，每辆公交车在两个站点之间往返不停歇。任意两个站点之间至多有一辆公交车运行。\n\nPolycarp 乘坐了 #cf_span[n] 次公交车。对于每次出行，已知他上车的站点和下车的站点。这些出行按 Polycarp 笔记中的时间顺...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, a, b, k, f \\in \\mathbb{Z} $ be given integers with $ 1 \\leq n \\leq 300 $, $ 1 \\leq b < a \\leq 100 $, $ 0 \\leq k \\leq 300 $, $ 1 \\leq f \\leq 1000 $. \nLet $ T = \\{(s_i, e_i) ...",
"is_translate": false,
"language": "Formal"
}
]
}