agitatie

O firmă producătoare de software organizează un interviu pentru ocuparea unui post de programator, la care s-au prezentat $N$ candidaţi. Aceştia sunt ordonaţi în funcţie de momentul la care şi-au trimis CV-ul şi numerotaţi cu numere consecutive de la $1$ la $N$. Fiecărui candidat i-a fost realizat în prealabil un profil psihologic şi i s-a determinat nivelul de agitaţie provocat de interviul care urmează să aibă loc, precum şi un sens (crescător sau descrescător) de modificare a acestui nivel. Astfel, la ora la care s-a anunţat începerea interviului (pe care o vom considera momentul $0$), fiecare candidat are un nivel de agitaţie iniţial.

Pentru fiecare unitate de timp după momentul $0$ şi până în momentul în care candidatul este invitat pentru interviu (până atunci el trebuind să aştepte), nivelul său de agitaţie se modifică cu $1$: pentru o parte din candidaţi nivelul creşte cu $1$ unitate, iar pentru ceilalţi nivelul scade cu $1$ unitate. Dacă nivelul de agitaţie a unui candidat ajunge la $0$, din acel moment, pentru fiecare unitate de timp următoare, nivelul de agitaţie va creşte cu $1$ (se schimbă sensul de modificare a nivelului de agitaţie).

Firma va invita candidaţii la interviu în grupuri, în ordinea numerotării (toţi candidaţii având numere de ordine mai mici decât un candidat $K$ vor fi invitaţi într-un grup anterior sau în acelaşi grup cu candidatul $K$).

Înainte de a invita un grup, comisia ce conduce interviul poate decide să aştepte un număr întreg de unităţi de timp (zero sau mai multe). Pentru un grup, durata interviului se consideră neglijabilă (fiecare candidat trebuie doar să răspundă la câteva întrebări de tip grilă). Din momentul în care un candidat este invitat la interviu, nivelul de agitaţie a acestuia rămâne constant. Deoarece firma doreşte ca, indiferent de rezultatul interviului, toţi candidaţii să rămână cu o părere bună, comisia va forma grupurile şi va alege timpii de aşteptare în aşa fel încât suma totală a nivelelor de agitaţie a candidaţilor la sfârşitul interviului să fie minimă.

Cerință

Să se scrie un program care să determine suma totală minimă a nivelelor de agitaţie a candidaţilor la sfârşitul interviului.

Date de intrare

Fişierul de intrare agitatie.in are pe prima linie numărul natural $N$, reprezentând numărul de candidaţi. Pe următoarele N linii se află câte două numere întregi $A$ şi $B$, separate printr-un spaţiu. $A$ reprezintă nivelul iniţial de agitaţie a candidatului, iar $B$ reprezintă sensul de modificare a agitaţiei pentru fiecare unitate de timp în care acesta aşteaptă (dacă $B$ este $1$, atunci nivelul de agitaţie creşte, iar dacă $B$ este $-1$, nivelul de agitaţie scade). Linia $k+1$ din fişier va conţine valorile corespunzătoare candidatului cu numărul $k$.

Date de ieșire

Fişierul de ieşire agitatie.out va conţine pe prima (şi singura) linie suma totală minimă a nivelelor de agitaţie a candidaţilor la sfârşitul interviului.

Restricții și precizări

• $1 \leq N \leq 3 \ 000$
• $1 \leq$ nivelul iniţial de agitaţie a fiecărui candidat $\leq 3 \ 000$

Exemplu

agitatie.in

6
10 1
3 -1
2 -1
1 -1
9 1
6 -1

agitatie.out

23

Explicație

Suma totală minimă este $23$. O posibilă soluţie este următoarea: Se formează $3$ grupuri.

Primul grup este format doar din candidatul $1$ şi aşteaptă $0$ unităţi de timp. Prin urmare, nivelul final de agitaţie a candidatului $1$ va fi $10$.

Al doilea grup va aştepta $2$ unităţi de timp din momentul în care a terminat interviul primul grup (deci va începe interviul la momentul $2$), iar din grup vor face parte candidaţii $2, 3, 4$ şi $5$. Nivelele finale de agitaţie a acestor candidaţi vor fi: $1, 0, 1$ şi $11$.

Observaţi că nivelul de agitaţie a candidatului $4$ a scăzut întâi până la $0$ apoi a crescut la $1$. Al $3$-lea grup va mai aştepta $4$ unităţi de timp (deci va începe interviul la momentul $6$), iar din grup va face parte doar candidatul $6$. Nivelul final de agitaţie a acestuia va fi $0$.