Fişierul intrare/ieşire:	covrigi.in, covrigi.out	Sursă	FMI No Stress 9
Autor	Theodor Moroianu	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.05 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Covrigi

Concursul FMICUSTRESS se desfasoara in Universitatea din Bucuresti. Fiind un concurs deosebit de cunoscut, are si o cantitate deosebita de premii.

Astfel, castigatorul concursului urmeaza sa primeasca un telefon, cel de pe locul 2 un cupon cu 10 beri gratuite la beraria H etc.
Tie nu prea iti pasa de premiu pentru ca oricum urmeaza sa il vinzi pentru a avea bani sa iti cumperi covrigi de la Luca in pauza, asa ca ti-ai construit un vector V, unde V[i] reprezinta castigul tau daca iesi pe pozitia i (cati covrigi Luca o sa poti sa iti cumperi). In mod evident, ca la oricare concurs care se respecta, V[i + 1] ≤ V[i].

Pentru a avea un loc mai bun, ai posibilitatea sa iti cumperi cateva raspberry pi-uri (oricum sunt foarte ieftine), sa le plasezi undeva in universitate, si sa ii "convingi" pe cei din jurul lor sa te lase sa castigi, rasberry pi-urile picandu-le netul (in regulamentul intern al universitatii scrie explicit ca nu patesti nimic pana nu esti prins - ceea ce evident nu o sa fie cazul).

Concret stii ca:

1. sunt N concurenti care participa la concurs,
2. studentii sunt impartiti in M sali,
3. un raspberry pi costa echivalentul a K covrigi Luca,
4. cu fiecare raspberry pi poti sa impiedici o unica sala din a participa la concurs.

Ti se dau si cei doi vectori: V, al castigului in functie de loc, si C, C[i] reprezentand cati concurenti din sala i ar fi clasati mai bine ca tine daca nu i-ai impiedica.

Cati covrigi Luca o sa poti sa iti iei maxim dupa concurs, presupunand ca joci optim?

Date de intrare

Fişierul de intrare covrigi.in contine pe prima linie numerele N, M si K, cu semnificatiile de mai sus.
Urmatoarea linie contine vectorul V de lungime N.
Ultima linie contine vectorul C, de lungime M. Se garanteaza ca suma elementelor din C este mai mica decat N.

Date de ieşire

În fişierul de ieşire covrigi.out contine un singur numar, numarul maxim de covrigi pe care poti sa ii castigi.

Restricţii

• 1 ≤ N, M ≤ 50.000
• Participa cel putin un concurent la concurs (tu).
• Numerele citite sunt ne-negative.
• Numerele citite din input sunt mai mici decat 2³⁰.
• Pentru teste in valoare de 20 de puncte (testele 1-2), M ≤ 10.
• Pentru alte teste in valoare de 30 de puncte (testele 3-4-5), M ≤ 20.

Exemplu

Explicaţie

Pentru a avea profitul maxim, poti sa impiedici sala #1 si #4, ceea ce te costa 2 * 1 = 2, si iesi pe locul 1 ceea ce iti aduce 10.
In total castigi 10 - 2 = 8 covrigi.

Cum se trimit solutii?