Вечером Поликарп решил проанализировать свои сегодняшние расходы на поездки в общественном транспорте.
Автобусная сеть в столице Берляндии устроена таким образом, что каждый автобус курсирует по маршруту между двумя конечными остановками. Промежуточных остановок у автобуса нет. Таким образом, каждый из автобусов непрерывно курсирует по маршруту от одной конечной остановки до другой и назад. Между парой остановок курсирует не более одного автобуса.
Поликарп совершил n поездок на автобусе, каждая из которых задается названием остановки, откуда он уехал, и названием остановки, куда он приехал. В записях Поликарпа поездки следуют в хронологическом порядке.
Известно, что одна поездка на автобусе любого маршрута стоит a бурлей. Однако, если пассажир совершает пересадку, то цена поездки уменьшается до b бурлей (b < a). Считается, что пассажир совершает пересадку, если остановка, на которой он садится в автобус, совпадает с остановкой, на которой он вышел из предыдущего автобуса. Очевидно, что первая поездка не может быть совершена после пересадки.
Например, если Поликарп совершил последовательно три поездки: «BerBank» 
«University», «University» «BerMall», «University» «BerBank», то он заплатит a + b + a = 2a + b бурлей. Из BerBank он приехал в University, там пересел и поехал в BerMall. Затем он прошёл пешком до University и вернулся в BerBank.
Поликарп мог купить не более чем k проездных по цене f бурлей за один проездной. Проездной покупается для одного автобусного маршрута и делает любую поездку по этому маршруту (в любом направлении) бесплатной. Единожды купленный проездной может использоваться неограниченное количество раз любом из двух направлений.
Какую наименьшую сумму денег мог потратить Поликарп сегодня, если бы приобрел не более k проездных оптимальным образом?
В первой строке записаны пять целых чисел n, a, b, k, f (1 ≤ n ≤ 300, 1 ≤ b < a ≤ 100, 0 ≤ k ≤ 300, 1 ≤ f ≤ 1000), где:
- n — количество поездок Поликарпа,
- a — цена одной обычной поездки,
- b — цена одной поездки после пересадки,
- k — максимальное количество проездных,
- f — цена одного проездного.
Далее следуют n строк, описывающие поездки в порядке их совершения. Каждая строка содержит ровно два различных слова, разделенных единичным пробелом — название стартовой остановки и название финальной остановки для очередной поездки Поликарпа. Все названия состоят из прописных и строчных букв латинского алфавита, содержат от 1 до 20 букв. Прописные и строчные буквы следует считать различными.
Выведите наименьшую сумму денег, которую Поликарп мог потратить сегодня, если бы приобрел не более k проездных оптимальным образом.
3 5 3 1 8
BerBank University
University BerMall
University BerBank
11
4 2 1 300 1000
a A
A aa
aa AA
AA a
5
В первом примере Поликарп может купить проездной на маршрут «BerBank 
University», потратив 8 бурлей. Заметим, что его вторая поездка «University» «BerMall» совершается после пересадки; следовательно, за эту поездку он заплатит 3 бурля. Таким образом, искомая сумма денег равна 8 + 3 = 11 бурлей.
Во втором примере Поликарпу невыгодно покупать проездные. Заметим, что каждая его поездка, кроме первой, совершена после пересадки. Следовательно, искомая сумма денег равна 2 + 1 + 1 + 1 = 5 бурлей.
