## Mock CCC '22 Contest 2 J5 - Dominating the Olympics

View as PDF

Points: 10
Time limit: 1.5s
Java 2.5s
Python 3.5s
Memory limit: 512M

Author:
Problem types

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 events at the Olympics, numbered to , and event takes minutes. Unfortunately, the organizers have come up with a plan to stop Tommy. Each event will have prerequisite events, where Tommy must complete all the prerequisite events of event before competing in event . The organizers may have also created these prerequisites in a loop. For example, he must do event before event , event before event , and event before . 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!

#### Input Specification

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

The next lines begin with two space-separated integers, the line containing information for event : , the time event takes, and , the number of prerequisite events event has. space-separated integers will follow, indicating the events Tommy must finish before competing in event .

#### 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 and at the beginning. After completing event and in minutes, he can then do event . After completing event , after an additional minutes, he can do event , which takes minutes. This sums to minutes. Event can be done anytime in this minute time frame, so it does not need to be added to the total time.