covrigi

Covrigi

# 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.

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?

N, M <= 1.000.000
 
 

h2. Date de intrare
Fişierul de intrare $covrigi.in$ contine pe prima linie numerele $N$, $M$ si $K$, cu semnificatiile de mai sus.

h2. Restricţii

* $1 ≤ N, M ≤ 100.000$
* Se garanteaza ca inputul este valid (Cel putin un concurent, toate numerele din input sunt pozitive etc)
* Numerele citite din input sunt mai mici decat $2^31^$

* $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") ==