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

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