Problem H
Citations

CC0 Public Domain, congerdesign via Pixabay.

Grace is going to read a certain scientific book. However, she is very careful about always reading the sources that books refer to, and also the sources of the sources, and so on. It usually ends up being the case that she reads quite a lot more books than just the one she originally intended to read. The librarians are constantly complaining about Grace’s excessive borrowing of books, and so she now wants to find an order in which to read the books that minimizes the total borrow time.

There are $N$ books that she eventually will need to read. The books are numbered from $1$ to $N$, and book $i$ takes $K_ i$ minutes to read. Every book $i$ has a citation list containing $F_ i$ books. The book Grace originally wants to read has index $1$. Before starting with book $1$ Grace has already borrowed all $N$ books.

When Grace reads a book she does the following:

• First she opens the book and reads the citation list, which takes a minute,

• then she reads all the books that are in the list, in some order of her own choosing,

• thereafter she reads the actual book and returns it to the library, which takes $K_ i$ minutes.

You now want to compute the minimum total borrow time for all books, given that Grace reads the books in an optimal order. Books may contain empty citation lists, and every book except book $1$ will occur in exactly one citation list. There will be no cycles of citations.

Input

The first line contains the integer $N$ ($1 \le N \le 100\, 000$). Then follows $N$ lines, one for each book $1$ to $N$. On each such row there will be a number $K_ i$ ($1 \le K_ i \le 1\, 000$), the number of minutes the book takes to read. Then follows a number $F_ i$ ($0 \le F_ i < N$), followed by $F_ i$ numbers, the indices of the books that book $i$ refers to.

Output

Output a single positive integer, the minimum total borrow time for all books.

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. Your final score will be the maximum score of a single submission.

Explanation of Sample 1

time 1: open book 1
time 2: open book 2
time 3: open book 4
time 4: close book 4 (borrow time 4 minutes)
time 14: close book 2 (borrow time 14 minutes)
time 15: open book 3
time 16: open book 5
time 17: close book 5 (borrow time 17 minutes)
time 37: close book 3 (borrow time 37 minutes)
time 38: close book 1 (borrow time 38 minutes)

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

110