Description

There are $N (1\le N\le 1000)$ cows (numbered from $1$ to $N$) participating in a special relay race, where multiple cows are allowed to run simultaneously.

At time $t=0$, cow $1$ starts running along the track.

Normally, cow $i$ needs $L_i (1\le L_i\le 1000)$ seconds to complete one lap. At the instant it crosses the start line again, it will notify $M_i (1\le M_i\le N)$ cows $A_{ij} (1\le j\le M_i)$ to start. Note that it is possible that $M_i=0$ and the list $A_i$ does not exist.

Every cow that starts racing will, upon returning to the start line, notify other cows to start. It is possible that multiple cows notify the same cow to start, but each cow is willing to run only one lap, so any cow starts at most once.

The farmer wants you to determine the total race time (that is, from the race start to the moment when the last cow crosses the finish line).

Input Format

The first line contains an integer $N$, the number of participating cows.

Lines $2$ to $N+1$: line $i+1$ contains multiple space-separated integers: $L_i$, $M_i$, and $M_i$ integers $A_{ij}$.

Output Format

Output a single integer, the time when the entire race ends.

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

14

Hint

Translated by ChatGPT 5