시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 326 82 68 28.452%

문제

오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다. (즉, 오른쪽 버튼 같은 것은 없다)

입력

첫째 줄에 p와 w가 주어진다. (1<=p,w<=1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자인 문자를 연속으로 찍기 위해 기다리는 시간을 의미한다. 그리고 둘째 줄에는 적을 문자열이 주어진다. 단, 이 문자열의 길이는 1000보다 작고, 맨 앞에 공백이 들어오는 경우는 없다고 가정하여도 좋다. 문자열은 알파벳 대문자와 띄어쓰기만으로 이루어져 있다.

출력

첫째 줄에 메시지를 적는데 걸리는 시간을 출력한다.

예제 입력

2 10
ABBAS SALAM

예제 출력

72

힌트