题目描述

给定 $n$ 张卡牌，每张卡牌有对应的颜色 $c_i$ 和点数 $a_i$。

你可以进行以下任意次操作，你的初始得分为 $0$。

• 选择两张不同颜色的卡牌 $i,j$，得分增加 $a_i+a_j$，并丢弃其中一张卡牌。

求得分最大值。

输入格式

一行一个整数 $n$，表示卡牌数量。

以下 $n$ 行，每行两个整数 $a_i,c_i$，表示点数和颜色。

输出格式

一行一个整数 $x$，表示得分最大值。

4
5 1
3 2
-1 1
4 2

20

提示

【样例解释】

• 在第一次操作中，选中卡牌 $1$ 和 $2$，分数增加 $8$ 分，丢弃第 $2$ 张牌。
• 在第二次操作中，选中纸牌 $3$ 和 $4$，得分增加 $3$ 分，丢弃第 $3$ 张牌。
• 第三次操作选择纸牌 $1$ 和 $4$，得分增加 $9$ 分。 弃掉第 $1$ 张牌。

共计得分为 $20$ 分，可以证明这是最大值。

【数据范围与约定】

对于全部数据，均满足 $2 \le n \le 5\times 10^5,-10^9\le a_i\le 10^9,1\le c_i \le n$。

• Subtask $1$（$13$ pts）：$c_1=1,c_i=2(2 \le i \le n)$。
• Subtask $2$（$22$ pts）：$n \ge 3,c_1=c_2=1,c_i=2(3 \le i \le n),a_i\ge 0(1\le i \le n)$。
• Subtask $3$（$10$ pts）：$n \ge 3,c_1=c_2=1,c_i=2(3 \le i \le n)$。
• Subtask $4$（$28$ pts）：$c_i \le 2(1\le i \le n)$。
• Subtask $5$（$27$ pts）：无特殊限制。