Problem H
Handy Beer
Karl is an blazingly fast typist and always wins the anual speed typing competition at ScrollBar by a wide margin.
This year, he wants to show off even more than usual: he plans to win while holding a beer. Of course, holding a beer will slow him down quite a bit, as he can only type with the free hand. Karl can reach all the keys preferred by the given hand in normal QWERTY touch typing at his normal (blazingly fast) speed. But when reaching over to the other hand’s domain, his speed deteriorates to one keystroke per second. The space bar can be reached (blazingly fast) with either hand.
![\includegraphics[width=.5\textwidth ]{img/qwerty.pdf}](/problems/handybeer/file/statement/en/img-0002.png)
At any point in time, Karl can swap the beer over to his other hand, but that will take a little bit of time. Karl can choose which hand the beer starts in.
Input
The first line contains two integers, $t$ and $s$, with $0<t<1000$ and $500\leq s \leq 5000$. The (blazingly fast) typing speed $t$ is how many milliseconds it takes Karl to type one character with the preferred hand. The swapping speed $s$ is how many milliseconds it takes to swap the beer between hands.
The second line contains the text that Karl must type. The text consists of at least $1$ and at most $1000$ characters, all lower case letters a–z as well as space, comma, and period. The newline character at the end is not part of the text.
Output
A single integer: the shortest possible time for Karl to finish typing the given text, in milliseconds.
Sample 1 explanation
There are two optimal ways for Karl to type “ready room” within $3450$ ms.
First way: touch type “read”, swap the beer over, touch type “y ”, reach over and slow type “r”, and touch type “oom”. Total time: $50 + 50 + 50 + 50 + 2000 + 50 + 50 + 1000 + 50 + 50 + 50 = 3450$.
Second way: touch type “read”, reach over and slow type “y”, touch type “ r”, swap the beer over, and touch type “oom”. Total time: $50 + 50 + 50 + 50 + 1000 + 50 + 50 + 2000 + 50 + 50 + 50 = 3450$.
| Sample Input 1 | Sample Output 1 |
|---|---|
50 2000 ready room |
3450 |
| Sample Input 2 | Sample Output 2 |
|---|---|
50 1000 a yummy test. |
3550 |
| Sample Input 3 | Sample Output 3 |
|---|---|
100 800 hej, verden. |
3700 |
| Sample Input 4 | Sample Output 4 |
|---|---|
50 1000 le |
1050 |
| Sample Input 5 | Sample Output 5 |
|---|---|
50 500 le |
600 |
