homecoming

Homecoming

== 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") ==