Fişierul intrare/ieşire:covrigi.in, covrigi.outSursăFMI No Stress 9
AutorTheodor MoroianuAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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 230.
  • 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

covrigi.incovrigi.out
10 4 1
10 8 5 4 4 3 2 1 1 0
2 0 0 1
8

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?