== include(page="template/taskheader" task_id="provacanta") ==
Poveste şi cerinţă...
Doru Muncitoru s-a angajat la o noua firma de spalat castroane in Cluj. Cum afacerea merge foarte bine, acesta are $N$ proiecte la dispozitie. Pentru fiecare se cunoste $t{~i~}$, timpul necesar (in zile) pentru realizarea proiectului si $c{~i~}$, suma pe care acesta o castiga in urma finalizarii proiectului. Deoarece toata lumea il adora pe Doru Muncitoru, acesta a primit si $M$ oferte de vacanta pentru care de asemenea se cunoaste $t{~i~}$, numarul de zile de concediu si $c{~i~}$, suma cu care este acesta platit (Doru Muncitoru isi alege doar vacante platite).
Precum si numele lui sugereaza, Doru este un baiat harnic si nu il intereseaza vacantele atat de mult. In schimb, Doru este disperat sa castige cat mai multi bani. Din pacate, el stie ca de fiecare data cand lucreaza la un proiect nou, randamentul acestuia scade, ca urmare orice proiect ulterior o sa il realizeze cu o zi mai mult. Acesta oboseala se propaga, deci dupa ce a realizat $X$ proiecte, al $X + 1$ - lea proiect care in mod normal i-ar fi luat $Y$ zile o sa dureze $X + Y$ zile. In schimb, de fiecare data cand se duce in vacanta, randamentul lui revine la normal. Doru realizeaza ca desi vacantele pot sa fie platite mai prost, este posibil sa ii convina sa mearga si sa se odihneasca pentru a isi reintra in forma.
Doru Muncitoru nu are mult timp de pierdut. Din moment ce nu are stare si isi schimba locul de munca foarte des, el are la dispozitie doar $K$ zile sa castige cat mai multi bani. Stiind cele $N$ proiecte, cele $M$ oferte de vacanta si $K$ (numarul de zile pe care il are la dispozitie), el va roaga sa determinati suma maxima pe care acesta poate sa o obtina.
h2. Date de intrare
Fişierul de intrare $provacanta.in$ ...
Fişierul de intrare $provacanta.in$ va contine pe prima linie un număr natural $T$, reprezentând numărul de teste. Structura unui test este următoarea: pe prima linie $3$ numere naturale $N$, $M$ si $K$. Pe urmatoarele $N$ linii vor fi cate $2$ numere naturale $t{~i~}, c{~i~}$ reprezentand cele $N$ proiecte. Pe urmatoarele $M$ linii vor fi cate $2$ numere naturale $t{~i~}, c{~i~}$ reprezentand cele $M$ oferte de vacanta
h2. Date de ieşire
În fişierul de ieşire $provacanta.out$ ...
Fişierul de ieşire $provacanta.out$ va contien un singur numar natural reprezentand suma maxima pe care o poate castiga Doru Muncitoru in cele $K$ zile pe care le are la dispozitie.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 5$
* $1 ≤ N, M ≤ 100$
* $1 ≤ K ≤ 1.000$
* $1 ≤ t{~i~} ≤ K$
* $1 ≤ c{~i~} ≤ 1.000.000$
h2. Exemplu
table(example). |_. provacanta.in |_. provacanta.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
6 4 14
4 18
2 10
1 8
4 18
2 10
1 18
6 18
5 21
6 14
3 9
|74
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="provacanta") ==
