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).


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
6 3
2 6
3 6
2 5
3 5
1 9
3 1

Output
22

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

Output
23

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

Output
0



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:

num_students, num_cats = [int(x) for x in input().split()]

cats = [[] for _ in range(num_cats)]

for _ in range(num_students):
    cat_idx, skill = [int(x) for x in input().split()]
    cat_idx -= 1
    cats[cat_idx].append(skill)

for cat in cats:
    cat.sort(key=lambda x : -x)

entries = []

for cat in cats:
    team_size = 0
    team_skill = 0
    for skill in cat:
        team_size += 1
        team_skill += skill
        entries.append((team_size, -team_skill))

entries.sort()

best_skill = 0
total_skill = 0
curr_size = 1
for entry in entries:
    size, neg_skill = entry
    skill = -neg_skill

    if size != curr_size:
        best_skill = max(total_skill, best_skill)
        curr_size = size
        total_skill = 0

    if skill > 0:
        total_skill += skill

best_skill = max(total_skill, best_skill)

print(best_skill)


n, m = list(map(int, input().split()))
inp = tuple(([] for _ in range(m)))
for __ in range(n):
	s, r = list(map(int, input().split()))
	inp[s - 1].append(r)
for rs in inp:
	rs.sort(reverse=True)
res = 0
inp1 = list(map(iter, inp))
curs = [0] * m
for ___ in range(n):
	cur = 0
	i = 0
	while i < m:
		try:
			curs[i] += next(inp1[i])
			if curs[i] < 0:
				raise StopIteration
			cur += curs[i]
			i += 1
		except StopIteration:
			m -= 1
			try:
				inp1[i] = inp1.pop()
			except IndexError:
				pass
			try:
				curs[i] = curs.pop()
			except IndexError:
				pass
	res = max(res, cur)
print(res)


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n, m = mi()
a = [[] for i in range(m + 1)]
for i in range(n):
    s, r = mi()
    a[s].append(r)

ch = [0] * (n + 1)
for i in range(1, m + 1):
    a[i].sort(reverse=True)
    pr = 0
    for j in range(len(a[i])):
        pr += a[i][j]
        if pr > 0:
            ch[j + 1] += pr

ans = max(ch)
print(ans)


n, m = list(map(int, input().split()))
spec = {}
for i in range(n):
    s, r = list(map(int, input().split()))
    if s in spec:
        spec[s].append(r)
    else:
        spec[s] = [r]
f = n
cnt = [-1 for i in range(n + 1)]
for k, cur in list(spec.items()):
    cur.sort(reverse=True)
    for j in range(1, len(cur)):
        cur[j] += cur[j - 1]
    for j in range(1, len(cur) + 1):
        if cnt[j] == -1:
            cnt[j] = 0
        cnt[j] += max(0, cur[j - 1])
print(max(cnt))


import math

def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    m = int(buflist[1])
    sr = []
    for i in range(n):
        buf = input()
        buflist = buf.split()
        sr.append((int(buflist[0])-1, int(buflist[1]))) # zero indexing
    sr = list(reversed(list(sorted(sr, key = lambda x:x[1]))))
    sp_list = []
    for i in range(m):
        sp_list.append([])
    for i in sr:
        sp_list[i[0]].append(i[1])
    sp_list = list(reversed(list(sorted(sp_list, key = lambda x:len(x)))))
    while len(sp_list[-1]) == 0:
        sp_list.pop() # remove empty subject
    score_list = []
    for i, _ in enumerate(sp_list):
        score_list.append(0)
    max_level = 0
    st_idx = 0
    while len(sp_list) > 0:
        level = 0
        for i, _ in enumerate(sp_list):
            score_list[i] += sp_list[i][st_idx]
            if score_list[i] > 0:
                level += score_list[i]
        if level > max_level:
            max_level = level
        st_idx += 1
        while len(sp_list) > 0:
            if len(sp_list[-1]) <= st_idx:
                sp_list.pop()
                score_list.pop()
            else:
                break
    print(max_level)


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
SR=[list(map(int,input().split())) for i in range(n)]

LIST=[[] for i in range(m+1)]

for s,r in SR:
    LIST[s].append(r)

