Farm Chores Scheduling

John's farm has a list of n chores that must be completed before the cows can be milked. Each chore i requires a certain amount of time, denoted as t_i, to finish. Some chores have prerequisite chores that must be completed before they can begin. In particular, chore 1 has no prerequisites and can start immediately. For any chore i (with i > 1), its prerequisites can only be chosen from among chores 1 through i-1.

Since unrelated chores can be performed concurrently (assuming an unlimited number of workers), the goal is to complete all chores in the minimum total time. Define the completion time for chore i as:

\( C_i = t_i + \max_{j \in P_i} C_j \)

where \( P_i \) is the set of prerequisites for chore i. If \( P_i \) is empty, then \( C_i = t_i \). The answer to the problem is the maximum completion time among all chores:

\( \max_{1 \leq i \leq n} C_i \)

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of chores. Each of the following n lines describes a chore in order. The i-th line contains an integer t (the time required for chore i), followed by an integer m representing the number of prerequisites. If m is greater than 0, then the line is followed by m integers representing the indices of the prerequisite chores (each in the range from 1 to i-1).

outputFormat

Output a single integer representing the minimum total time required to complete all the chores.

sample

5
3 0
2 1 1
4 1 1
2 2 2 3
3 1 4

12