Futbola spēles translācija

Uzdevums

Maksas televīzijas kanāla vadība ir nolēmusi translēt nozīmīgu futbola spēli. Televīzijas kanāla raidītāju un abonentu tīklu var attēlot kā koku. Koka sakne ir raidītājs, kas pārraida futbola spēli, koka lapas ir abonenti, bet pārējās virsotnes ir raidītāji, kas retranslē(pārraida tālāk) saņemto signālu.

Signāla pārraides izmaksas no viena raidītāja līdz otram un no raidītāja līdz abonentam ir zināmas. Visas pārraides kopējās izmaksas ir visu atsevišķo signālu pārraides izmaksu summa.

Katrs abonents paziņo, kādu naudas summu viņš ir ar mieru maksāt par iespēju skatīties šīs spēles pārraidi un tad kanāla vadība izlemj, vai nodrošināt pārraidi līdz šim abonentam vai nē.

Uzrakstiet programmu, kas nosaka lielāko iespējamo abonentu skaitu, līdz kuriem iespējams nodrošināt spēles signāla pārraidi, lai televīzijas kanāls neciestu zaudējumus!

Ievaddati

Teksta faila futbols.dat pirmajā rindā dotas divu naturālu skaitļu N(koka virsotņu skaits, 2≤N≤3000) un M(potenciālo abonentu skaits,1≤M≤N-1) vērtības, kas atdalītas ar tukšumsimbolu.

Koka sakne ir apzīmēta ar skaitli 1, pārējie raidītāji ir numurēti ar skaitļiem no 2 līdz N-M un potenciālie abonenti ar skaitļiem no N-M+1 līdz N.

Nākošās N-M faila rindas satur informāciju par raidītājiem formā

K A₁ C₁ A₂ C_{2 ...} A_K C_K

, kas nozīmē, ka dotais raidītājs pārraida signālu K patērētājiem (citiem raidītājiem vai abonentiem), katru no kuriem apraksta naturālu skaitļu pāris A(patērētāja numurs) un C(signāla pārraides no raidītāja līdz šim patērētājam izmaksas). Faila (i+1)-ajā rindā dota informācija par i-to raidītāju.

Faila pēdējā rindā doti M veseli skaitļi, kas atdalīti ar tukšumsimboliem - naudas daudzums, cik katrs no abonentiem ir ar mieru maksāt par iespēju skatīties spēles pārraidi.

Izvaddati

Teksta faila futbols.rez vienīgajā rindā jāizvada vesels skaitlis - lielākais iespējamais abonentu daudzums, līdz kuriem iespējams nodrošināt spēles pārraidi.

Piemērs

futbols.dat	futbols.rez
5 3 2 2 2 5 3 2 3 2 4 3 3 4 2	2
futbols.dat	futbols.rez
5 3 2 2 2 5 3 2 3 2 4 3 4 4 2	3
futbols.dat	futbols.rez
9 6 3 2 2 3 2 9 3 2 4 2 5 2 3 6 2 7 2 8 2 4 3 3 3 1 1	5

Atsauces