Fişierul intrare/ieşire:homecoming.in, homecoming.outSursăBOI 2018
AutorAndrei Constantinescu, Bogdan CiobanuAdăugată deAndrei1998Andrei Constantinescu •Andrei1998
Timp execuţie pe test1.25 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 Ai 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ă Bi 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.

Date de intrare

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.

Date de ieşire

Fişierul de ieşire homecoming.out va conţine răspunsurile pentru cele T teste, câte unul pe fiecare rând.

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 ≤ Ai, Bi ≤ 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

Exemple

homecoming.inhomecoming.out
1
3 2
40 80 100
140 0 20
60
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?