여행 카드

저녁에 Polycarp는 오늘 대중교통을 이용하며 쓴 교통비를 분석하기로 했다.

Berland 수도의 버스 체계에서는 각 버스가 두 정류장 사이의 노선을 따라 운행한다. 각 버스에는 중간 정류장이 없다. 따라서 각 버스는 한 정류장에서 다른 정류장으로 갔다가 돌아오는 노선을 계속해서 운행한다. 한 쌍의 정류장 사이를 운행하는 버스는 최대 하나이다.

Polycarp는 버스로 n번 이동했다. 각 이동에 대해 출발한 정류장과 도착한 정류장이 알려져 있다. Polycarp의 기록에는 이동이 시간순으로 나열되어 있다.

어떤 버스든 한 번 이용하는 데 a burles가 든다고 알려져 있다. 승객이 환승하면 이동 비용은 b burles로 감소한다 (b < a). 승객이 버스에 타는 정류장이 이전 버스에서 내린 정류장과 일치하면 환승한 것이다. 당연히 첫 번째 이동에서는 환승할 수 없다.

예를 들어 Polycarp가 연속해서 세 번, "BerBank"에서 "University"까지, "University"에서 "BerMall"까지, "University"에서 "BerBank"까지 이동했다면, 그는 a + b + a = 2a + b burles를 지불했다. 그는 BerBank에서 University에 도착하여 다른 버스로 환승한 뒤 BerMall로 출발했다. 그런 다음 University까지 걸어가서 버스를 타고 BerBank로 돌아왔다.

또한 Polycarp는 여행 카드를 최대 k장 살 수 있다. 각 여행 카드의 가격은 f burles이다. 한 버스 노선용 여행 카드를 사용하면 그 노선의 모든 이동을 양방향 모두 무료로 할 수 있다. 한 번 구매한 여행 카드는 어느 방향으로든 몇 번이든 사용할 수 있다.

Polycarp가 여행 카드를 최대 k장 살 수 있을 때, 오늘 지출할 수 있었던 최소 금액은 얼마인가?

첫 번째 줄에는 다섯 정수 n, a, b, k, f (1 ≤ n ≤ 300, 1 ≤ b < a ≤ 100, 0 ≤ k ≤ 300, 1 ≤ f ≤ 1000)가 주어진다. 각 값의 의미는 다음과 같다.

• n — Polycarp가 이동한 횟수,
• a — 일반적인 한 번의 이동 비용,
• b — 환승 후 이동 비용,
• k — Polycarp가 살 수 있는 여행 카드의 최대 개수,
• f — 여행 카드 한 장의 가격.

이어지는 n개의 줄에는 이동이 시간순으로 주어진다. 각 줄에는 정확히 하나의 공백으로 구분된 서로 다른 두 단어, 즉 이동을 시작한 정류장의 이름과 이동을 마친 정류장의 이름이 주어진다. 모든 이름은 영문 대문자와 소문자로만 이루어지며 길이는 1 이상 20 이하이다. 대문자와 소문자는 서로 다른 것으로 간주해야 한다.

Polycarp가 여행 카드를 최대 k장 구매할 수 있을 때, 오늘 지출할 수 있었던 최소 금액을 출력한다.

첫 번째 예제에서 Polycarp는 "BerBank University" 노선의 여행 카드를 사서 8 burles를 쓸 수 있다. 그의 두 번째 이동인 "University"에서 "BerMall"까지의 이동은 환승 후에 이루어졌으므로, Polycarp는 이 이동에 3 burles를 지불했다. 따라서 최소 총액은 8 + 3 = 11 burles이다.

두 번째 예제에서는 여행 카드를 사는 것이 의미가 없다. Polycarp의 이동은 첫 번째를 제외하고 모두 환승으로 이루어졌다는 점에 유의하라. 따라서 최소 총액은 2 + 1 + 1 + 1 = 5 burles이다.