Heist 2.0

Era o noapte calmă de noiembrie, iar Parisul dormea sub o ploaie subțire. Doar lumina palidă a felinarelor se oglindea în Sena, tremurând ca o respirație. În umbra muzeului Luvru, un tânăr cu ochi limpezi și pași ușori pășea hotărât: Ciprian, un hoț neobișnuit.

Își spusese mereu că fiecare obiect are o poveste, un loc potrivit. Unele lucruri merită păstrate aproape de inimă, altele pot fi dăruite, împărțite cu lumea. Așa că, în noaptea aceea, Ciprian nu fura la întâmplare, ci alegea cu grijă. De la un colț la altul, printre statui și pânze, aduna amintiri: o mănușă de dantelă dintr-un portret vechi, o cheie ruginită, o bijuterie ascunsă sub praf. Pe fiecare o privea o clipă și o punea în sac.

Dar Ciprian nu era singur. La ieșire îl aștepta Șeful: "Din ceea ce-mi aduci, nimic nu trebuie să semene. Vreau doar lucruri diferite."

Din toate minunile furate, trebuia să aleagă cât mai mult, dar fără să repete nimic. Așa că, pe marginea Senei, la adăpostul unui pod, a început să sorteze. Unele lucruri le-a păstrat, erau prea dragi, prea pline de sens. Altele le-a oferit, fără regret, cu o liniște aproape frumoasă.

Când s-a luminat de ziuă, Parisul s-a trezit fără o bijuterie, dar mai bogat cu o poveste. Ciprian dispăruse, iar în fața muzeului a rămas doar un bilet, scris cu cerneală albastră:

Nu am luat tot ce am putut.
Am luat doar cât era drept.

Se spune că de atunci, în unele nopți de primăvară, când plouă ușor, poți zări o umbră traversând curtea Luvrului. Nu lasă urme, doar o armonie ciudată între ceea ce lipsește și ceea ce rămâne.

Cerință

Sunt $Q$ lovituri (independente) pe care Ciprian (maestru al furtului discret) le dă. Fiecare lovitură este descrisă astfel:

Se dau $N$ obiecte, fiecare obiect având anumite caracteristici. Al $i$-lea obiect are următoarele caracteristici:

• $tip[i]$ reprezintă tipul acestuia (un număr natural);
• $neimportant[i]$ reprezintă dacă Ciprian dorește obiectul ($0$) sau îl poate preda ($1$).

Pentru fiecare tip de obiect, fie acesta $t$, definim:

• $cnt[t]$ câte obiecte de tipul $t$ a strâns;
• $ok[t]$ câte obiecte de tipul $t$ a strâns și pe care le poate preda fără resentimente.

Pentru fiecare tip $t$ se alege o cantitate $give[t]$, unde $0\leq give[t] \leq cnt[t]$, astfel încât toate valorile nenule ale lui $give[t]$ sunt distincte (doar $0$ se poate repeta, în rest trebuie să fie distincte).

Trebuie maximizată suma tuturor elementelor șirului $give$ (numărul total de obiecte predate), pe care o vom nota cu $S$. Dintre toate alegerile cu $S$ maxim se va alege cea care maximizează numărul de obiecte neimportante predate Șefului. Fie această cantitate $P$. $P$ este numărul total de obiecte predate șefului și pe care nu îl deranjează pe Ciprian să le dea (câte obiecte $i$ din cele predate au $neimportant[i] = 1$).

Date de intrare

Fișierul de intrare heist.in conține:

• pe prima linie un număr natural nenul $Q$, cu semnificația din enunț;
• pe următoarele linii pentru fiecare dintre cele $Q$ spargeri pe prima linie $N$, reprezentând numărul de obiecte pe care le fură Ciprian, și pe următoarele $N$ linii câte o pereche de numere natuarale reprezentând $tip[i]$ și $neimportant[i]$.

Date de ieșire

Se vor afișa în fișierul de ieșire heist.out, pe $Q$ linii, perechile $(S,P)$, separate printr-un spațiu, fiecare pereche pe o linie separată, reprezentând răspunsurile pentru cele $Q$ spargeri.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$;
• Suma lui $N$ pe toate cele $Q$ lovituri nu va depăși $200 \ 000$;
• $1 \leq tip[t] \leq N, 1 \leq t \leq N$.

Exemplu

heist.in

5
8
1 0
4 1
2 0
4 1
5 1
6 1
3 0
2 0
4
1 1
1 1
2 1
2 1
9
2 0
2 0
4 1
4 1
4 1
7 0
7 1
7 0
7 1
5
1 0
1 0
1 1
2 0
3 1
6
1 0
1 0
1 0
2 1
2 1
3 1

heist.out

3 3
3 3
9 5
4 2
6 3