Minimum Task Completion Time

You are given n tasks, numbered from 1 to n. Each task i has an associated time T_i (the time required to complete the task) and a list of prerequisites. A task can only begin after all of its prerequisite tasks are finished.

The tasks are represented in the following format:

Each task is described by a line containing:
T K A₁ A₂ ... A_K, where T is the time the task takes, K is the number of prerequisite tasks, and A₁, A₂, ..., A_K are the indices of the prerequisite tasks.

You need to determine the minimum total time required to complete all tasks. Note that multiple tasks can be processed in parallel if their prerequisites are met.

The completion time for a task i can be expressed as:

$$ completion_i = T_i + \max_{j \in P_i} (completion_j) $$

where \(P_i\) is the set of prerequisite tasks for task i. The answer is the maximum of all completion times: $$ answer = \max_{1 \le i \le n} (completion_i) $$

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), which denotes the number of tasks. The next n lines each contain the description of a task in the following form:

T K A1 A2 ... AK

Here, T (1 ≤ T ≤ 10⁹) is the time required for the task, K (0 ≤ K ≤ n-1) is the number of prerequisites, and A1, A2, ..., AK are the indices of the prerequisite tasks (1-indexed).

outputFormat

Output a single integer which is the minimum total time required to complete all tasks.

## sample

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

10