| Fişierul intrare/ieşire: | tribut.in, tribut.out | Sursă | ACM ICPC - Romanian Programming Contest 2016 |
| Autor | Traian Rebedea | Adăugată de |  Traian Rebedea •trebedea |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tribut
Marele Imperiu Galactic stăpâneşte un număr de N sisteme solare tributare acestuia şi cu o bogăţie variată în resurse. Fiecare sistem solar datorează un anumit procent din veniturile sale Împăratului sub formă de tribut (taxe) pentru serviciile aduse, în special pentru înlesnirea comerţului.
Împăratul ar dori să colecteze o cantitate cât mai mare din tributurile plătite de sistemele solare, însă se confruntă cu următoarea problemă. Conform tratatelor semnate cu sistemele solare, există o serie de M uniuni comerciale formate din sisteme solare, iar fiecare uniune are agreată o cantitate maximă de tribut pe care toate sistemele din uniune trebuie să le plătească cumulat Împăratului. Dacă o ţară face parte din multe uniuni comerciale, atunci ea poate fi fortaţă să contribuie la tributurile plătite de către oricare dintre acestea, în limita cantităţii maxime de tribut datorat de ţara respectivă. Ţările care nu fac parte din nici o uniune comercială sunt scutite de tribut.
Ştiind valorile de tribut calculate pentru fiecare ţară în parte în funcţie de veniturile sale, precum şi valorile maxime de tribut stabilite prin tratatele cu fiecare uniune, ajutaţi-l pe Împărat să decidă care este valoarea maximă a tributului pe care o va primi de la toate sistemele solare. În mod evident, nici o uniune comercială nu va plăti o valoare mai mare decât cea stabilită prin tratatul cu Imperiul Galactic, însă Împăratul poate decide contribuţia fiecărui sistem solar din uniunea respectivă la suma totală a uniunii.
Date de intrare
Datele de intrare se citesc din fişierul tribut.in.
Pe prima linie se află numărul de teste, T. După aceea, pentru fiecare test sunt citite următoarele informaţii:
- Prima linie a unui test conţine două numere întregi separate prin spaţiu: N - numărul de sisteme solare şi M - numărul de uniuni comerciale.
- Următoarea linie conţine N numere întregi separate prin spaţiu, reprezentând tributul maximal ce poate fi plătit de fiecare sistem solar pe baza veniturilor sale ( tribut[i], 1 <= i <= N ).
- Dupa aceea, urmează M linii pentru fiecare uniune comercială. Fiecare linie începe cu două numere întregi: primul conţine numărul de sisteme solare care fac parte din uniune - P, iar al doilea tributul maximal plătit de către toate ţările din uniune conform tratatului semnat cu Imperiul Galactic ( tribut[j], 1 <= j <= M ). Urmează apoi cele P sisteme solare din uniunea curentă indexate între 1..N.
Date de ieşire
Fişierul de ieşire este tribut.out care va conţine câte o linie pentru fiecare test. Pe fiecare linie trebuie să se afle un singur număr, care este valoarea maximă a tributului pe care o va primi de la toate sistemele solare care fac parte dintr-o uniune comercială.
Restricţii
- $ 1 ≤ T ≤ 10 $
- 1 ≤ N, M ≤ 100
- $0 ≤ tribut[i], tribut[j] ≤ 10000 $
Exemplu
| tribut.in | tribut.out |
|---|---|
| 2 4 4 2 1 1 1 2 2 1 2 2 1 3 4 2 2 1 3 2 0 2 4 9 6 5 0 2 0 2 0 2 0 3 3 4 1 2 3 3 0 4 5 6 3 0 7 8 9 3 6 1 4 7 3 0 2 5 8 3 0 3 6 9 | 5 9 |
Explicaţie
- În primul caz, avem 4 sisteme solare şi 4 uniuni comerciale, iar tributul maxim ce poate fi obţinut de Împărat este 5. Prima uniune contribuie cu 2: sistemul 1 cu 1 şi sistemul 2 cu 1. A doua uniune contribuie cu 1 platit de sistemul 4. A treia uniune contribuie cu 2: sistemul 1 cu 1 şi sistemul 3 cu 1. A patra uniune nu contribuie cu nimic.
- În al doilea caz, sunt doar 2 uniuni comerciale care pot contribui cu tribut, celelalte au semnat tratate care le protejează de tribut. O posibilă soluţie de împărţire a tributului pe uniuni este: prima uniune poate contribui cu 3, iar a patra cu 6.
