Baltic Olympiad in Informatics 2018 Open - practice session

Start

2018-04-27 17:30 CEST

Baltic Olympiad in Informatics 2018 Open - practice session

End

2018-04-27 19:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -590 days 9:09:52

Time elapsed

2:00:00

Time remaining

0:00:00

Problem B
Viited

Grace tahab lugeda üht teadusraamatut. Tal on harjumus alati hoolikalt lugeda ka kõiki allikaid, millele tema loetavad raamatud viitavad ja nende allikaid j.n.e. Tavaliselt on tulemuseks, et ta loeb märksa rohkem raamatuid kui see üks, mida ta algselt lugeda plaanis. Raamatukoguhoidjad juba pahandavad tema tohutute laenutusmahtude pärast. Selle vähendamiseks tahab ta leida, mis järjekorras ta peaks raamatuid lugema, et summaarne laenutusaeg oleks vähim võimalik.

On teada, et lõpuks loeb ta kokku $N$ raamatut. Raamatud on nummerdatud $1 \dots N$ ja raamatu $i$ lugemiseks kulub $K_ i$ minutit. Raamatus $i$ on viited $F_ i$ teisele raamatule. Raamat, mida Grace algselt lugeda plaanis, on number $1$. Enne lugemise algust on Grace juba laenutanud kõik $N$ raamatut.

Iga raamatu lugemisel käitub Grace järgmiselt:

  • Kõigepealt avab ta raamatu ja loeb läbi selle viidete nimekirja, milleks kulub üks minut.

  • Siis loeb ta mingis tema valitud järjekorras läbi kõik viidatud raamatud.

  • Lõpuks loeb ta läbi raamatu enda ja tagastab selle raamatukokku, milleks kulub $K_ i$ minutit.

Leida minimaalne laenutuste aegade summa, kui Grace loeb raamatuid optimaalses järjekorras. Mõne raamatu viidete nimekiri võib olla tühi ja on teada, et iga raamat (peale raamatu $1$) on täpselt ühe teise raamatu viidete nimekiras. Lisaks on teada, et viidete hulgas ei ole tsükleid.

Input

Sisendi esimesel real on raamatute arv $N$ ($1 \le N \le 100\, 000$). Järgmised $N$ rida kirjeldavad raamatuid nende numbrite järjekorras. Igal real on kõigepealt raamatu lugemiseks kuluvate minutite arv $K_ i$ ($1 \le K_ i \le 1\, 000$), selle järel raamatus olevate viidete arv $F_ i$ ($0 \le F_ i < N$), ja selle järel $F_ i$ viidatavate raamatute numbrit.

Output

Väljastada täpselt üks täisarv, vähim võimalik kõigi raamatute laenutusaegade summa.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Group

Points

Limits

1

20

$1 \le N \le 10, 1 \le K_ i \le 1000$

2

30

$1 \le N \le 50, 1 \le K_ i \le 10$, $F_ i \le 5$

3

20

$1 \le N \le 100\, 000, 1 \le K_ i \le 1000, F_ i \le 5$

4

30

$1 \le N \le 100\, 000, 1 \le K_ i \le 1000$

Explanation of Sample 1

1. minut: ava raamat 1
2. minut: ava raamat 2
3. minut: ava raamat 4
4. minut: tagasta raamat 4 (laenutuse aeg 4 minutit)
14. minut: tagasta raamat 2 (laenutuse aeg 14 minutit)
15. minut: ava raamat 3
16. minut: ava raamat 5
17. minut: tagasta raamat 5 (laenutuse aeg 17 minutit)
37. minut: tagasta raamat 3 (laenutuse aeg 37 minutit)
38. minut: tagasta raamat 1 (laenutuse aeg 38 minutit)

Sample Input 1 Sample Output 1
5
1 2 2 3
10 1 4
20 1 5
1 0
1 0
110