인용

Grace는 과학책 한 권을 읽으려고 한다. 책을 끝까지 이해하기 위해 그 책이 인용한 모든 책을 읽고, 그 책들이 인용한 책들도 차례로 읽는다. 읽어야 할 책은 모두 $N$권이며 $1$번부터 $N$번까지 번호가 있다. 책 $i$를 실제로 읽고 반납하는 데는 $K_i$분이 걸린다. 책 $i$에는 $F_i$권의 인용 목록이 들어 있다. 처음에 읽고 싶었던 책은 $1$번이다. $1$번을 제외한 모든 책은 정확히 하나의 인용 목록에만 등장하며 인용 관계에 사이클이 없다. 따라서 인용 관계는 $1$번을 루트로 하는 트리를 이룬다.

책 한 권을 읽는 절차는 다음과 같다.

• 책을 펴고 인용 목록을 읽는 데 $1$분이 걸린다.
• 목록에 있는 책들을 자신이 정한 순서대로 모두 읽는다.
• 본문을 읽고 도서관에 반납하는 데 $K_i$분이 걸린다.

모든 책은 시각 $0$에 이미 빌린 상태이다. 책 $i$의 대출 시간은 그 책을 반납하는 시각이다. 읽는 순서를 잘 정해 모든 책의 대출 시간 합을 최소로 하라.

첫째 줄에 정수 $N$이 주어진다 ($1 \le N \le 100000$). 다음 $N$개의 줄에는 $i=1$부터 $N$까지 순서대로 책 $i$의 정보가 주어진다. 각 줄은 $K_i$ ($1 \le K_i \le 1000$), $F_i$ ($0 \le F_i < N$), 그리고 인용된 $F_i$개의 책 번호로 이루어진다. $1$번을 제외한 모든 책 번호는 전체 입력에서 정확히 한 번만 인용 목록에 등장한다.

모든 책의 대출 시간 합의 최솟값을 나타내는 양의 정수 하나를 출력한다.

모든 책을 시각 $0$에 빌리므로 답은 각 책이 닫히는 시각들의 합과 같다. 한 책의 자식 서브트리들을 처리하는 데 걸리는 전체 시간은 순서와 무관하게 $T(u) = 1 + K_u + \sum T(v)$로 고정되며, 전체 처리 시간은 $N + \sum K_i$이다. 따라서 문제는 각 노드에서 자식들을 어떤 순서로 읽을지 정하는 문제로 귀결되며, 전체 합은 자식 서브트리 내부의 합에 자식들 사이의 대기 시간이 더해진 형태가 된다.