== 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 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.

$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$.

h2. Cerinta

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.

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.

h2. Date de intrare

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.

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.

h2. Date de ieşire

Î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.

 
Î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.

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