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
Na wyjściu powinna pojawić się się jedna liczba całkowita, oznaczająca minimalny czas
potrzebny do uzyskania tekstu, który czytany zarówno od lewej jak i od prawej będzie taki sam.
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).