15859번 - Citations 서브태스크다국어

문제

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 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:

• 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.

입력

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 K_i (1 ≤ K_i ≤ 1000), the number of minutes the book takes to read. Then follows a number F_i (0 ≤ F_i < N), followed by F_i numbers, the indices of the books that book i refers to.

출력

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

제한

서브태스크 1 (20점)

• 1 ≤ N ≤ 10
• 1 ≤ K_i ≤ 1000

서브태스크 2 (30점)

• 1 ≤ N ≤ 50
• 1 ≤ K_i ≤ 10
• F_i ≤ 5

서브태스크 3 (20점)

• 1 ≤ N ≤ 100000
• 1 ≤ K_i ≤ 1000
• F_i ≤ 5

서브태스크 4 (30점)

• 1 ≤ N ≤ 100000
• 1 ≤ K_i ≤ 1000

힌트

• 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)