Rodzina surykatek składająca się z $N$ surykatek żyje w grupie. W ciągu dnia surykatki wychodzą z nory, aby pełnić wartę na jednowymiarowej osi współrzędnych w celu obrony przed drapieżnikami. Każda surykatka, pełniąc wartę, ma określoną swoją pozycję oraz kierunek, w którym patrzy – w lewo lub w prawo – i nie może zmienić kierunku podczas warty.

Wszystkie surykatki w rodzinie mają różne wzrosty. Surykatka nie widzi (nie może obserwować) jeśli w kierunku, w którym patrzy, znajduje się wyższa surykatka. Litując się nad nimi, możesz niezauważenie przez rodzinę dowolnie wykonywać następującą operację:

• Wybierz dwie surykatki patrzące w tym samym kierunku i zamień je miejscami.

Oblicz maksymalną liczbę surykatek, które mogą widzieć (obserwować) po odpowiednim wykonaniu powyższych operacji.

Wejście

W pierwszym wierszu podana jest liczba surykatek $N$. ($3 \leq N \leq 5\,000$)

W kolejnych $N$ wierszach podane są informacje o surykatkach. Dla każdego $1 \leq i \leq N$, w $(i+1)$-szym wierszu znajdują się: liczba całkowita $A_i$ oznaczająca wzrost surykatki znajdującej się na $i$-tej pozycji od lewej oraz znak $D_i$ oznaczający kierunek, w którym patrzy, oddzielone spacją. ($1 \leq A_i \leq N$) $D_i$ to L, jeśli patrzy w lewo, lub R, jeśli patrzy w prawo.

Wszystkie wartości $A_i$ są parami różne.

Wyjście

W pierwszym wierszu wypisz maksymalną liczbę surykatek, które mogą widzieć.

Przykład

Wejście 1

5
5 L
2 R
3 R
4 R
1 L

Wyjście 1

4

Wejście 2

7
7 R
1 L
6 R
3 L
5 L
4 R
2 R

Wyjście 2

4