Baltic Olympiad in Informatics 2018 Open - practice session

Start

2018-04-27 15:30 UTC

Baltic Olympiad in Informatics 2018 Open - practice session

End

2018-04-27 17:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -590 days 9:13:05

Time elapsed

2:00:00

Time remaining

0:00:00

Problem B
Odniesienia

Gracjan przymierza się do przeczytania książki naukowej. Ponieważ czyta bardzo uważnie, zawsze czyta również pozycje, do których odnosi się książka. I pozycje, do których odnoszą się owe pozycje. I tak dalej. Zwykle kończy się tak, że Gracjan czyta o wiele więcej książek niż zamierzał. Ponieważ bibliotekarka zaczyna narzekać na hobby Gracjana skutkujące w długie wypożyczenia, zamierza on znaleźć taką kolejność czytania książek, aby zminimalizować łączny czas ich wypożyczenia.

Gracjan będzie musiał przeczytać $N$ książek. Książki są ponumerowane od $1$ do $N$, przeczytanie książki numer $i$ zajmuje $K_ i$ minut. Książka $i$ ma bibliografię (listę odniesień) zawierającą $F_ i$ pozycji. Początkowo Gracjan zamierza przeczytać książkę $1$. Przed rozpoczęciem czytania Gracjan wypożyczył wszystkie $N$ książek.

Czytając książkę numer $i$ Gracjan:

  • Otwiera książkę i czyta bibliografię w ciągu jednej minuty,

  • potem czyta wszystkie pozycje, do których odnosi się książka

  • i dopiero czyta książkę $i$, co zajmuje mu $K_ i$ minut. Przeczytana książka jest natychmiast zwracana w 0 minut.

Twoim zadaniem jest policzenie minimalnego łącznego czasu wypożyczenia książek przy założeniu, że Gracjan czyta je w optymalnej kolejności. Książka może zawierać pustą bibliografię i każda książka za wyjątkiem książki $1$ jest wymieniona na w dokładnie jednej bibliografii. Odniesienia nie tworzą cykli.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita $N$ ($1 \le N \le 100\, 000$). Kolejne $N$ wierszy opisuje książki w kolejności od $1$ do $N$. Na początku pojedynczego opisu znajdują się liczby całkowite $K_ i$ i $F_ i$ ($1 \le K_ i \le 1\, 000$, $0 \le F_ i < N$) oznaczające odpowiednio liczbę minut, przez które Gracjan czyta $i$-tą oraz liczbę pozycji w bibliografii. Kolejne $F_ i$ liczb zawiera numery książek, do których odnosi się $i$-ta książka.

Wyjście

Na wyjście wypisz pojedynczą liczbę całkowitą – minimalny łączny czas wypożyczenia wszystkich książek.

Ograniczenia

Twoje rozwiązanie będzie uruchomione na grupach testów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, twoje rozwiązanie musi przejść wszystkie testy z tej grupy.

Grupa

Punkty

Limity

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$

Wyjaśnienie do przykładu 1

min 1: otwarcie książki 1
min 2: otwarcie książki 2
min 3: otwarcie książki 4
min 4: zamknięcie i zwrot książki 4 (czas wypożyczenia 4 minuty)
min 14: zamknięcie i zwrot książki 2 (czas wypożyczenia 14 minut)
min 15: otwarcie książki 3
min 16: otwarcie książki 5
min 17: zamknięcie i zwrot książki 5 (czas wypożyczenia 17 minut)
min 37: zamknięcie i zwrot książki 3 (czas wypożyczenia 37 minut)
min 38: zamknięcie i zwrot książki 1 (czas wypożyczenia 38 minut)

Przykładowe wejście 1 Przykładowe wyjście 1
5
1 2 2 3
10 1 4
20 1 5
1 0
1 0
110