Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem I: 五队-长春-魔法实验

Problem I: 五队-长春-魔法实验

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 54  Solved: 4
[Submit][Status][Web Board]

Description

cc喜欢魔法,更喜欢做魔法实验.cc现在有n+1种魔法物质,编号从0-n,每种魔法物质都有一个非负的魔力值.当多个魔法物质混合在一起时,会释放出大量魔力,且释放的魔力量恰好等于混合的魔法物质的魔力值之和.但是要注意,这些魔法物质之间存在着克制关系.具体来说,每种魔法物质i都有一个克制其魔力发挥的魔法物质j,若混合物中同时含有i,j,那么魔法实验就会失败,失败的魔法实验不会放出任何魔力.0号物质比较特殊,其魔力值为0,且不与其他任何物质克制或被克制,在魔法实验中可以当作催化剂.现在,cc想知道,从这n+1种物质中选若干种出来做实验,所能获得的最大魔力值是多少.

Input

第一行一个正整数T,表示有多少组输入数据

每组数据第一行一个正整数n(2<=n<=1e6)

接下来n,每行两个正整数,依次描述物质1-n的魔力值(<=2e5)以及克制其魔力发挥的魔法物质编号

Output

每组数据输出一个正整数,代表实验多能获得的最大魔力值.

Sample Input

1
3
15 3
45 1
60 2

Sample Output

60

HINT

[Submit][Status][Web Board]