codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1082C.md (2378B)


      1 Source: https://codeforces.com/problemset/problem/1082/C
      2 
      3 C. Multi-Subject Competition
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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!).
     24 
     25 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.
     26 
     27 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.
     28 
     29 (Of course, Alex doesn't have any spare money so each delegate he chooses must participate in the competition).
     30 
     31 Input
     32 
     33 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.
     34 
     35 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.
     36 
     37 Output
     38 
     39 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.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 6 3
     47 2 6
     48 3 6
     49 2 5
     50 3 5
     51 1 9
     52 3 1
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 22
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 5 3
     65 2 6
     66 3 6
     67 2 5
     68 3 5
     69 1 11
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 23
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 5 2
     82 1 -1
     83 1 -5
     84 2 -1
     85 2 -1
     86 1 -10
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 0
     93 ```
     94 
     95 Note
     96 
     97 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$.
     98 
     99 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$.
    100 
    101 In the third example it's impossible to obtain a non-negative sum.