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.

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\le s\le 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$.

50 2000
ready room

3450

50 1000
a yummy test.

3550

100 800
hej, verden.

3700

50 1000
le

1050

50 500
le

600