Minimum Time to Complete Tasks

There are N tasks to complete, where 3 <= N <= 10000. Each task has an integer duration between 1 and 100.

Some tasks have prerequisites. A task may start only after all of its prerequisite tasks are complete. For task K, every prerequisite task number is between 1 and K - 1. At least one task has no prerequisites, and task 1 always has none.

Tasks with no prerequisite relationship between them may be performed at the same time. Find the minimum time required to complete all tasks.

The first line contains N, the number of tasks.

The next N lines describe tasks 1 through N in order. Each line first contains the duration of the task, followed by the number C of prerequisite tasks (0 <= C <= 100). It is then followed by the C prerequisite task numbers.

Print one line containing the minimum time required to complete all tasks.

The finish time of a task is its own duration plus the latest finish time among all of its prerequisites. The total completion time is the maximum finish time among all tasks.