== include(page="template/taskheader" task_id="fnaf") ==
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 o inchizi ca sa te aperi. Insa resursele sunt limitate si nu poti tine usile inchise tot timpul.
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 te 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)).
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 (exceptie momentul cand se deschide o usa si se inchide cealalta - clarificare in primul exemplu).
Gasiti timpul total minim in care usile vor sta inchise daca Georgel joaca optim.
h2. Date de intrare
Fişierul de intrare $fnaf.in$ ...
Fişierul de intrare $fnaf.in$ va contine pe prima linie un numar intreg $T$ reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se vor afla doua numere intregi $N$ si $d$, reprezentand numarul de evenimente si durata minima pentru care trebuie sa stea inchisa o usa; pe fiecare dintre urmatoarele $N$ linii se va afla descrierea unui eveniment $(t, usa)$, numarul intreg $t$ fiind timpul la care se intampla evenimentul si caracterul $usa$ care reprezinta partea din care vine monstrul ($S$ pentru stanga, $D$ pentru dreapta).
h2. Date de ieşire
În fişierul de ieşire $fnaf.out$ ...
În fişierul de ieşire $fnaf.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru un test consta intr-un singur rand pe care se va afla numarul maxim de minioni adversi care pot fi omorati de minionul lui Georgel, fara ca acesta sa moara.
În fişierul de ieşire $hsattack.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru un test consta intr-un singur rand pe care se va afla timpul total minim in care usile vor sta inchise daca Georgel joaca optim.
h2. Restricţii
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 10^6^$
* $1 ≤ t, D ≤ 10^9^$
