Multi-Subject Competition

题意翻译

### 题目描述 现在有 $n$ 个人分成 $m$ 组，第 $i$ 个人属于第 $s_i$ 组，能力值为 $r_i$ 。 现在你要选择任意一些组，在这些组中选择相同数目的人，最大化他们的能力值总和。 ### 输入格式 第一行两个整数 $n$ , $m$ $(1\le n,m \le 10^5)$. 接下来 $n$ 行每行两个整数 $s_i$ , $r_i$. $(1\le s_i \le m, |r_i|\le 10^4)$ . ### 输出格式 输出一个整数表示最大的能力值总和。如果答案小于 $0$, 输出 $0$ .

题目描述

A multi-subject competition is coming! The competition has $ m $ different subjects participants can choose from. That's why Alex (the coach) should form a competition delegation among his students. He has $ n $ candidates. For the $ i $ -th person he knows subject $ s_i $ the candidate specializes in and $ r_i $ — a skill level in his specialization (this level can be negative!). The rules of the competition require each delegation to choose some subset of subjects they will participate in. The only restriction is that the number of students from the team participating in each of the chosen subjects should be the same. Alex decided that each candidate would participate only in the subject he specializes in. Now Alex wonders whom he has to choose to maximize the total sum of skill levels of all delegates, or just skip the competition this year if every valid non-empty delegation has negative sum. (Of course, Alex doesn't have any spare money so each delegate he chooses must participate in the competition).

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5 $ , $ 1 \le m \le 10^5 $ ) — the number of candidates and the number of subjects. The next $ n $ lines contains two integers per line: $ s_i $ and $ r_i $ ( $ 1 \le s_i \le m $ , $ -10^4 \le r_i \le 10^4 $ ) — the subject of specialization and the skill level of the $ i $ -th candidate.

输出格式

Print the single integer — the maximum total sum of skills of delegates who form a valid delegation (according to rules above) or $ 0 $ if every valid non-empty delegation has negative sum.

输入输出样例

输入样例 #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

说明

In the first example it's optimal to choose candidates $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ , so two of them specialize in the $ 2 $ -nd subject and other two in the $ 3 $ -rd. The total sum is $ 6 + 6 + 5 + 5 = 22 $ . In the second example it's optimal to choose candidates $ 1 $ , $ 2 $ and $ 5 $ . One person in each subject and the total sum is $ 6 + 6 + 11 = 23 $ . In the third example it's impossible to obtain a non-negative sum.

题意翻译

### 题目描述 现在有 $n$ 个人分成 $m$ 组，第 $i$ 个人属于第 $s_i$ 组，能力值为 $r_i$ 。 现在你要选择任意一些组，在这些组中选择相同数目的人，最大化他们的能力值总和。 ### 输入格式 第一行两个整数 $n$ , $m$ $(1\le n,m \le 10^5)$. 接下来 $n$ 行每行两个整数 $s_i$ , $r_i$. $(1\le s_i \le m, |r_i|\le 10^4)$ . ### 输出格式 输出一个整数表示最大的能力值总和。如果答案小于 $0$, 输出 $0$ .