== include(page="template/taskheader" task_id="covrigi") ==
Poveste şi cerinţă...
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:
# sunt $N$ concurenti care participa la concurs,
# studentii sunt impartiti in $M$ sali,
# un raspberry pi costa echivalentul a $K$ covrigi Luca,
# 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?
h2. Date de intrare
Fişierul de intrare $covrigi.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $covrigi.out$ ...
În fişierul de ieşire $covrigi.out$ contine un singur numar, numarul maxim de covrigi pe care poti sa ii castigi.
h2. 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^30^$.
* 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$.
h2. Exemplu
table(example). |_. covrigi.in |_. covrigi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 4 1
10 8 5 4 4 3 2 1 1 0
2 0 0 1
| 8
|
h3. 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.
== include(page="template/taskfooter" task_id="covrigi") ==
