Problem description


Kiedy Dostawa?
(D)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Bajtek znalazł w sklepie internetowym wymarzoną koszulkę. Niestety okazało się, że jego rozmiar jest obecnie niedostępny! Nie chcąc przegapić kolejnej dostawy, Bajtek zapisał się na listę oczekujących, dzięki czemu będzie mógł odebrać koszulkę, gdy tylko pojawi się ona w magazynie.

Bajtek nie należy jednak do cierpliwych osób. Postanowił więc napisać do sklepu wiadomość z pytaniem, ile najdłużej będzie musiał czekać na swoją koszulkę.

Pech chciał, że na wiadomość Bajtka musi odpowiedzieć pracownik, który dopiero dziś rozpoczął pracę w sklepie.

Pracownik wie, że każdego dnia do sklepu przyjeżdża dostawa koszulek w jednym z trzech rozmiarów: S, M lub L. Dostawy odbywają się według ustalonego harmonogramu składającego się z N dni, który powtarza się cyklicznie.

Harmonogram jest opisany napisem S długości N. W i-tym dniu cyklu dostarczane są koszulki w rozmiarze Si. Po ostatnim dniu harmonogram rozpoczyna się ponownie od pierwszego dnia.

Pracownik otrzymał harmonogram oraz informację, że Bajtek potrzebuje koszulki w rozmiarze C. Nie zdążył jednak dowiedzieć się, który dzień cyklu właśnie trwa. Wie jedynie, że dzisiejsza dostawa zawiera koszulki w rozmiarze D.

Pomóż pracownikowi odpowiedzieć na wiadomość Bajtka. Wyznacz największą możliwą liczbę dni, które Bajtek będzie musiał czekać na najbliższą dostawę koszulek w rozmiarze C. Przyjmij, że jeśli odpowiedni rozmiar zostanie dostarczony jeszcze dzisiaj, czas oczekiwania wynosi 0 dni.

Wejście

W pierwszym wierszu znajdują się liczba całkowita N oraz dwa znaki C i D. Oznaczają one odpowiednio długość harmonogramu, rozmiar poszukiwany przez Bajtka oraz rozmiar znajdujący się w dzisiejszej dostawie.

W drugim wierszu znajduje się napis S długości N, złożony wyłącznie ze znaków S, M i L. Opisuje on harmonogram dostaw.

Wyjście

Wypisz jedną liczbę całkowitą - największą możliwą liczbę dni oczekiwania na najbliższą dostawę koszulek w rozmiarze C.

Ograniczenia

1 ≤ N ≤ 106, C, D ∈ {S, M, L}, |S| = N, każdy znak napisu S należy do zbioru {S, M, L}, znaki C i D występują w napisie S

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 SN = C 40
2 Bez dodatkowych ograniczeń 60

Przykład

Wejście Wyjście Wyjaśnienie
5 L S
SLLSM
3

Dostawy rozmiaru S znajdują się na pozycjach 0 i 3. Z pozycji 0 do najbliższej dostawy L trzeba czekać 1 dzień. Z pozycji 3 harmonogram prowadzi kolejno przez M, S i L, więc oczekiwanie trwa 3 dni. Większa z tych wartości to 3.

Wejście Wyjście Wyjaśnienie
1 S S
S
0

Jedyna dostawa ma rozmiar S. Poszukiwany rozmiar jest dostarczany dzisiaj, więc czas oczekiwania wynosi 0 dni.

Wejście Wyjście Wyjaśnienie
6 M L
MLSSSL
5

Dostawy rozmiaru L znajdują się na pozycjach 1 i 5. Z pozycji 1 harmonogram prowadzi przez S, S, S, L, a następnie M, więc oczekiwanie trwa 5 dni. Z pozycji 5 dostawa M następuje po 1 dniu. Większa z tych wartości to 5.