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" $\rightarrow$ "University", "University" $\rightarrow$ "BerMall", "University" $\rightarrow$ "BerBank", then he payed a + b + a = 2a + 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.


-----Examples-----
Input
3 5 3 1 8
BerBank University
University BerMall
University BerBank

Output
11

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

Output
5



-----Note-----

In the first example Polycarp can buy travel card for the route "BerBank $\leftrightarrow$ University" and spend 8 burles. Note that his second trip "University" $\rightarrow$ "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.

Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
def main():
	(trips, reg, cheap, cards, card_cost) = list(map(int, input().split()))
	costs = []
	indexes = {}
	total = 0
	last = ''
	for i in range(trips):
		(a, b) = input().split()
		pair = (min(a, b), max(a, b))
		if pair in indexes:
			index = indexes[pair]
		else:
			costs.append(0)
			indexes[pair] = len(costs) - 1
			index = len(costs) - 1
		total += cheap if a == last else reg
		costs[index] += cheap if a == last else reg
		last = b
	costs = sorted(costs, reverse=True)
	for c in costs:
		if c < card_cost or cards <= 0:
			break
		total -= c
		total += card_cost
		cards -= 1
	print(total)
main()


(n, a, b, k, f) = [int(i) for i in input().split()]
stops = dict()
prev = ''
ans = 0
for i in range(n):
	(x, y) = [i for i in input().split()]
	price = a
	if x == prev:
		price = b
	prev = y
	(p, q) = (min(x, y), max(x, y))
	if (p, q) in stops:
		stops[p, q] += price
	else:
		stops[p, q] = price
	ans += price
edge_cost = sorted([stops[key] for key in stops], reverse=True)
for i in edge_cost:
	if k > 0 and f < i:
		ans = ans - i + f
	else:
		break
	k -= 1
print(ans)


(n, a, b, k, f) = list(map(int, input().split()))
totalCost = {}
lastStop = ''
total = 0
for i in range(n):
	(s1, s2) = input().split()
	cost = a if lastStop != s1 else b
	key = (min(s1, s2), max(s1, s2))
	if key not in totalCost:
		totalCost[key] = cost
	else:
		totalCost[key] += cost
	total += cost
	lastStop = s2
sortedTotalCost = [(totalCost[key], key[0], key[1]) for key in totalCost]
sortedTotalCost.sort(reverse=True)
i = 0
while i < len(sortedTotalCost) and k > 0 and (sortedTotalCost[i][0] > f):
	total -= sortedTotalCost[i][0]
	total += f
	k -= 1
	i += 1
print(total)


(n, a, b, k, f) = map(int, input().split())
slov = dict()
temp = input().split()
slov[frozenset(temp)] = a
for i in range(1, n):
	temp2 = input().split()
	try:
		if temp2[0] == temp[1]:
			slov[frozenset(temp2)] += b
		else:
			slov[frozenset(temp2)] += a
	except KeyError:
		if temp2[0] == temp[1]:
			slov[frozenset(temp2)] = b
		else:
			slov[frozenset(temp2)] = a
	temp = temp2
costs = sorted(list(slov.values()), reverse=True)
for i in range(min(k, len(costs))):
	if costs[i] > f:
		costs[i] = f
	else:
		break
print(sum(costs))


(n, a, b, k, f) = [int(i) for i in input().split()]
pred = '_'
d = dict()
for i in range(n):
	(s1, s2) = [i for i in input().split()]
	pr = a
	if s1 == pred:
		pr = b
	if (s1, s2) in list(d.keys()):
		d[s1, s2] += pr
	elif (s2, s1) in list(d.keys()):
		d[s2, s1] += pr
	else:
		d[s1, s2] = pr
	pred = s2
cn = k
ans = sum(d.values())
for i in sorted(list(d.values()), reverse=True):
	if cn == 0 or i <= f:
		break
	ans = ans - i + f
	cn -= 1
print(ans)


import heapq
import sys
(num_trips, a, b, k, f) = sys.stdin.readline().strip().split(' ')
(a, b, k, f) = (int(a), int(b), int(k), int(f))
trips = []
for line in sys.stdin:
	trips.append(line.strip().split(' '))
my_dict = dict()
for i in range(0, len(trips)):
	trip = trips[i]
	cost = 0
	if i - 1 >= 0 and trips[i - 1][1] == trip[0]:
		cost = b
	else:
		cost = a
	if str(sorted(trip)) in my_dict:
		my_dict[str(sorted(trip))] += cost
	else:
		my_dict[str(sorted(trip))] = cost
heap = [(-1 * my_dict[x], x) for x in my_dict]
heapq.heapify(heap)
total = sum((int(my_dict[x]) for x in my_dict))
for i in range(0, k):
	if len(heap) > 0:
		cur_max = int(heapq.heappop(heap)[0]) * -1
		if cur_max > f:
			total = total - (cur_max - f)
print(total)