Državno natjecanje 2014. godine za 3. i 4. razred Srednje Škole - 3. zadatak - 2. dan

U firmi za brzu i kvalitetnu prehranu ‘Gangsta Sushi d.o.o’ radi N radnika označenih redom brojevima od 1 do N. Svaki radni dan je podijeljen na sitne vremenske jedinice koje nazivamo trenutci. Trenutaka u radnom vremenu jednog dana ima točno 10^9 te su redom označeni cijelim brojevima 0, 1, 2, …, 10^9 -1.

Svaki radnik dođe svaki dan na posao u nekom trenutku, ostane na poslu određeni broj trenutaka te nakon toga ode sa posla i više se ne vraća do sljedećeg dana. Marljivost radnika K je prirodni broj koji označavamo s MK te označava razliku između zadnjeg i prvog trenutka u kojima je radnik bio na poslu. Dakle, ako radnik K dođe neki dan na posao u trenutku T onda je toga dana na poslu u točno trenutcima T, T+1, T+2, …., T+MK (uključivo). Marljivost svakog pojedinog radnika je ista svaki dan, ali različiti radnici mogu imati različite marljivosti.

Radnici firme se dijele u dvije grupe: kasnioci i ranioci.

• Kasnioci svaki dan dolaze i odlaze s posla jedan trenutak kasnije nego prethodni dan. Dakle, ako je kasnioc u jednom danu stigao na posao u trenutku T, sljedeći dan će stići u trenutku T+1.
• Ranioci svaki dan dolaze i odlaze s posla jedan trenutak ranije nego prethodni dan. Slično, ako je ranioc u jednom danu stigao na posao u trenutku T, sljedeći dan će stići u trenutku T-1.

Za svakog radnika poznata je njegova marljivost te je li kasnioc ili ranioc. Također, poznato je točno u kojem trenutku je koji radnik došao na posao prvog dana 2014. godine. Zanima nas koliko se najviše radnika nalazilo na poslu u istom trenutku u istom danu tijekom razdoblja od točno D dana koji počinje s prvim danom 2014. godine (i uključuje taj dan).

U ulazu se nalazi P različitih scenarija, napišite program koji će za svaki od njih odrediti taj najveći broj radnika kako je opisano gore.

ULAZNI PODACI

Prvi red ulaza sadrži prirodni broj P (1 ≤ P ≤ 5) - broj scenarija koje je potrebno riješiti. U nastavku slijedi P blokova gdje svaki blok sadrži opis jednog scenarija.

Prvi red svakog bloka sadrži dva prirodna broja N i D (1 ≤ N ≤ 200 000, 1 ≤ D ≤ 1 000 000 000) - broj radnika i broj dana u razdoblju koji nas zanima. U svakom od sljedećih N redova bloka nalaze se podaci o jednom zaposleniku - najprije znak ZK koji označava tip zaposlenika (veliko slovo ‘K’ za kasnioce i veliko slovo ‘R’ za ranioce) te dva cijela broja TK i MK (0 ≤ TK, ≤ 1 000 000 000, 1 ≤ MK ≤ 1 000 000 000), trenutak dolaska na posao prvi dan razdoblja te marljivost zaposlenika.

Napomena: Ulazni podaci bit će takvi da niti jedan zaposlenik neće doći na posao prije trenutka 0 ili ostati na poslu nakon trenutka 10^9 -1 u niti jednom od D dana.

IZLAZNI PODACI

Potrebno je ispisati P redova - rješenja za pojedine scenarije onim redoslijedom kojim dolaze u ulazu.

PRIMJERI TEST PODATAKA

ulaz

3
2 1
K 1 1
K 2 1
2 1
K 1 1
R 4 1
2 2
K 1 1
R 4 1

izlaz

2
1
2

ulaz

1
6 6
K 5 9
R 6 13
R 6 8
R 14 14
K 1 4
R 8 15

izlaz

5

ulaz

3
4 1000
K 1000 1
K 1001 1
R 1005 1
R 1006 1
3 3
R 9 11
K 3 9
R 3 6
3 3
R 6 9
K 5 10
R 8 10

izlaz

3
3
3