← 返回题目列表

Codeforces · 1082/C

C. 多学科竞赛

中文机器翻译题面 查看原题

多学科竞赛来了!比赛有 $$$m$$$ 不同的科目可供参赛者选择。这就是为什么亚历克斯(教练)应该在他的学生中组成一个比赛代表团。

他有 $$$n$$$ 个候选人。对于第 $$$i$$$ 人来说,他知道候选人擅长的主题 $$$s_i$$$ 和 $$$r_i$$$ — 其专业领域的技能水平(该水平可以为负!)。

比赛规则要求每个代表团选择他们将参加的一些科目。唯一的限制是参加每个选定科目的团队中的学生人数必须相同。

Alex决定每个候选人只参加他擅长的主题。现在Alex想知道他必须选择谁来最大化所有代表的技能水平总和,或者如果每个有效的非空代表团都有负总和,则跳过今年的比赛。

(当然,Alex没有闲钱,所以他选择的每个代表都必须参加比赛)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^5$$$) — 考生数量和科目数量。

接下来的 $$$n$$$ 行每行包含两个整数:$$$s_i$$$ 和 $$$r_i$$$ ($$$1 \le s_i \le m$$$, $$$-10^4 \le r_i \le 10^4$$$) — 第 $$$i$$$ 候选人的专业主题和技能水平。

输出

打印单个整数 — 组成有效代表团的代表的最大技能总和(根据上述规则)或 $$$0$$$(如果每个有效的非空代表团都有负数)。

示例

输入 #1

6 3
2 6
3 6
2 5
3 5
1 9
3 1

输出 #1

22

输入 #2

5 3
2 6
3 6
2 5
3 5
1 11

输出 #2

23

输入 #3

5 2
1 -1
1 -5
2 -1
2 -1
1 -10

输出 #3

0

注意

在第一个示例中,最好选择候选人 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$,因此其中两人专注于 $$$2$$$-nd 科目,另外两人专注于 $$$3$$$-rd。总和为 $$$6 + 6 + 5 + 5 = 22$$$。

在第二个示例中,最佳选择候选 $$$1$$$、$$$2$$$ 和 $$$5$$$。每个科目 1 人,总金额为 $$$6 + 6 + 11 = 23$$$。

在第三个示例中,不可能获得非负和。