Echipe

Avem $N$ oameni care vor să participe la ICPC. O echipă este întotdeauna formată din trei concurenți și un antrenor. Cum ni se pare OK să judecăm oamenii după aparență, ne vom uita la ei și vom spune despre fiecare dacă are sau nu următoarele trei abilități:

• Este bun la ciucuieli
• Este bun la informatică
• Este bun la matematică

Știm că un om care vrea să participe la ICPC are cel puțin una dintre cele $3$ abilități menționate. În același timp, un om poate să stăpânească mai multe sau chiar toate aceste abilități.

Chiar dacă un om este priceput la mai multe lucruri atunci când se alătură unei echipe, trebuie să declare abilitatea pe care se va concentra în timpul concursului. Astfel că pe lângă atuul ales, nu se va mai ține cont de celelalte abilități pe care le are.

Se știe că în orice echipă este nevoie de cel puțin un om bun la mate, unul bun la info și unul care să știe să scrie ciucuieli. În același timp prea multă ciucuială poate să strice, deci putem să formăm echipe de doar două tipuri:

• Echipă cu $2$ oameni buni la informatică, un om bun la matematică și un om care știe să scrie ciucuieli.
• Echipă cu $2$ oameni buni la matematică, un om bun la informatică și un om care știe să scrie ciucuieli.

De menționat că un om poate face parte dintr-o singură echipă și există posibilitatea ca nu toți oameni să-și găsească echipă și să participe la ICPC.

Fiindcă sunt și ei oameni, pe lângă abilitățile lor intelectuale mai știm pentru fiecare dintre ei care este factorul de risc $X$ de a se certa cu coechipierii în timpul probei.

Vrem să formăm un număr maxim de echipe, astfel încât să respecte unul din cele două tipuri acceptate iar suma factorilor de risc sa fie minima pentru a micșora șansele de ceartă între concurenți. (Degeaba se pricep dacă se ceartă între ei).

Din păcate sau din fericire, în viață, oamenii se mai și schimbă, așa că vom avea și $Q$ update-uri care schimbă factorul de risc al unui om. După fiecare update, vrem să recalculăm factorul total de risc minim ce se poate obține date fiind noile condiții. Aceste update-uri rămân valabile până la final (sunt persistente).

Pentru a calcula factorul total de risc, facem suma factorilor de risc a tuturor membrilor ce au fost selectați să participe în cadrul unei echipe.

Cerință

Se dă $N$ și, pentru fiecare om, care dintre cele 3 categorii face parte, dar și factorul său de risc. Se dau și $Q$ și $Q$ update uri de forma $(i, X_i)$, unde $i$ este indicele omului și $X_i$ este noul său factor de risc. Se cere pentru starea inițială dar și pentru toate stările de după fiecare update să se calculeze numărul maxim de echipe ce se pot forma și riscul total minim necesar. La momentul fiecarui update rămân valabile toate update-urile până în acel moment.

Date de intrare

Pe prima linie a intrării se va afla un singur număr natural întreg $N$ reprezentând numărul de oameni.
Pe următoarele $N$ linii, se vor afla câte un șir binar de lungime exact $3$ cu semnificația:

• Dacă primul caracter este $1$ atunci omul este considerat bun la scris ciucuieli.
• Dacă al doilea caracter este $1$ atunci omul este considerat bun la matematică
• Dacă al treilea caracter este $1$ atunci omul este considerat bun la informatică

Pe aceeași linie separat de un spațiu de șirul binar se va afla un număr natural $X_i$ reprezentând factorul de risc al persoanei $i$. Persoanele sunt indexate de la $1$ la $N$ în ordinea dată, astfel persoana descrisă pe rândul $2$ al intrării este persoana cu indicele $1$ și așa mai departe.

Pe linia $N+2$ se află un singur număr natural $Q$ reprezentând numărul total de update-uri în urma cărora trebuie recalculat factorul de risc.

Pe următoarele $Q$ linii se vor afla două numere naturale separate printr-un spațiu: $i$ reprezentând indicele persoanei ce își va schimba factorul de risc și $X_i$ reprezentând noul factor de risc al persoanei $i$ (persoanele sunt numerotate de la $1$ în ordinea dată).

Date de ieșire

Prima linie va conține răspunsul calculat pentru datele inițiale înainte de orice update și se va afișa numărul maxim de echipe ce poate fi format și riscul total minim.

Pe următoarele $Q$ linii se va afișa riscul total minim recalculat după fiecare update. La momentul fiecarui update se ține cont de toate update-urile anterioare.

Restricții și precizări

• $1 \leq N, Q \leq 150 \ 000$.
• $1 \leq X_i \leq 1 \ 000 \ 000 \ 000$

Exemplu

stdin

6
101 3
110 2
100 4
010 2
111 99
100 6
3
3 100
3 4
5 1

stdout

1 11
13
11
8

Explicație

Se va formă o singură echipa. Puteam să îl alegem pe omul cu numărul $5$, dar acesta avea, fără vreun motiv aparent, trei sfori la el în momentul chestionării, motiv pentru că i s-a atribuit gradul de risc $99$. Prin urmare, echipa va fi formată din oamenii $1$, $2$, $3$ și $4$. După primul update, echipa va fi formată din oamenii $1$, $2$, $4$ și $6$. După al doilea update, revenim la starea inițala. După ultimul update, echipa va fi formată din $1$, $2$, $4$ și $5$.