== include(page="template/taskheader" task_id="bile5") ==

$N$ prieteni stau în jurul a $N$ urne cu bile. Prietenii şi urnele sunt numerotate cu numere de la $0$ la $N-1$. Fiecare urnă $i (0 ≤ i ≤ N-1)$ conţine $S{~i~}$ bile. Prietenii doresc să extragă bile din urne şi să le pună în buzunare. Datorită aşezării, din urna $i$ pot extrage bile doar prietenii $i$ şi $((i+1) mod N)$. Fiecare prieten $i$ $(0 ≤ i ≤ N-1)$ are o capacitate a buzunarelor de $P{~i~}$ bile (adică nu poate extrage mai mult de $P{~i~}$ bile în total). Prietenul $0$ este liderul lor şi îşi pune întrebări de forma: dacă eu extrag exact $x$ bile din urna $0$, atunci care este numărul maxim de bile pe care le pot extrage în total toţi prietenii, folosind o strategie adecvată şi considerând limitările problemei? O strategie adecvată determină câte bile extrage fiecare prieten din fiecare urnă din care poate extrage bile, considerând că prietenul $0$ extrage neapărat $x$ bile din urna $0$.

N prieteni stau în jurul a N urne cu bile. Prietenii şi urnele sunt numerotate cu numere de la 0 la N-1. Fiecare urnă i (0≤i≤N-1) conţine Si bile. Prietenii doresc să extragă bile din urne şi să le pună în buzunare. Datorită aşezării, din urna i pot extrage bile doar prietenii i şi ((i+1) mod N). Fiecare prieten i (0≤i≤N-1) are o capacitate a buzunarelor de Pi bile (adică nu poate extrage mai mult de Pi bile în total). Prietenul 0 este liderul lor şi îşi pune întrebări de forma: dacă eu extrag exact x bile din urna 0, atunci care este numărul maxim de bile pe care le pot extrage în total toţi prietenii, folosind o strategie adecvată şi considerând limitările problemei? O strategie adecvată determină câte bile extrage fiecare prieten din fiecare urnă din care poate extrage bile, considerând că prietenul 0 extrage neapărat x bile din urna 0.

h2. Cerinta

Pentru fiecare valoare posibilă a lui $x$ (de la $0$ la $min(S{~0~}, P{~0~}))$, determinaţi numărul maxim de bile pe care le pot extrage cei $N$ prieteni în total din cele $N$ urne.

Pentru fiecare valoare posibilă a lui x (de la 0 la min{S0, P0}), determinaţi numărul maxim de bile pe care le pot extrage cei N prieteni în total din cele N urne.

h2. Date de intrare

Prima linie a fişierului $bile5.in$ conţine numărul de teste $T$ descrise în continuare. Prima linie a fiecărui test conţine numărul $N$ de prieteni. Urmează apoi $N$ linii. Linia $i$ dintre acestea $(0 ≤ i ≤ N-1)$ conţine numerele întregi $S{~i~}$ şi $P{~i~}$, separate printr-un spaţiu.

Prima linie a fişierului bile.in conţine numărul de teste T descrise în continuare. Prima linie a fiecărui test conţine numărul N de prieteni. Urmează apoi N linii. Linia i dintre acestea (0≤i≤N-1) conţine numerele întregi Si şi Pi, separate printr-un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $bile5.out$ veţi afişa răspunsurile pentru fiecare test, în ordinea în care acestea sunt date în fişierul de intrare. Pentru fiecare valoare posibilă a lui $x$ (considerând ordinea crescătoare a valorilor) pentru testul respectiv, veţi afişa o linie conţinând numărul maxim total de bile pe care îl pot extrage prietenii din urne.

În fişierul de ieşire bile.out veţi afişa răspunsurile pentru fiecare test, în ordinea în care acestea sunt date în fişierul de intrare. Pentru fiecare valoare posibilă a lui x (considerând ordinea crescătoare a valorilor) pentru testul respectiv, veţi afişa o linie conţinând numărul maxim total de bile pe care îl pot extrage prietenii din urne.

h2. Restricţii

* $1 ≤ T ≤ 10$
* $2 ≤ N ≤ 15 000$
* $1 ≤ Si ≤ 16 000$
* $1 ≤ Pi ≤ 16 000$
* $40%$ dintre teste au $N ≤ 500$ şi $max(Si,Pi) ≤ 500 (0 ≤ i ≤ N-1)$
* $A mod B$ reprezintă restul împărţirii întregi a lui $A$ la $B$.

* 1≤T≤10
* 2≤N≤15 000
* 1≤Si≤16 000
* 1≤Pi≤16 000
* 40% dintre teste au N≤500 şi max{Si,Pi}≤500 (0≤i≤N-1)
* A mod B reprezintă restul împărţirii întregi a lui A la B.

* O bilă poate fi extrasă o singură dată, de un singur prieten.
h2. Exemplu

h3. Explicaţie

Pentru primul test $x$ poate lua valori între $0$ şi $min(S0, P0)=5$.
Pentru $x=0$, cei $4$ prieteni pot extrage în total $17$ bile.
Pentru $x=1$, cei $4$ prieteni pot extrage în total $18$ bile.
Pentru $x=2$, cei $4$ prieteni pot extrage în total $19$ bile.
Pentru $x=3$, cei $4$ prieteni pot extrage în total $19$ bile.
Pentru $x=4$, cei $4$ prieteni pot extrage în total $19$ bile.
Pentru $x=5$, cei $4$ prieteni pot extrage în total $18$ bile.
Valoarea lui $x$ a fost inclusă de fiecare dată în numărul total de bile ce pot fi extrase de cei $4$ prieteni.

Pentru primul test x poate lua valori între 0 şi min{S0, P0}=5.
Pentru x=0, cei 4 prieteni pot extrage în total 17 bile.
Pentru x=1, cei 4 prieteni pot extrage în total 18 bile.
Pentru x=2, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=3, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=4, cei 4 prieteni pot extrage în total 19 bile.
Pentru x=5, cei 4 prieteni pot extrage în total 18 bile.
Valoarea lui x a fost inclusă de fiecare dată în numărul total de bile ce pot fi extrase de cei 4 prieteni.

== include(page="template/taskfooter" task_id="bile5") ==

3927