Georgel joaca Five Nights at Freddy’s, un joc in care controlezi doua usi. Cand se apropie un monstru de usa stanga sau de cea dreapta, trebuie sa inchizi usa respectiva ca sa il opresti. Insa resursele sunt limitate si nu poti tine usile inchise tot timpul.

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

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, exceptand momentul in care se schimba usa (clarificari in exemplu). Daca *inchidem* o usa la momentul $t$, trebuie sa o tinem *inchisa* pana la momentul $t + d$. Putem sa o *deschidem* la momentul $t + d$ si sa o *inchdem* pe cealalta usa tot la momentul $t + d$.

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 sau specificati daca este imposibila satisfacerea tuturor evenimentelor.

* Intr-un moment de timp poate fi atacata o singura usa (nu se intampla doua evenimente simultan).
* Vor fi cel mult $10^6^$ evenimente in fisierul de intrare.

De revazut:
  cica avem timpi negativi
  treaba ca la timpul t se poate inchide o usa si sa se deschida cealalta
  raspunsul e pe long long
 

h2. Exemplu
table(example). |_. fnaf.in |_. fnaf.out |
|3
3 3

1 D
2 S
4 D

1 S
4 S
5 D

3 4
6 S
8 D

2 10
10 S
25 S

|9

|6

-1
15
|

h3. Explicaţie
*Testul 1*

Inchidem usa dreapta la momentul $-2$ pana la $1$, apoi inchidem usa stanga in intervalul de timp $[1, 4]$ si apoi usa dreapta in intervalul $[4, 7]$.

Usa stanga poate fi inchisa in intervalul de timp $[1,4]$ (satisfacand evenimentele $1$ si $2$) si apoi usa dreapta in intervalul $[5,8]$ (satisfacand evenimentul $3$).

*Testul 2*
E imposibil pentru ca intre primul si ultimul eveniment sunt $3$ secunde si usa trebuie sa stea inchisa cel putin $4$ secunde, asa ca nu putem satisface al doilea eveniment fara sa ratam unul dintre primul sau ultimul eveniment.