문자메시지

다음과 같은 휴대폰 숫자 자판으로 영어 메시지를 입력하려고 한다. 각 숫자 버튼에는 아래 문자가 차례대로 배정되어 있다.

하나의 문자를 입력하려면 해당 문자가 나올 때까지 같은 버튼을 누른다. 예를 들어 2번 버튼을 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 C가 입력된다.

이전 문자와 다음 문자가 같은 버튼에 배정되어 있으면, 다음 문자를 입력하기 전에 w만큼 기다려야 한다. 예를 들어 A 다음에 C를 입력하려면 2번 버튼을 다시 누르기 전에 기다려야 한다. 단, 공백을 연속으로 입력할 때는 기다리지 않는다.

버튼을 한 번 누르는 데 걸리는 시간이 p일 때, 주어진 메시지를 입력하는 데 필요한 최소 시간을 구하라.

첫째 줄에 p와 w가 주어진다. (1 ≤ p, w ≤ 1,000) p는 버튼을 한 번 누르는 데 걸리는 시간이고, w는 같은 버튼을 연속해서 사용해야 할 때 기다리는 시간이다.

둘째 줄에 입력할 메시지가 주어진다. 메시지의 길이는 1000보다 작고, 맨 앞과 맨 뒤에는 공백이 없다. 메시지는 알파벳 대문자와 공백으로만 이루어진다.

메시지를 입력하는 데 걸리는 최소 시간을 한 줄에 출력한다.