Tommy is an all-around winter Olympian. In fact, he is so good he can participate in any event and easily win. Tommy is also a genius scientist and can clone himself infinitely to participate in multiple events at once.

There are $N$ events at the Olympics, numbered $1$ to $N$, and event $i$ takes $T_i$ minutes. Unfortunately, the organizers have come up with a plan to stop Tommy. Each event $i$ will have $R_i$ prerequisite events, where Tommy must complete all the prerequisite events of event $i$ before competing in event $i$. The organizers may have also created these prerequisites in a loop. For example, he must do event $X$ before event $Y$, event $Y$ before event $Z$, and event $Z$ before $X$. Since Tommy cannot bypass this, he will ignore those events.

Help Tommy find out the minimum time he can take to complete all the events he can!

Constraints

$1\le N\le 5\times {10}^3$

$1\le T_i\le {10}^4$

$0\le R_i<N$

Input Specification

The first line contains one integer $N$, the number of events.

The next $N$ lines begin with two space-separated integers, the $i^{\text{th}}$ line containing information for event $i$: $T_i$, the time event $i$ takes, and $R_i$, the number of prerequisite events event $i$ has. $R_i$ space-separated integers will follow, indicating the events Tommy must finish before competing in event $i$.

Output Specification

Output the minimum number of minutes Tommy can take to complete all the events he can.

Sample Input

5
30 1 3
20 0
10 2 4 5
10 0
10 0

Sample Output

50

Explanation

Tommy can be doing events $4$ and $5$ at the beginning. After completing event $4$ and $5$ in $10$ minutes, he can then do event $3$. After completing event $3$, after an additional $10$ minutes, he can do event $1$, which takes $30$ minutes. This sums to $10+10+30=50$ minutes. Event $2$ can be done anytime in this $50$ minute time frame, so it does not need to be added to the total time.