多学科竞赛来了!比赛有 $$$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$$$。
在第三个示例中,不可能获得非负和。