LENLIST=[0]*(m+1)
for i in range(1,m+1):
    LIST[i].sort(reverse=True)
    LENLIST[i]=len(LIST[i])

LISTSUM=[[] for i in range(m+1)]

for i in range(1,m+1):
    if LIST[i]==[]:
        continue
    LISTSUM[i].append(LIST[i][0])

    for j in range(1,LENLIST[i]):
        LISTSUM[i].append(LISTSUM[i][-1]+LIST[i][j])

LEN=len(max(LIST,key=lambda x:len(x)))

ANS=[0]*LEN

for j in range(1,m+1):
    for i in range(LENLIST[j]):
        if LISTSUM[j][i]>0:
            ANS[i]+=LISTSUM[j][i]
        else:
            break

print(max(ANS))


3.5

N, M = [*list(map(int, input().split()))]
_L = [list() for i in range(0, M)]

for i in range(0, N):
    s, r = [*list(map(int, input().split()))]
    _L[s-1].append(r)

L = []
L_sum = []

for x in _L:
    if len(x) != 0:
        x.sort(reverse=True)
        L.append(x)

L.sort(reverse=True, key=lambda x: len(x))
for x in L:
    _s = [0]*len(x)
    _s[0] = x[0]

    for i in range(1, len(x)):
        _s[i] = _s[i-1] + x[i]

    L_sum.append(_s)
        
ret = 0
for i in range(1, N+1):
    cpt = 0
    for j in range(0, len(L)):
        if len(L[j]) < i:
            break
        
        if L_sum[j][i-1] > 0:
            cpt += L_sum[j][i-1]

    ret = max(ret, cpt)

print(max(0, ret))


__author__ = 'tanunia'

from sys import stdin

n, m = [int(k) for k in stdin.readline().split()]
lst = []
for _ in range(n):
    s, r = [int(k) for k in stdin.readline().split()]
    lst.append([s - 1, r])

lst = sorted(lst, key=lambda x: -x[1])

students_num = [[0, 0] for _ in range(m)]
best_score = [0 for _ in range(n + 1)]
for it in lst:
    sub, rating = it[0], it[1]
    students_num[sub][0] += rating
    students_num[sub][1] += 1
    if students_num[sub][0] > 0:
        best_score[students_num[sub][1]] += students_num[sub][0]

print(max(best_score))


from sys import stdin, stdout
from math import *
from heapq import *
from collections import *
def inputlistint():
    return [int(x) for x in stdin.readline().split()]
def main():
    n,m=inputlistint()
    s=[]
    r=[]
    f=[]
    for _ in range(m+2):
        f.append([])
    for _ in range(n):
        a,b=inputlistint()
        s.append(a)
        r.append(b)
        f[a].append(b)
    f.sort(key=lambda x: len(x), reverse=True)
    for a in f:
        a.sort(reverse=True)
    res=0
    for k in range(len(f[0])):
        test=0
        for i in range(m+1):
            if (k>=len(f[i])):
                break
            if (k>0):
                f[i][k]=f[i][k]+f[i][k-1]
            if (f[i][k]>0):
                test=test+f[i][k]
        res=max(res,test)
    stdout.write(str(res))
    return 0

def __starting_point():
    main()
__starting_point()

'''input
5 3
2 6
3 6
2 5
3 5
1 11
'''
n, m = map(int, input().split())
a = [None] * n
s = [0] * (max(n, m) + 1)
cnt = [0] * (max(n, m) + 1)
ans = [0] * (max(n, m) + 1)
for i in range(n):
	x, y = map(int, input().split())
	a[i] = (x - 1, y)
a = sorted(a, key=lambda x:x[1], reverse=True)
for i in range(n):
	cnt[a[i][0]] += 1
	s[a[i][0]] += a[i][1]
	ans[cnt[a[i][0]]] += max(0, s[a[i][0]])
print(max(ans))

n, m = list(map(int, input().split()))
a, s = [], []
for q in range(n):
    d = list(map(int, input().split()))
    a.append(d[0])
    s.append(d[1])
d = {}
for q in range(n):
    if a[q] in d:
        d[a[q]].append(s[q])
    else:
        d[a[q]] = [s[q]]
