고속도로

도로는 왼쪽에서 오른쪽으로 이어지는 N개의 단위 구간으로 이루어져 있다. 각 구간에서 도로는 같은 높이를 유지하거나, 높이가 1 올라가거나, 높이가 1 내려간다.

자동차가 원래 도로의 한 단위 구간을 지나는 데 걸리는 시간은 다음과 같다.

• 높이가 그대로인 구간: A초
• 높이가 1 올라가거나 내려가는 구간: B초

산 아래에는 터널을, 골짜기 위에는 고가도로를 지을 수 있다. 하나의 구조물은 수평이어야 하며, 어떤 위치에서 시작해 오른쪽으로 처음 다시 같은 높이가 되는 위치까지 이어진다. 자동차가 터널이나 고가도로의 한 단위 길이를 지나는 데에는 C초가 걸린다.

지을 수 있는 구조물의 총 개수는 K개 이하이다. 주어진 지형에서 자동차가 도로 전체를 지나가는 데 필요한 최소 시간을 구하라.

그림은 세 번째 공개 테스트의 상황을 나타낸다. 얇은 선은 원래 도로이고, 굵은 선은 최적 경로이다. 구조물을 최대 2개만 지을 수 있으므로 첫 번째 산 아래에는 터널을 짓지 않는다.

첫째 줄에 정수 A, B, C가 주어진다. 세 값은 각각 1 이상 100 이하이다.

둘째 줄에 정수 N과 K가 주어진다. 1 ≤ N ≤ 30,000, 1 ≤ K ≤ 1,000이다.

셋째 줄에 지형을 왼쪽에서 오른쪽으로 나타내는 길이 N의 문자열이 주어진다. 각 문자의 의미는 다음과 같다.

• D: 다음 단위 구간에서 지형이 높이 1만큼 내려간다.
• R: 다음 단위 구간에서 지형의 높이가 그대로이다.
• G: 다음 단위 구간에서 지형이 높이 1만큼 올라간다.

자동차가 도로 전체를 지나가는 데 필요한 최소 시간을 출력한다.