CF847K Travel Cards

傍晚时分，Polycarp 决定分析一下他今天在公共交通上的出行支出。 Berland 首都的公交系统设置如下：每辆公交车只在两个车站之间运行，中间没有任何停靠点。因此，每辆公交车总是在这两个站点之间往返运行。任意一对站点之间至多有一辆公交车运行。 Polycarp 今天共乘坐了 $n$ 次公交。对于每次乘车，都已知他开始和结束的车站。Polycarp 的记录按时间顺序排列。 已知每乘坐一次公交需花费 $a$ 布尔币。如果乘客进行“换乘”，则该次乘车费用降低为 $b$ 布尔币（$b

第一行包含五个整数 $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$ —— 最多可购买的交通卡数量； - $f$ —— 单张交通卡的价格。 接下来的 $n$ 行，按顺序描述每次乘车。每行两个不同单词，分别表示出发站和到达站，两词以一个空格隔开。所有站名只由大小写拉丁字母组成，长度为 $1$ 到 $20$。需区分大小写。

输出 Polycarp 今天最小可能支出的总金额。

在第一个样例中，Polycarp 可为 "BerBank $\leftrightarrow$ University" 购一张交通卡，支出 $8$ 布尔币。注意他第二次出行 "University $\to$ BerMall" 为换乘，因此花费 $3$ 布尔币。故最小总支出为 $8+3=11$ 布尔币。 在第二个样例中，不买交通卡更优。注意除了第一次，每次均为换乘，因此最小总支出为 $2+1+1+1=5$ 布尔币。 由 ChatGPT 5 翻译