Black and White Stones

Time limit3sMemory limit256 MB

Summary

Shagga reorders black and white stones so all black stones stand left of white ones with minimum cost, paying A per swap and A minus B for adjacent swaps.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, String
Solved: No attempts yet

Problem

Shagga and Dolf play a game with stones. Every stone is either black or white. Dolf opens the game by laying all the stones in one line from left to right, and Shagga then has to reorder them so that every black stone sits to the left of every white stone.

Shagga has exactly one move. He picks two stones of different colors, swaps their positions, and pays Dolf $A$ coins for it. If the two swapped stones were next to each other, Dolf refunds $B$ coins, so that swap costs Shagga only $A - B$ coins.

Shagga has not worked out that he only loses coins by playing this game. He does know that playing well loses fewer coins than his current habit of picking the two stones at random. Find the smallest number of coins Shagga has to pay Dolf to reach an arrangement where every black stone is to the left of every white stone.

Input

The first line contains two integers $A$ and $B$ ( $0 \le B < A \le 10^6$ ). $A$ is the price of one swap and $B$ is the refund for swapping two neighboring stones.

The second line contains a non-empty string $S$ of at most $5000$ characters. The $i$ -th character of $S$ gives the color of the $i$ -th stone from the left in the starting line. The character B marks a black stone and the character W marks a white stone.

Output

Print one integer on a single line: the smallest number of coins Shagga has to pay Dolf to arrange the stones so that every black stone is to the left of every white stone.

Examples3

Example 1
Input
```
2 1
BWWB
```
Expected output
```
2
```
Example 2
Input
```
5 3
WBWWBWBWBWBBBWWBBB
```
Expected output
```
27
```
Example 3
Input
```
1000000 0
W
```
Expected output
```
0
```