== include(page="template/taskheader" task_id="homecoming") ==
Poveste şi cerinţă...
Spiderman este încă în liceu. Vecinul prietenos supererou are $N$ materii la şcoală, numerotate de la $0$ la $N-1$. Pentru fiecare materie pe care o trece, va primi un premiu în bani de la Tony Stark. Dacă trece materia $i$, va primi $A{~i~}$ dolari.
Să treci o materie e totuşi nu e chiar aşa uşor. Pentru a trece are nevoie să cumpere nişte manuale. Desigur, super eroul nostru este foarte deştept, deci nu are nevoie de niciun manual pentru a învăţa, dar unii profesori nu îl lasă sa treacă decât dacă investeşte nişte bani în manuale. Sunt $N$ manuale numerotate de la $0$ la $N-1$, iar al $i$-lea manual costă $B{~i~}$ dolari.
Pentru a trece materia $i$, Peter are nevoie să cumpere manualele $i$, $(i+1)%N$, ..., $(i+K-1)%N$, unde $K$ este o constantă dată.
Lui Peter nu îi mai pasă de şcoală, căci visul lui este să devină un Avenger, deci nu e relevant dacă trece sau nu toate materiile. Peter iubeşte timpul, şi timpul înseamnă bani, deci ajutaţi-l pe Peter să işi maximizeze profitul.
h2. Date de intrare
Fişierul de intrare $homecoming.in$ ...
Pe prima linie a fişierului de intrare $homecoming.in$ se va găsi un număr $T$ ce reprezintă numărul de teste. Urmează cele $T$ teste.
Primul rând al unui test va conţine numerele $N$ şi $K$.
Al doilea rând al unui test va conţine cele $N$ elemente ale şirului $A$.
Al treilea rând al unui test va conţine cele $N$ elemente ale şirului $B$.
h2. Date de ieşire
În fişierul de ieşire $homecoming.out$ ...
Fişierul de ieşire $homecoming.out$ va conţine răspunsurile pentru cele $T$ teste, câte unul pe fiecare rând.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 2.000.000$
* Dacă $SN$ este suma lui $N$ pentru toate testele dintr-un fişier, atunci $1 ≤ SN ≤ 2.000.000$
* $0 ≤ A{~i~}, B{~i~} ≤ 1.000.000.000$
* Pentru $13$ puncte, $1 ≤ SN ≤ 500$
* Pentru alte $18$ puncte, $1 ≤ SN ≤ 5.000$
* Pentru alte $31$ puncte, $1 ≤$ suma lui $N * K$ pentru toate testele dintr-un fişier $≤ 2.000.000$
h2. Exemplu
h2. Exemple
table(example). |_. homecoming.in |_. homecoming.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 1
3 2
40 80 100
140 0 20
| 60
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="homecoming") ==
