Maximum Cycle Time in Water Puddles

During rainfall, water puddles form on the ground. Each puddle directs water to exactly one other specific puddle (i.e. each puddle has at most one outgoing connection), and water never flows backward. As a result, several puddles may flow into the same puddle. On this day, mixed with rain and drizzle, there is exactly one duck floating in each puddle. WYH dispatches an inspector beside every puddle; each inspector marks the duck in his puddle and starts a timer when, at a specific moment, all ducks begin to drift along the water flows.

Every duck will follow the unique water path out of its starting puddle. If a duck eventually drifts back to the puddle where it was originally marked, its corresponding inspector stops the timer and records the total time taken. In other words, if a duck’s path forms a cycle that includes its starting puddle, the recorded time is the sum of the time costs along the edges in that cycle. Formally, if a cycle includes a sequence of puddles \(v_1 \to v_2 \to \cdots \to v_k \to v_1\) with corresponding time costs \(t_{v_1}, t_{v_2}, \dots, t_{v_k}\) on each edge, then the cycle time is given by

$$\text{Cycle Time} = \sum_{i=1}^{k} t_{v_i}$$

WYH has surveyed the terrain and provided you with the directional relationships (i.e. the water flow mapping) and the time cost for each stream. Your task is to compute the maximum cycle time reported by any inspector. It is guaranteed that if a duck does not belong to a cycle (i.e. it never returns to its starting puddle), then no time is recorded for that puddle.

inputFormat

The input begins with a single integer \(n\) (\(1 \leq n \leq 10^5\)) indicating the number of puddles. The next \(n\) lines each contain two space-separated integers \(f_i\) and \(t_i\). For the \(i\)-th line:

• \(f_i\) (1-indexed) indicates the destination puddle that the water flows to from puddle \(i\).
• \(t_i\) indicates the time cost for the water to flow from puddle \(i\) to puddle \(f_i\) (\(1 \leq t_i \leq 10^9\)).

It is guaranteed that every puddle has exactly one outgoing flow.

outputFormat

Output a single integer, which is the maximum cycle time among all puddles (i.e. the maximum sum of time costs over all cycles discovered). If no cycle exists, output 0.

sample

3
2 4
3 5
1 6

15