放学铃声响起，教室里 N 名同学打算依次离开座位、互相串门。第 i 名同学想去拜访第 a_i 名同学（a_i \neq i），若成功拜访则带来 v_i 点愉悦值。

同学们按照某个顺序 (p_1, p_2, \ldots, p_N) 依次行动，规则如下：

• 当轮到第 p_t 名同学时，若第 a_{p_t} 名同学仍在座位上（尚未离座去拜访他人），则第 p_t 名同学离开座位前去拜访，获得 v_{p_t} 点愉悦值；
• 若第 a_{p_t} 名同学已经离座，则第 p_t 名同学本次拜访失败，留在原座位，愉悦值为 0。

注意：同学只有在成功拜访他人时才会离开座位；拜访失败则继续留在原位，仍可被其他同学拜访。

请求出在所有可能的离座顺序中，愉悦值总和的最大值。

第一行包含一个正整数 N，表示同学人数。

接下来 N 行，第 i 行包含两个整数 a_i 和 v_i，分别表示第 i 名同学想拜访的同学编号与成功拜访带来的愉悦值。

输出一行，包含一个整数，表示愉悦值总和的最大值。

样例输入 4

18
2 8
3 5
1 11
2 7
2 6
5 4
8 3
9 12
10 9
7 1
9 10
11 2
12 15
15 14
14 13
15 0
16 20
17 18

样例输出 4

139

样例说明 1

拜访关系：1\to2、2\to4、3\to2、4\to5、5\to4。

其中同学 4 和同学 5 互相拜访，形成一个"互访"（4\to5\to4）。在任意顺序下，这里必有一人找不到对方——应让愉悦值最小的那人失败，即同学 5（v_5=2）。其余同学均可成功拜访。

最优顺序 (1,3,2,4,5)：

• 同学 1 拜访同学 2（在座）：+5；
• 同学 3 拜访同学 2（在座）：+3；
• 同学 2 拜访同学 4（在座）：+8；
• 同学 4 拜访同学 5（在座）：+7；
• 同学 5 拜访同学 4（已离座）：失败。

总愉悦值 = 5+3+8+7 = 23。

数据范围

对于所有测试数据，保证：2 \leq N \leq 10^5，1 \leq a_i \leq N，a_i \neq i，0 \leq v_i \leq 10^9。

特殊性质 A：满足有且只有 1 个人无法获得愉悦值。

月赛26年6月图论