题目描述

某工厂有 $n$ 项待完成的任务，每项任务需要一定时间来执行。部分任务之间存在依赖关系：某些任务必须在其所有前置任务完成后才能开始。编号为 $1$ 的任务没有任何前置任务，可以最先执行。

给定 $n$ 项任务的耗时和依赖关系，求完成全部任务的最短总耗时。假设工厂有足够多的工人，可以同时执行任意多项互不依赖的任务。

输入格式

第 $1$ 行一个整数 $n\ (3 \le n \le 10{,}000)$，表示任务数。

第 $2$ 至 $n+1$ 行，每行若干空格分隔的整数：

• 第一个整数为任务编号（保证从 $1$ 到 $n$ 递增）；
• 第二个整数为该任务的耗时 $len\ (1 \le len \le 100)$；
• 之后为该任务的前置任务编号列表，以 $0$ 结束。无前置任务时只写一个 $0$。

每个前置任务的编号一定小于当前任务编号。前置任务总数不超过 $100$ 个。输入中无多余空格。

输出格式

一个整数，表示完成所有任务的最短总耗时。

样例

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

23