Problem H
Odniesienia

CC0 Public Domain, congerdesign via Pixabay.

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

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktó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. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

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)

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

110