Nosaukums
Ķirši (cherry)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Mazais, bet drosmīgais pelēns ir nolēmis apēst visas ogas no pagalmā augošā ķirša. Ķirsis ir parasts koks, kura zari var sazaroties, bet nekad nesaaug kopā. No punkta, kur beidzas viens zars, var sākties citi zari vai atrasties noteikts ogu skaits.

Ķirša zari ir tik gari, ka pelēna spēki pārvietošanās laikā izsīkst. Kad pelēns ir nogājis pa zaru vienu metru, viņa enerģijas rezerves (ER) samazinās par vienu vienību. Savukārt, vienas ogas apēšana palielina ER par vienu vienību. Ja ER vērtība kļūst negatīva, pelēns iet bojā.

Uzrakstiet programmu, kas pēc ķirša apraksta nosaka mazāko ER vienību skaitu, kādam jābūt pelēnam, lai viņš varētu apēst visas ogas un atgriezties uz zemes! Šajā laikā nevienu brīdi pelēna ER vērtība nedrīkst būt negatīva. Kustība vienmēr sākus un beidzas ar zaru nr.1, kas atbilst ķirša stumbram.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dots naturāls skaitlis N (1≤N ≤100) - koka zaru skaits. Tālāk seko N rindas, kas apraksta koku. Katra (i+ 1)-ā faila rinda satur i-tās virsotnes aprakstu. Pirmais ir naturāls skaitlis L (1 ≤L≤30 000), kas uzdod zara garumu metros. Otrais ir vesels skaitlis K, kas apzīmē to zaru skaitu, kas sākas no i-tā zara beigām. Tālāk seko K skaitļi - šo zaru numuri. Ja kādam zaram K vērtība ir 0, tad trešais skaitlis šajā rindā ir ogu skaits V (0≤V≤30 000) šī zara galā.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais ER vienību skaits, kādam jābūt pelēnam, lai viņš varētu apēst visas ogas un atgriezties uz zemes.


Piezīmes

Uzdevums izmantots Ukrainas XVI informātikas olimpiādē.


Paraugdati

Stdin
8
5 3 6 5 7
5 0 10
9 0 1
4 0 19
11 0 50
5 2 2 4
3 2 8 3
4 0 0
Stdout
15

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.