tribut

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

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

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

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

h2. Restricţii

* Î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.

== include(page="template/taskfooter" task_id="robo") ==

== include(page="template/taskfooter" task_id="tribut") ==