URI Online Judge | 1744

Pedras Pretas e Brancas

Por Fidel I. Schaposnik Massolo, Universidad Nacional de La Plata AR Argentina

Timelimit: 1

Shagga e Dolf gostam de jogar um jogo com pedras, cada uma das quais é preto ou branco. No início do jogo, Dolf organiza todas as pedras em uma única linha, da esquerda para a direita. Então, o objetivo da Shagga é reordenar as pedras para que todas as pedras pretas fiquem à esquerda de todas as pedras brancas. Para fazer isso, ele pode escolher qualquer par de pedras de cor diferente e trocar as suas posições, pagando A moedas para Dolf no processo. No entanto, se as duas pedras cujas posições que ele está trocando são adjacentes, Dolf deve dar-lhe um reembolso de B moedas, o que significa que a operação vai custar a Shagga apenas A - B moedas.

Shagga não é muito esperto, por isso ele ainda não percebeu que ele só vai perder moedas ao jogar este jogo. No entanto, ele está consciente de suas limitações, então ele sabe que, se ele jogar de forma ótima ele perderá menos moedas do que ele está perdendo agora, com sua estratégia de escolher aleatoriamente as pedras que ele troca a cada movimento. Por isso, ele quer saber o número mínimo de moedas que ele terá que pagar a Dolf, a fim de chegar a ordenação desejada das pedras, e ele está ameaçando a te dar de alimento as cabras, se você não ajudá-lo.

Entrada

A primeira linha contém dois inteiros A e B (0 ≤ B <A ≤ 106), que representam, respectivamente, o custo da troca de duas pedras e o valor da restituição ao trocar pedras adjacentes. A segunda linha contém uma string não-vazia S de, no máximo, 5.000 caracteres. O i-ésimo caracter de S indica a cor da i-ésima pedra, a partir da esquerda para a direita, no arranjo inicial das pedras. O caracter é a letra maiúscula "B" ou a letra maiúscula "W", indicando, respectivamente, uma pedra preta ou uma pedra branca.

Saída

Imprima uma linha contendo um inteiro que representa o número mínimo de moedas que Shagga terá que pagar a Dolf para ordernar as pedras de tal forma que todas as pedras pretas estejam à esquerda de todas as pedras brancas.

Exemplos de Entrada Exemplos de Saída

2 1
BWWB

2

5 3
WBWWBWBWBWBBBWWBBB

27

1000000 0
W

0