for q in d:
    d[q].sort(reverse=True)
for q in list(d.values()):
    sum1 = 0
    for q1 in range(len(q)):
        sum1 += q[q1]
        q[q1] = sum1
f = [0]*(len(max(list(d.values()), key=lambda x: len(x)))+1)
for q in list(d.values()):
    for q1 in range(len(q)):
        if q[q1] > 0:
            f[q1] += q[q1]
print(max(f))


n,m = list(map(int,input().split()))
l = [ list() for i in range( m ) ]
for i in range( n ):
    a,b = list(map(int,input().split()))
    l[a-1].append( b )
ss = []
for i in l:
    ii = sorted( i )
    ii.reverse()
    s = 0
    i.clear()
    for c in ii:
        s += c
        if s >= 0:
            i.append( c )
    i.sort()
    ss.append( sum(i) )
ind = list( range( m ) )
s = 0
m = 0
while len( ind ) > 0:
    nind = []
    sub = 0
    for i in ind:
        ll = l[ i ]
        if len( ll ) > 0:
            s += ll.pop()
        if len( ll ) > 0:
            nind.append( i )
        else:
            sub += ss[ i ]
    m = max( m, s )
    s -= sub
    ind = nind
print( m )

# d = round(2**16)
# i = 0
# m = 0
# while d > 0:
#     s = 0
#     ss = 0
#     j = i + d
#     jj = i - d
#     j = min( j, n )
#     jj = max( 1, jj )
#     d = round( d / 2 )
#     for ll in l:
#         if j <= len( ll ) and ll[ j - 1 ] > 0:
#             s += ll[ j - 1 ]
#         if jj <= len( ll ) and ll[ jj - 1 ] > 0:
#             ss += ll[ jj - 1 ]
#     if s > m:
#         m = s
#         i = j
#     if ss > m:
#         m = ss
#         i = jj
    # print( i, j, jj)

# print( m )


n, m = [int(_) for _ in input().split()]
d = [[] for k in range(m + 1)]
for _ in range(n):
    s, r = [int(_) for _ in input().split()]
    d[s].append(r)
max_num = 0
for v in d:
    max_num = max(max_num, len(v))
sums = [0] * max_num
for i, v in enumerate(d):
    v.sort(reverse=True)
    s = 0
    for k, j in enumerate(v):
        s += j
        if s > 0:
            sums[k] += s
        else:
            break
print(max(sums))

import sys
sys.setrecursionlimit(2000)
from collections import Counter

def __starting_point():

    # single variables
    n, m = [int(val) for val in input().split()]

    delagates = {}

    for i in range(n):
        
        s, r = [int(val) for val in input().split()]
    
        if(s in delagates):
            delagates[s].append(r)
        else:
            delagates[s] = [r]


    summs = {}
    for key in delagates:
        delagates[key].sort(reverse=True)
        summ = 0
        for i in range(1, len(delagates[key])+1):
            summ += delagates[key][i-1]
            if(summ < 0):
                continue
            if(i in summs):
                summs[i] += summ
            else:
                summs[i] = summ
 
    
    summs[-1] = 0
    best = max([val for key, val in list(summs.items())])
    print(max(best, 0))



__starting_point()

from sys import stdin
n,m=list(map(int,stdin.readline().strip().split()))
adj=[[0,0] for i in range(max(m,n)+1)]
dp=[0 for i in range(max(m,n)+1)]
s=[]
for i in range(n):
    a,b=list(map(int,stdin.readline().strip().split()))
    s.append([b,a])
s.sort(reverse=True)
ans=0
for i in range(n):
    a,b=s[i][1],s[i][0]
    adj[a][0]+=1
    adj[a][1]+=b
    dp[adj[a][0]]=max(dp[adj[a][0]]+adj[a][1],dp[adj[a][0]])
print(max(dp))


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n, m = mi()
a = [[] for i in range(m + 1)]
for i in range(n):
    s, r = mi()
    a[s].append(r)

ch = [0] * (n + 1)
for i in range(1, m + 1):
    a[i].sort(reverse=True)
    pr = 0
    for j in range(len(a[i])):
        pr += a[i][j]
        if pr > 0:
            ch[j + 1] += pr

