Šeštadieninė informatikos olimpiadininkų mokykla

Labirintą sudaro kambariai ir perėjimai tarp jų. Perėjimais galima judėti tik nurodyta kryptimi. Labirinte ciklų nėra.

Kiekviename kambaryje yra arba prizas, arba bauda - tai išreiškiama taškais. Keliautojui patekus į kambarį, jei kambaryje yra prizas, taškai pridedami prie keliautojo sąskaitos, o jei kambaryje yra bauda, tai keliautojo sąskaita sumažinama baudos taškais.

Keliautojas gali pasirinkti, kuriame kambaryje jis nori pradėti judėti labirintu, ir kuriame kambaryje jis sustos; tačiau keliautojas privalo aplankyti bent vieną labirinto kambarį.

Parašykite programą, kuri duotam labirintui surastų didžiausią taškų skaičių, kurį gali surinkti keliautojas (jei visuose kambariuose yra tik baudos, tai didžiausiais taškų skaičius bus neigiamas). Pradiniu momentu sąskaitoje yra nulis taškų.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas labirinto kambarių skaičius N (). Toliau eina N eilučių, atitinkančių kambarius (kambariai numeruojami nuo 1 iki N). Kiekvienoje eilutėje pirmas skaičius T reiškia, kiek taškų yra šiame kambaryje: jei T > 0, tai prizas, jei T < 0, tai bauda. Toliau eilutėje įrašytas skaičius P, kuris lygus perėjimų, išeinančių iš atitinkamo kambario, skaičiui, po jo pateikta P kambarių, į kuriuos veda tie perėjimai, numeriai. Skaičiai eilutėse skiriami tarpais.

Rezultatai

Į pirmą rezultatų failo eilutę įrašykite skaičių, reiškiantį, kokį didžiausią taškų skaičių galima surinkti duotajame labirinte.

Pavyzdžiai

7
  1 1 5
 -1 1 5 
 10 2 1 2
 50 1 7
-10 1 4
-2  1 3
-3  0

51

4
-1  0 
-7  1  4 
-2  2  1  2
-3  0

-1