cho.shTime limit
2s
Memory limit
128 MB
Given the mobile phone numeric keypad below, compute the minimum time needed to type an English message.
| Key | Characters |
|---|---|
| 1 | space |
| 2 | A B C |
| 3 | D E F |
| 4 | G H I |
| 5 | J K L |
| 6 | M N O |
| 7 | P Q R S |
| 8 | T U V |
| 9 | W X Y Z |
To enter one character, press its key until that character appears. For example, pressing key 2 once enters A, twice enters B, and three times enters C.
If two consecutive characters use the same key, you must wait w time units before pressing the key for the second character. For example, typing A followed by C requires a wait before pressing key 2 again. Consecutive spaces are the exception: they do not require waiting.
Each key press takes p time units. Find the minimum time required to type the given message.
The first line contains p and w (1 ≤ p, w ≤ 1,000). Here, p is the time required for one key press, and w is the waiting time required when the same key must be used for consecutive characters.
The second line contains the message to type. Its length is less than 1000, and it has no leading or trailing spaces. The message consists only of uppercase English letters and spaces.
Print one line containing the minimum time required to type the message.