Problem description

Na pręcie długości L umieszczono N robaków w różnych pozycjach tego pręta. Dla każdego robaka znamy jego kierunek początkowy (w kierunku lewego lub prawego końca pręta). Każdy robak porusza się z tą samą prędkością.

Gdy dwa robaki spotkają się na pręcie w tym samym miejscu, w mgnieniu oka zmieniają kierunki podróży na przeciwne (tak jakby się od siebie odbijały). Robaki są też dość głupie i gdy dojdą do końca (prawego lub lewego) pręta, będąc skierowanym w stronę tego końca spadają z niego (i giną, bo pręt jest wysoko nad ziemią). Zwróć uwagę, że robak na końcu pręta nie spadnie z niego jeśli jest skierowany w drugą stronę.

Napisz program, który: wczyta długość pręta i pozycje robaków na pręcie, wyznaczy po jakim czasie zginą wszystkie robaki i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i L, oddzielone pojedynczym odstępem i określające kolejno: liczbę robaków oraz długość pręta.

W kolejnych N wierszach znajdują się opisy kolejnych robaków. Opis każdego robaka składa się z jednej liczby A_i, określającej jego początkową pozycję (odległość od lewego końca pręta), pojedynczego odstępu oraz jednej litery L lub P, określającej początkowy kierunek ruchu i-tego robaka: odpowiednio w stronę lewego końca pręta i prawego końca pręta.

Możesz założyć, że robaki pokonują jedną jednostkę długości w tempie jednej sekundy. Możesz założyć, że początkowe pozycje robaków są parami różne.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – czas (w sekundach), po którym ostatni robak spadnie z pręta.

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ L ≤ 10⁹, 0 ≤ A_i ≤ L.

W testach wartych łącznie 50% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 5 000.

Przykład

3 10
4 P
5 L
6 P

6

2 5
3 L
2 P

3

2 10
0 L
10 L

10