Se dau N evenimente de forma $(t, usa)$, ceea ce inseamna ca la timpul $t$ trebuie sa fie inchisa usa respectiva (ex: $(7, STANGA)$).

Usile sunt vechi asa ca dupa ce o usa a fost inchisa, ea va ramane inchisa cel putin $d$ secunde. De asemenea, o singura usa poate fi inchisa la un moment dat (exceptie momentul cand se deschide o usa si se inchide cealalta - clarificare in primul exemplu).

Usile sunt vechi asa ca dupa ce o usa a fost inchisa, ea va ramane inchisa cel putin $d$ secunde. De asemenea, o singura usa poate fi inchisa la un moment dat.

Gasiti timpul total minim in care usile vor sta inchise daca Georgel joaca optim.

* $1 ≤ T ≤ 30$
* $1 ≤ N ≤ 2 * 10^5^$
* $1 ≤ t, D ≤ 10^9^$

* Evenimentele vor fi date in ordine cronologica.

h2. Exemplu

3 3
1 S
4 S

4 D

5 D

3 4
6 S
8 D