[R79C]卡片 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 张卡片，编号为 $1,2,\ldots,n$。第 $i$ 张卡片的颜色编号为 $c_i$，权值为 $w_i$。两张卡片的颜色编号相同，当且仅当它们的颜色相同。

你需要从中选择至少一张卡片，要求任意两张被选中的卡片颜色不同。所选卡片的总权值等于这些卡片的权值之和。

请问，所选卡片的总权值最大是多少？

格式

输入格式

第一行包含一个整数 $n$，表示卡片的数量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $c_i,w_i$，分别表示第 $i$ 张卡片的颜色编号和权值。

同一行中相邻整数之间用空格分隔。

输出格式

输出一行，包含一个整数，表示所选卡片的最大总权值。

样例

样例输入 #1

6
1 4
2 7
1 9
3 5
2 6
4 2

样例输出 #1

23

样例解释 #1

选择编号为 $2,3,4,6$ 的卡片，它们的颜色编号分别为 $2,1,3,4$，互不相同，总权值为 $7+9+5+2=23$。这是能够得到的最大总权值。

样例输入 #2

4
1 3
1 8
1 8
1 5

样例输出 #2

8

样例解释 #2

所有卡片的颜色都相同，只能选择其中一张。选择编号为 $2$ 或 $3$ 的卡片，均可得到最大总权值 $8$。

样例输入 #3

3
1 1000000000
2 1000000000
3 1000000000

样例输出 #3

3000000000

样例解释 #3

三张卡片的颜色互不相同，可以全部选择，总权值为 $3000000000$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$2000$
$2$	$70$	$2 \times 10^5$

对于 $100\%$ 的数据，$1\le n\le 2 \times 10^5$，$1\le c_i\le n$，$1\le w_i\le 10^9$。