Citations

Grace wants to read one science book. To understand it fully, she reads every book it cites, then every book those books cite, and so on. There are $N$ books in total, numbered from $1$ to $N$. Reading book $i$ itself and returning it takes $K_i$ minutes. Book $i$ contains a citation list of $F_i$ books. The book she originally wanted to read is book $1$. Every book except book $1$ appears in exactly one citation list, and there is no cycle of citations. Hence the citations form a tree rooted at book $1$.

Reading one book proceeds as follows.

• Open the book and read its citation list, which takes $1$ minute.
• Read all books in the list, in any order she chooses.
• Read the main text and return the book, which takes $K_i$ minutes.

All books are already borrowed at time $0$. The borrow time of book $i$ is the moment it is returned. Choose the reading order so that the sum of borrow times over all books is minimized.

The first line contains the integer $N$ ($1 \le N \le 100000$). The next $N$ lines describe books $i = 1$ through $N$ in order. Each line contains $K_i$ ($1 \le K_i \le 1000$), $F_i$ ($0 \le F_i < N$), followed by $F_i$ book numbers cited by book $i$. Every book number except $1$ appears exactly once across all citation lists.

Print a single positive integer, the minimum possible total borrow time over all books.

Since every book is borrowed at time $0$, the answer equals the sum of the moments at which the books are closed. For a book $u$ with children $v$, the total time of its subtree does not depend on the order and equals $T(u) = 1 + K_u + \sum T(v)$, so the whole process always takes $N + \sum K_i$. The problem therefore reduces to choosing the order of children at each node, and the total is the sum inside the child subtrees plus the waiting time between siblings.