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.