Palindromy

Limit pamięci: 32 MB

Poznajcie Fifusia! To nowy bohater naszych przygód. W przeciwieństwie do Bitusiów, Bajtusiów, Bajtazarów, Bajtków i innych dziwnych typów Fifuś wprost nie znosi informatyki. Natomiast jego życiową misją jest służenie Fifolandii w armii Fifoli. Nie wypadałoby nie wspomnieć, że Fifuś jest bardzo dzielnym żołnierzem i ma ambicje piąć się po szczeblach kariery oficerskiej, aż do stopnia generała. Oh! Już bym zapomniał. Fifolandia jest obecnie w stanie wojny z Wielka Barańską Gogolską Dżamahirijją Ludową. Brygada Fifusia musi przesłać tajne informacje do oddziału, który znajduje się na froncie i walczy z wojskami Wielkej Barańskiej Gogolskiej Dżamahirijji Ludowej. Nie jest to proste zadanie, zwłaszcza jeśli weźmiemy pod uwagę fakt, że brygada Fifusia nie ma najmniejszego pojęcia, jak posługiwać się urządzeniem służącym do przesyłania, które zostało im dostarczone. Jedyne, co wiedzą, to jak wprowadzić do maszyny tekst i to, że po wciśnięciu przycisku wysyłania maszyna bierze pierwszą literę z tekstu, wysyła ją, usuwa i powtarza czynność dopóki są jeszcze jakieś litery we wprowadzonym tekście. Jednakże Fifuś nie wie, czy maszyna wybiera pierwszą literę z lewej, czy prawej strony. Fifuś chce zatem tak zmienić tekst, aby niezależnie czy będzie czytany od prawej do lewej, czy od lewej do prawej, był taki sam.

Tekst długości został już wprowadzony do urządzenia. Na szczęście maszyna umożliwia zmianę tekstu poprzez usuwanie lub dodanie liter, co zajmuje pewną ilość czasu. Dla każdej litery jest określone, ile czasu zajmuje jej dodanie, a ile jej usunięcie. Oddział na froncie może być w niebezpieczeństwie, dlatego należy stwierdzić, kiedy najszybciej będzie można wysłać wiadomość. Spiesz się!

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i (, ). W następnym wierszu znajduje się słowo zawierające znaków, które zostało wprowadzone do urządzenia. Słowo to składa się z małych liter alfabetu angielskiego. Możesz założyć, że dla każdej litery tego słowa będzie podany koszt jej usunięcia oraz dodania.

W następnych wierszach znajduje się znak oraz dwie liczby całkowite i (), oznaczające odpowiednio czas dodania oraz czas usunięcia znaku .

Wyjście

Przykład

Dla danych wejściowych:

3 4
abcb
a 1000 1100
b 350 700
c 200 800

poprawną odpowiedzią jest:

900

Autor zadania: Łukasz Jocz (zapożyczenie).