Zadanie

Extrémne masívne zadanie

Počet bodov: 35,

Merlin a Duško sú udatní bojovníci, ktorí už skolili veľa príšer. Keď zabíjajú nejakú príšeru, tá pri tom hrozne kričí, z čoho potom bojovníkom píska v ušiach. Najhoršie je, že výkriky príšer sú veľmi komplikované. Bojovníci by chceli, aby príšera radšej kričala proste len AAAAAAAAAAAAAAAAA…. Používajú preto špeciálne zbrane - keď Merlin príšeru dingne svojím mečom, vie zmeniť vo výkriku príšery jeden konkrétny výskyt písmena na ľubovoľné iné. Dongnutím kladiva si zas Duško vie vybrať nejaké písmeno z výkriku a všetky jeho výskyty posunie o 1 smerom k A.

Bojovníkov ich útoky stoja rôznu energiu a na zabitie príšery jej chcú dokopy minúť čo najmenej. Pomôžte vymyslieť Merlinovi a Duškovi stratégiu, pri ktorej bude príšera kričať len písmená ‘A’.

Vstup a výstup

Na prvom riadku vstupu sú 2 čísla, množstvo energie spotrebovanej na Ding a Dong.

Na druhom riadku je reťazec tvorený veľkými písmenami anglickej abecedy - aktuálny krik príšery.

Vypíšte jediné číslo - minimálny počet energie minutej na to, aby príšera kričala ‘AAAAAAA…’ - reťazec tvorený len znakmi ‘A’.

Obmedzenia

Ceny dingu a dongu sú kladné celé čísĺa neprevyšujúce \(150\,000\).

Vstupy sú rozdelené do 5 sád, platia pre ne nasledovné obmedzenia na dĺžky kriku príšery: \(10\), \(100\), \(100\), \(100\,000\), \(100\,000\).

Navyše v druhej a štvrtej sade príšera kričí iba písmená ‘A’ a ‘B’.

Pozor, výsledok môže byť pomerne veľké číslo, no vždy sa zmestí do 64-bitovej premennej.

Príklady

Input:

2 4
ZJEMVAS

Output:

12

Najviac sa oplatí aby Merlin dingol všetky písmenká okrem Á-čka

Input:

2 4
BABABABAZ

Output:

6

Merlin dingne Z a Duško dongne všetky B.