ans = max(ch)
print(ans)

#!/usr/bin/env python
# coding: utf-8

# In[22]:


n, m=list(map(int, input().rstrip().split()))
data=[]
for i in range(0,n):
    data.append( list(map(int, input().rstrip().split())))


# In[4]:





# In[ ]:





# In[64]:


def mergesortbysecond(l):
    if len(l)==1:
        return l
    llower=[]
    lupper=[]
    for i in range(0,int(len(l)/2)):
        llower.append(l[i])
    for i in range(int(len(l)/2),len(l)):
        lupper.append(l[i])
    #print(lupper)
    #print(llower)

    slower=mergesortbysecond(llower)
    supper=mergesortbysecond(lupper)

    b=0
    u=0
    sort=[]
    while b<len(slower) and u<len(supper):
        if slower[b][1]<=supper[u][1]:
            sort.append(slower[b])
            b=b+1
        elif supper[u][1]<slower[b][1]:
            sort.append(supper[u])
            u=u+1    
    #print(sort)
    if b==len(slower):
        for i in range(u,len(supper)):
            sort.append(supper[i])
    elif u==len(supper):
        for i in range(b,len(slower)):
            sort.append(slower[i])
    #print(sort)
    return sort


# In[2]:





# In[65]:


sort=mergesortbysecond(data)


# In[66]:


bsort=[]
for i in range(0,n):
    bsort.append(sort[n-i-1])


# In[67]:


dic={}
for i in range(0,n):
    if bsort[i][0] in dic:
        dic[bsort[i][0]].append(bsort[i][1])
    else:
        dic[bsort[i][0]]=[bsort[i][1]]
    


# In[68]:


array=[]
for i in range(0,n):
    array.append([])


# In[69]:


for ele in dic:
    j=0
    for i in range(0,len(dic[ele])):
        j=j+dic[ele][i]
        array[i].append(j)


# In[70]:


array


# In[71]:


ma=0

for i in range(0,len(array)):
    s=0
    for j in range(0,len(array[i])):
        s=s+max([array[i][j],0])
        
    if s>ma:
        ma=s


# In[72]:


print(ma)


# In[ ]:






n, m = map(int, input().split())
vec = [[] for j in range(100007)]
vt = [[] for j in range(100007)]
cv = []
ck = [0 for i in range(100007)]

for i in range(n):
    s, r = map(int, input().split())
    vec[s].append(r)
    if (ck[s] == 0):
        cv.append(s)
        ck[s] = 1

for i in cv:
    vec[i].sort(reverse=True)
    psum = 0
    for j in range(len(vec[i])):
        psum = psum + vec[i][j]
        vt[j].append(psum)

for i in range(100007):
    if len(vt[i]) == 0:
        break
    vt[i].sort(reverse=True)

ans = 0
for i in range(100007):
    if len(vt[i]) == 0:
        break
    tmp = 0
    for j in range(len(vt[i])):
        if (i + 1)*(j + 1) > n:
            break
        if vt[i][j] <= 0:
            break
        tmp = tmp + vt[i][j]
    ans = max(ans, tmp)

print (ans)

n, m = map(int, input().split())
vec = [[] for j in range(100007)]
vt = [[] for j in range(100007)]
cv = set()

for i in range(n):
    s, r = map(int, input().split())
    vec[s].append(r)
    cv.add(s)

for i in cv:
    vec[i].sort(reverse=True)
    psum = 0
    for j in range(len(vec[i])):
        psum += vec[i][j]
        vt[j].append(psum)

ans = 0
for i in range(100007):
    if len(vt[i]) == 0:
        break
    vt[i].sort(reverse=True)
    tmp = 0
    for j in range(len(vt[i])):
        if (i + 1)*(j + 1) > n or vt[i][j] <= 0:
            break
        tmp += vt[i][j]
    ans = max(ans, tmp)

print (ans)

n, m = map(int, input().split())
vec = [[] for j in range(100007)]
vt = [[] for j in range(100007)]

for i in range(n):
    s, r = map(int, input().split())
    vec[s].append(r)

for i in range(100007):
    vec[i].sort(reverse=True)
    psum = 0
    for j in range(len(vec[i])):
        psum += vec[i][j]
        vt[j].append(psum)

