Background

TG T2 rrc.cpp

Description

过山车是大家喜爱的游乐项目，当然，每一趟过山车也分为许多阶段，例如上坡，下坡，回环等等，合理安排每一个阶段能为乘坐过山车的游客带来更多的刺激感和紧张感。

现在有一项过山车工程需要你去设计。我们认为，对于过山车的第 $i$ 个阶段，如果这个阶段的前面是阶段 $a_i$，那么这个过山车可以获得 $w_i$ 的刺激感。为了简化工程，对于过山车的每个阶段，有且仅有一个 $a_i$。

现在你需要最大化这个过山车项目的刺激感。

Format

Input

输入共 $n+1$ 行。

第一行，输入一个数 $n$，表示过山车拥有的阶段数。

第 $2\sim n+1$ 行，每行输入两个数 $a_i,w_i$，意义如上。

Output

输出一个数 $ans$，表示经过调整后，这个过山车项目刺激感的最大值。

Samples

5
2 3
4 4 
2 5
1 5
1 3

14

样例 2 参见附件 rrc02.in\rrc02.ans。

样例 3 参见附件 rrc03.in\rrc03.ans。

Sample Explanation

Sample 1 Explanation

在所有重排方式中，将项目按照 $5\rightarrow1\rightarrow4\rightarrow2\rightarrow3$ 的方式排列可以获得最大的刺激感，为 $0+0+5+4+5=14$。

Limitation

特殊性质 A：保证 $a_i$ 互不相同。

特殊性质 B：保证数据完全随机。

对于 $100\%$ 的数据，保证 $n\leq 2\times 10^5,a_i\not=i,a_i\in[1,n],1\leq w_i\leq 10^4$。

时空限制：1000ms/256MB。