bile

$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 \leq i \leq 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 \leq i \leq 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$.

Cerinţă

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.

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 \leq i \leq N-1)$ conţine numerele întregi $S_i$ şi $P_i$, separate printr-un spaţiu.

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.

Restricţii şi precizări

• $1 \leq T \leq 10$
• $2 \leq N \leq 15 \ 000$
• $1 \leq S_i \leq 16 \ 000$
• $1 \leq P_i \leq 16 \ 000$
• $40\%$ dintre teste au $N \leq 500$ şi $max \{ S_0, P_0 \}$ $\leq 500$ $(0 \leq i \leq N-1)$
• $A \ \text{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.

Exemplu

bile.in

2
4
5 5
3 4
8 6
3 4
4
2 3
6 5
2 4
3 1

bile.out

17
18
19
19
19
18
13
13
12

Explicație

Pentru primul test $x$ poate lua valori între $0$ şi $min\{ S_0, P_0 \}=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.