Brexit Negotiations

As everyone knows, Brexit negotiations are under way, but whether they will actually finish in time is still unknown.

The negotiations proceed topic by topic. To organise the negotiations as effectively as possible, each topic is discussed and finalised in a separate meeting, one meeting at a time.

This arrangement exists partly because some topics have (non-cyclic) dependencies on each other: for example, one cannot have a meaningful talk about tariffs before deciding upon the customs union. The EU may choose any order in which to negotiate the topics, as long as the stated dependencies hold and all topics are covered.

Each topic is discussed at length using every available piece of data, including key results from past meetings. At the start of each meeting, the delegates spend one extra minute for each meeting that has already taken place by that point, even unrelated ones, to recap the discussions and understand how the conclusions were reached. See Figure B.1 for an example.

Nobody likes long meetings. The EU asks you to help order the meetings so that the longest meeting takes as little time as possible.

Figure B.1: Illustration of how time is spent in each meeting in a solution to Sample Input 2.

The input consists of:

• One line containing an integer n (1 ≤ n ≤ 4 · 105), the number of topics to be discussed. The topics are numbered from 1 to n.
• n lines describing the negotiation topics.
  The ith such line starts with two integers ei and di (1 ≤ ei ≤ 106, 0 ≤ di < n), the number of minutes needed to reach a conclusion on topic i and the number of other specific topics that must be dealt with before topic i can be discussed.
  The remainder of the line has di distinct integers bi,1, . . . , bi,di (1 ≤ bi,j ≤ n and bi,j ≠ i for each j), the list of topics that need to be completed before topic i.

It is guaranteed that there are no cycles in the topic dependencies, and that the sum of di over all topics is at most 4 · 105.

Output the minimum possible length of the longest of all meetings, if meetings are arranged optimally according to the above rules.