Problem H
Citāti

CC0 Public Domain, congerdesign via Pixabay.

Greisa vēlas izlasīt noteiktu zinātnisku grāmatu. Tajā pašā laikā viņa ļoti nopietni attiecas pret grāmatā pieminētu avotu lasīšanu, kā arī pret šo avotu avotu lasīšanu utt. Parasti tas beidzas ar to, ka viņa izlasa daudz vairāk grāmatu par to vienu, ko viņa sākumā bija iecerējusi izlasīt. Bibliotekāres visu laiku kurn par Greisas pārlieku lielo grāmatu aizņemšanos, un tāpēc tagad viņa vēlas atrast tādu grāmatu lasīšanas secību, kas minimizētu kopējo aizņemšanās laiku.

Pavisam ir $N$ grāmatas, kuras Greisai beigu beigās vajadzēs izlasīt. Grāmatas ir sanumurētas no $1$ līdz $N$, un $i$-tā grāmata prasa $K_ i$ minūtes, lai to izlasītu. Katra grāmata $i$ satur citātu sarakstu, kas iekļauj $F_ i$ grāmatas. Grāmatai, kuru Greisa vēlējās izlasīt pašā sākumā, ir numurs $1$. Pirms 1. grāmatas lasīšanas iesākšanas Greisa jau ir aizņēmusies visas $N$ grāmatas.

Kad Greisa lasa grāmatu, viņa dara sekojošo:

• sākumā viņa atver grāmatu un izlasa citātu sarakstu, kas aizņem vienu minūti;

• pēc tam viņa izlasa visas grāmatas no šī saraksta, kaut kādā viņas pašas izvēlētā secībā;

• visbeidzot, viņa izlasa pašu grāmatu un atgriež to bibliotēkā, kas aizņem $K_ i$ minūtes.

Jums ir jāaprēķina minimālais kopējais visu grāmatu aizņemšanās laiks, ņemot vērā, ka Greisa lasa grāmatas optimālā secībā. Grāmatas var saturēt tukšus citātu sarakstus, un katra grāmata, izņemot 1. grāmatu, parādīsies tieši vienā citātu sarakstā. Ievaddatos neparādīsies citātu cikli.

Ievaddati

Pirmā rinda satur veselu skaitli $N$ ($1 \le N \le 100\, 000$). Pēc tam seko $N$ rindas, pa vienai uz katru grāmatu no $1$ līdz $N$. Katra tāda rinda satur skaitli $K_ i$ ($1 \le K_ i \le 1\, 000$) — minūšu skaitu šīs grāmatas izlasīšanai. Pēc tam seko skaitlis $F_ i$ ($0 \le F_ i < N$), pēc kura seko $F_ i$ skaitļi — grāmatu numuri, uz kuriem atsaucas $i$-tā grāmata.

Izvaddati

Izvadiet vienu veselu pozitīvu skaitli — minimālo kopējo grāmatu aizņemšanās laiku.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

1. parauga paskaidrojums

laiks 1: atver grāmatu 1
laiks 2: atver grāmatu 2
laiks 3: atver grāmatu 4
laiks 4: aizver grāmatu 4 (aizņemšanās laiks 4 minūtes)
laiks 14: aizver grāmatu 2 (aizņemšanās laiks 14 minūtes)
laiks 15: atver grāmatu 3
laiks 16: atver grāmatu 5
laiks 17: aizver grāmatu 5 (aizņemšanās laiks 17 minūtes)
laiks 37: aizver grāmatu 3 (aizņemšanās laiks 37 minūtes)
laiks 38: aizver grāmatu 1 (aizņemšanās laiks 38 minūtes)

5
1 2 2 3
10 1 4
20 1 5
1 0
1 0

110