Fişierul intrare/ieşire:provacanta.in, provacanta.outSursăAlgoritmiada 2016, Runda Finala, Juniori
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.75 secLimită de memorie200000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Provacanta

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 ti, timpul necesar (in zile) pentru realizarea proiectului si ci, 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 ti, numarul de zile de concediu si ci, 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.

Date de intrare

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 ti, ci reprezentand cele N proiecte. Pe urmatoarele M linii vor fi cate 2 numere naturale ti, ci reprezentand cele M oferte de vacanta

Date de ieşire

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.

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N, M ≤ 100
  • 1 ≤ K ≤ 1.000
  • 1 ≤ ti ≤ K
  • 1 ≤ ci ≤ 1.000.000

Exemplu

provacanta.inprovacanta.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?