homecoming

Homecoming

== include(page="template/taskheader" task_id="homecoming") ==

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.

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.

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

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