ans = 0
for i in range(100007):
    vt[i].sort(reverse=True)
    tmp = 0
    for j in range(len(vt[i])):
        if (i + 1)*(j + 1) > n or vt[i][j] <= 0:
            break
        tmp += vt[i][j]
    ans = max(ans, tmp)

print (ans)

n, m = map(int, input().split())
vec = [[] for j in range(m)]
vt = [[] for j in range(n)]

for i in range(n):
    s, r = map(int, input().split())
    vec[s - 1].append(r)

for i in range(m):
    vec[i].sort(reverse=True)
    psum = 0
    for j in range(len(vec[i])):
        psum += vec[i][j]
        vt[j].append(psum)

ans = 0
for i in range(n):
    vt[i].sort(reverse=True)
    tmp = 0
    for j in range(len(vt[i])):
        if (i + 1)*(j + 1) > n or vt[i][j] <= 0:
            break
        tmp += vt[i][j]
    ans = max(ans, tmp)

print (ans)

n, m = map(int, input().split())
vec = [[] for j in range(m)]
vt = [[] for j in range(n)]

for i in range(n):
    s, r = map(int, input().split())
    vec[s - 1].append(r)

for i in range(m):
    vec[i].sort(reverse=True)
    psum = 0
    for j in range(len(vec[i])):
        psum += vec[i][j]
        vt[j].append(psum)

ans = 0
for i in range(n):
    tmp = 0
    for j in range(len(vt[i])):
        if vt[i][j] > 0:
            tmp += vt[i][j]
    ans = max(ans, tmp)

print (ans)

(numcand, numsub) = (int(i) for i in input().split())
subs = [[] for _ in range(numsub)]
for _ in range(numcand):
    (sub, prof) = (int(i) for i in input().split())
    subs[sub-1].append(prof)
for sub in subs:
    sub.sort(reverse=True)
subs = [sub for sub in subs if sub and sub[0] > 0]
best = 0
while subs:
    best = max(best, sum(sub[0] for sub in subs))
    for i in reversed(list(range(len(subs)))):
        if (len(subs[i]) == 1) or (subs[i][0] + subs[i][1] <= 0):
            subs.pop(i)
        else:
            subs[i][0:2] = [subs[i][0] + subs[i][1]]
print(best)
    


n, m = map(int, input().split())
a = [[] for i in range(m)]
for _ in range(n):
    t, s = map(int, input().split())
    a[t - 1].append(s)
pre = [0] * n;
for i in range(m):
    a[i].sort(reverse = True)
    sum = 0; k = len(a[i])
    for j in range(k):
        sum = sum + a[i][j]
        if sum < 0: break
        pre[j] = pre[j] + sum
print(max(max(pre), 0))

import heapq, itertools, sys
NEGINF = -sys.maxsize

n, m = map(int, sys.stdin.readline().split())
skills_of_subject = {}
for i in range(1, m + 1):
    skills_of_subject[i] = []
for i in range(n):
    s, r = map(int, sys.stdin.readline().split())
    skills_of_subject[s].append(r)

cumul_subject_score_for_n_participants = {s : list(itertools.accumulate(sorted(skills_of_subject[s], key=lambda x: -x))) for s in skills_of_subject.keys()}


subject_with_atleast_nparts = {0 : skills_of_subject.keys()}
for i in range(1, n + 1):
    subject_with_atleast_nparts[i] = list(filter(lambda sid : len(skills_of_subject[sid]) >= i, subject_with_atleast_nparts[i - 1]))
#subject_with_atleast_nparts = {i : list(filter(lambda sid : len(skills_of_subject[sid]) >= i, skills_of_subject.keys())) for i in range(1, n + 1)}

curr_max = 0
for nParticipants in range(1, n+1):
    subject_army_by_competence = sorted([cumul_subject_score_for_n_participants[s][nParticipants - 1] for s in subject_with_atleast_nparts[nParticipants]], key=lambda x: -x)
    total_competence = 0
    for i in range(len(subject_army_by_competence)):
        total_competence += subject_army_by_competence[i]
        curr_max = max(curr_max, total_competence)

print (curr_max)