bile

Time limit: 0.4s Memory limit: 2MB Input: bile.in Output: bile.out

NN prieteni stau în jurul a NN urne cu bile. Prietenii şi urnele sunt numerotate cu numere de la 00 la N1N-1. Fiecare urnă ii (0iN1)(0 \leq i \leq N-1) conţine SiS_i bile. Prietenii doresc să extragă bile din urne şi să le pună în buzunare. Datorită aşezării, din urna ii pot extrage bile doar prietenii ii şi ((i+1)((i+1) mod N)N). Fiecare prieten ii (0iN1)(0 \leq i \leq N-1) are o capacitate a buzunarelor de PiP_i bile (adică nu poate extrage mai mult de PiP_i bile în total). Prietenul 00 este liderul lor şi îşi pune întrebări de forma: dacă eu extrag exact xx bile din urna 00, 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 00 extrage neapărat xx bile din urna 00.

Cerinţă

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

Date de intrare

Prima linie a fişierului bile.in conţine numărul de teste TT descrise în continuare. Prima linie a fiecărui test conţine numărul NN de prieteni. Urmează apoi NN linii. Linia ii dintre acestea (0iN1)(0 \leq i \leq N-1) conţine numerele întregi SiS_i şi PiP_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 xx (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

  • 1T101 \leq T \leq 10
  • 2N15 0002 \leq N \leq 15 \ 000
  • 1Si16 0001 \leq S_i \leq 16 \ 000
  • 1Pi16 0001 \leq P_i \leq 16 \ 000
  • 40%40\% dintre teste au N500N \leq 500 şi max{S0,P0}max \{ S_0, P_0 \} 500\leq 500 (0iN1)(0 \leq i \leq N-1)
  • A mod BA \ \text{mod} \ B reprezintă restul împărţirii întregi a lui AA la BB.
  • 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 xx poate lua valori între 00 şi min{S0,P0}=5min\{ S_0, P_0 \}=5.
Pentru x=0x=0, cei 44 prieteni pot extrage în total 1717 bile.
Pentru x=1x=1, cei 44 prieteni pot extrage în total 1818 bile.
Pentru x=2x=2, cei 44 prieteni pot extrage în total 1919 bile.
Pentru x=3x=3, cei 44 prieteni pot extrage în total 1919 bile.
Pentru x=4x=4, cei 44 prieteni pot extrage în total 1919 bile.
Pentru x=5x=5, cei 44 prieteni pot extrage în total 1818 bile.
Valoarea lui xx a fost inclusă de fiecare dată în numărul total de bile ce pot fi extrase de cei 44 prieteni.

Log in or sign up to be able to send submissions!