1349: 打击邪恶的2e
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：98
Solved：2
Description
学校ACM集训队有个私底下的小群,叫华莱士。群主2e941sb，独裁专政，滥用特权，乱行暴政。今天下苦2e久矣，遂苟弱果冻揭竿而起，号召群雄反击2e。
果冻找到了厉害的魔法大师大朱，大朱掌握了 $n$ 种魔法，每种魔法都具有一种属性。但大朱法力有限，他的每种魔法都只能使用最多一次，为了打败邪恶的2e，果冻需要让大朱的魔法伤害最大化。大朱拥有两种施法模式单发和双连。单发时，大朱使用对应魔法，造成对应伤害。双发时，大朱同时使用两种魔法，如果两种魔法的属性不同则，两种魔法中大朱可以任选一种魔法的伤害翻倍。大朱和果冻都笨笨的，不知道怎么最大化造成的伤害，故求救于你，为了华莱士的未来，请绝顶聪明的你出手吧。
Input
第一行输入一个正整数 $t(1 \le t \le 10^5 )$ 代表$t$个测试用例
每个测试用例的第一行输入一个整数 $n(1\leq n \leq 3\times 10^5)$表示大朱掌握魔法的数量。
接下来的 $n$ 行，第 $i$ 行包含两个值， $damge_i$ 和 $type_i$，代表大朱掌握第 $i$ 个魔法的伤害和魔法属性。
输入保证 $\sum n\le 5\times 10^5 , 1 \le damage_i \le 10^9 , 1 \le type_i \le n$
Output
对于每个测试用例输出一个值 $maxn$ 代表大朱可以造成的伤害的最大值。
Sample Input Copy
2
5
100 1
2 1
3 2
4 3
5 5
2
1 1
1000000 1Sample Output Copy
219
1000001HINT
对于第一组测试用例，大朱可以双连释放第 $ 1 , 3 $ 个魔法令第 $1$ 个魔法伤害翻倍，双连释放第 $ 2 , 5 $ 个魔法，令第 $5$ 个魔法伤害翻倍，单发释放第 $4$ 个魔法。最终造成的最大伤害为 $219$ ，不存在比这伤害更大的释放方式了。