시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 4 | 3 | 3 | 75.000% |
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 Ki minutes to read. Every book i has a citation list containing Fi 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:
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.
The first line contains the integer N (1 ≤ N ≤ 100000). Then follows N lines, one for each book 1 to N. On each such row there will be a number Ki (1 ≤ Ki ≤ 1000), the number of minutes the book takes to read. Then follows a number Fi (0 ≤ Fi < N), followed by Fi numbers, the indices of the books that book i refers to.
Output a single positive integer, the minimum total borrow time for all books.
5 1 2 2 3 10 1 4 20 1 5 1 0 1 0
110