Each of Bessie’s NN (2≤N≤1052≤N≤105) bovine buddies (conveniently labeled 1…N1…N) owns her own farm. For each 1≤i≤N1≤i≤N, buddy ii wants to visit buddy aiai (ai≠iai≠i).
Given a permutation (p1,p2,…,pN)(p1,p2,…,pN) of 1…N1…N, the visits occur as follows.
For each ii from 11 up to NN:
-
If buddy apiapi has already departed her farm, then buddy pipi remains at her own farm.
-
Otherwise, buddy pipi departs her farm to visit buddy apiapi’s farm. This visit results in a joyful "moo" being uttered vpivpi times (0≤vpi≤1090≤vpi≤109).
Compute the maximum possible number of moos after all visits, over all possible permutations pp.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains NN.
For each 1≤i≤N1≤i≤N, the i+1i+1-st line contains two space-separated integers aiai and vivi.
OUTPUT FORMAT (print output to the terminal / stdout):
A single integer denoting the answer.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
4
2 10
3 20
4 30
1 40
SAMPLE OUTPUT:
90
If p=(1,4,3,2)p=(1,4,3,2) then
-
Buddy 11 visits buddy 22's farm, resulting in 1010 moos.
-
Buddy 44 sees that buddy 11 has already departed, so nothing happens.
-
Buddy 33 visits buddy 44's farm, adding 3030 moos.
-
Buddy 22 sees that buddy 33 has already departed, so nothing happens.
This gives a total of 10+30=4010+30=40 moos.
On the other hand, if p=(2,3,4,1)p=(2,3,4,1) then
-
Buddy 22 visits buddy 33's farm, causing 2020 moos.
-
Buddy 33 visits buddy 44's farm, causing 3030 moos.
-
Buddy 44 visits buddy 11's farm, causing 4040 moos.
-
Buddy 11 sees that buddy 22 has already departed, so nothing happens.
This gives 20+30+40=9020+30+40=90 total moos. It can be shown that this is the maximum possible amount after all visits, over all permutations pp.
SCORING:
-
Test cases 2-3 satisfy ai≠ajai≠aj for all i≠ji≠j.
-
Test cases 4-7 satisfy N≤103N≤103.
-
Test cases 8-11 satisfy no additional constraints.