O retea de televiziune isi propune sa difuzeze Gala Premiilor Oscar.
Sistemul de transmisie al acestei televiziuni poate fi reprezentat ca un arbore.
Radacina arborelui este transmitatorul care emite imaginile filmate la Gala
Premiilor Oscar. Nodurile terminale din arbore (frunzele) sunt abonatii care
pot viziona spectacolul. Celelalte noduri din arbore sunt relee de transmisie.
Costul transmiterii semnalului de la un nod la altul este cunoscut, pretul
intregii transmisiuni fiind suma costurilor transmiterii semnalului intre noduri.
Abonatii sunt dispusi sa plateasca o anumita suma de bani pentru a viziona
Gala Premiilor Oscar, reteaua de televiziune urmand sa decida daca va furniza
sau nu semnal acelui abonat.
Cerinta
Scrieti un program care determina numarul maxim de abonati care
pot viziona Gala Premiilor Oscar, astfel incat reteaua de televiziune sa nu
piarda bani prin transmiterea evenimentului.
Date de intrare
Fisierul de intrare tv.in
contine pe prima linie doua numere naturale N si M, reprezentand numarul de
noduri din arbore si respectiv numarul de abonati. Radacina arborelui este numerotata cu 1, iar releele de transmisie sunt numerotate de la 2 la N-M. Evident, abonatii sunt numerotati de la N-M+1 la N.
Urmatoarele N-M linii contin informatii despre transmitatori astfel: K A1 C1 A2 C2 ... AK CK cu semnificatia: "transmitatorul emite semnal catre alti K transmitatori sau abonati, fiecare dintre acestia fiind descris printr-o pereche de numere de
forma A C, unde A este numarul transmitatorului sau abonatului, iar C este costul transmiterii semnalului catre acesta".
Ultima linie contine informatii despre abonati. Pe aceasta linie se afla M
numere intregi reprezentand, in ordine, suma de bani pe care abonatii sunt dispusi
sa o plateasca pentru a viziona Gala Premiilor Oscar.
Date de iesire
Fisierul de iesire tv.out va contine pe prima linie numarul maxim de abonati
care pot viziona Gala Premiilor Oscar, fara ca reteaua de televiziune sa piarda
bani.
Restrictii
2 <= N <= 3000
1 <= M <= N-1
Exemple
tv.in
tv.out
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
2
tv.in
tv.out
5 3
2 2 2 5 3
2 3 2 4 3
4 4 2
3
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi