Problem:
 Score : 400 points    Problem Statement There are N one-off jobs available. If you take the i -th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.  You can take and complete at most one of these jobs in a day.  However, you cannot retake a job that you have already done.  Find the maximum total reward that you can earn no later than M days from today.  You can already start working today.      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq A_i \leq 10^5  1 \leq B_i \leq 10^4         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  A_2  B_2  \vdots  A_N  B_N       Output Print the maximum total reward that you can earn no later than M days from today.        Sample Input 1 3 4
4 3
4 1
2 2      Sample Output 1 5  You can earn the total reward of 5 by taking the jobs as follows:   Take and complete the first job today. You will earn the reward of 3 after four days from today.  Take and complete the third job tomorrow. You will earn the reward of 2 after two days from tomorrow, that is, after three days from today.        Sample Input 2 5 3
1 2
1 3
1 4
2 1
2 3      Sample Output 2 10       Sample Input 3 1 1
2 1      Sample Output 3 0

Solution (Python):
import heapq

n, m = [int(v) for v in input().split()]
ab_ = [[int(v) for v in input().split()] for _ in range(n)]

ab = sorted(ab_, key=lambda x: (x[0], x[1])) 

ans = 0

h = []
idx = 0
for i in range(m + 1):
  while idx < len(ab):
    if ab[idx][0] == i:
      heapq.heappush(h, -ab[idx][1])
      idx += 1
    else:
      break
  if len(h) > 0:
    
    ans -= heapq.heappop(h)

print(ans)

Solution (Python):
from collections import defaultdict
import heapq

N,M = map(int,input().split())

l = defaultdict(list)
for i in range(N):
    A,B = map(int,input().split())
    l[A].append(-B)

h = []
ans = 0
for i in range(M):
    for B in l[i+1]:
        heapq.heappush(h,B)
    if len(h)!=0:
        ans += - heapq.heappop(h)
print(ans)

Solution (Python):
import heapq
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort()
h = []
i = 0
ans = 0
for m in range(M-1,-1,-1):
    while i<N and AB[i][0]+m <= M:
        heapq.heappush(h,-AB[i][1])
        i += 1
    if len(h) != 0:
        ans -= heapq.heappop(h)

print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
a_b = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a < m+1:
        a_b[a-1].append(-b)
h = []
heapq.heapify(h)
ans = 0
for i in range(m):
    for j in a_b[i]:
        heapq.heappush(h, j)
    if len(h) == 0:
        continue
    ans += heapq.heappop(h)*(-1)
print(ans)

Solution (Python):
import heapq
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.sort()
can = []
p = 0
ans = 0
for i in range(M+1):
    while p<N and (AB[p][0] <= i) :
        heapq.heappush(can,-AB[p][1])
        p += 1
        
    if can != []:
        ans += heapq.heappop(can)
print(-ans)

Solution (Python):
import bisect
import heapq

N, M = map(int, input().split())
task = []
for i in range(N):
    a, b = map(int, input().split())
    task.append((a, b))

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        heapq.heappush(wa,-task[j][1])
        j += 1
    if wa:
        ans -= heapq.heappop(wa)

print(ans)

Solution (Python):
import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)

Solution (Python):

import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    
    L = [] 
    Q = defaultdict(list)
    for a, b in zip(A, B):
        heapq.heappush(Q[a], -b)
    
    res = 0
    for d in range(1, M+1):
        for b in Q[d]:
            heapq.heappush(L, b)
        if len(L) == 0:
            continue
        b = heapq.heappop(L)
        res -= b

    print(res)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        d[a].append(-b)

    ans = 0
    heap = []
    for i in range(1, M+1):
        for b in d[i]:
            heappush(heap, b)
        if heap:
            ans -= heappop(heap)

    return ans


if __name__ == '__main__':
    print(main())

Solution (Python):
from heapq import *

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        heappush(c[m - a], -b)
r=0
for i in range(m - 1, -1, -1):
    if c[i]:
        r -= heappop(c[i])
        if i:
            f = len(c[i]) > len(c[i - 1])
            h, g = (c[i], c[i - 1]) if f else (c[i - 1], c[i])
            for x in g:
                heappush(h, x)
            if f:
                c[i - 1] = c[i]       
print(r)

Solution (Python):
from heapq import *

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        heappush(c[m - a], -b)
r=0
for i in range(m - 1, -1, -1):
    if c[i]:
        r -= heappop(c[i])
        if i:
            f = len(c[i]) > len(c[i - 1])
            h, g = (c[i], c[i - 1]) if f else (c[i - 1], c[i])
            for x in g:
                heappush(h, x)
            if f:
                c[i - 1] = c[i]       
print(r)

Solution (Python):

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import heapq
AB.sort()
heap = []
heapq.heapify(heap)
ans = 0
i = 0
day = 1
while day <= M:
    while i < N and AB[i][0] <= day:
        heapq.heappush(heap,-AB[i][1])
        i += 1
    day += 1
    if not(heap):continue
    ans -= heapq.heappop(heap)

print(ans)

Solution (Python):
import heapq
from collections import deque

N, M = map(int,input().split())

work = [list(map(int,input().split())) for _ in range(N)]

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        heapq.heappush(paytree, wq.popleft()[1] * (-1))
    if len(paytree) > 0:
        ans -= heapq.heappop(paytree)

print(ans)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))

Solution (Python):
from collections import defaultdict
from heapq import heapify, heappop, heappush
from sys import stdin

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * N]

    ab = defaultdict(list)
    for a, b in AB:
        ab[a].append(b)

    ans = 0
    reward = []
    for i in range(1, M + 1):
        if ab[i]:
            for n in ab[i]:
                heappush(reward, n * -1)
        if reward:
            ans += heappop(reward) * -1
    print(ans)

input = lambda: stdin.readline()
main()

Solution (Python):
import heapq

n, m = map(int, input().split())


jobs = [list(map(int, input().split())) for i in range(n)]
jobs_days = [[] for i in range(m)]
for job in jobs:
    if job[0] - 1 < m:
        jobs_days[job[0] - 1].append(-job[1])

reward = 0
h = []
heapq.heapify(h)

for i in range(m):
    for job in jobs_days[i]:
        heapq.heappush(h, job)
    if len(h) > 0:
        reward += heapq.heappop(h)

print(-reward)

Solution (Python):

import sys
from operator import attrgetter
import heapq

def main():
    N,M = [int(i) for i in sys.stdin.readline().strip().split()]
    works = [[] for i in range(10**5+1)]
    ans = 0
    for i in range(N):
        A,B = [int(i) for i in sys.stdin.readline().strip().split()]
        heapq.heappush(works[A], -B)
    
    avaiable_works = []
    for i in range(1, M+1):
        for item in works[i]:
            heapq.heappush(avaiable_works, item)
        if len(avaiable_works) > 0:
            revenue = abs(heapq.heappop(avaiable_works))
        else:
            continue
        ans += revenue
    
    print("%d" % ans)

def solve(N, M, works):
    ans = 0

    return 0

if __name__ == "__main__":
    main()

Solution (Python):



import heapq

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    ll = []
    for _ in range(n):
        a, b = rli()
        ll.append((a, b))
    ll.sort()
    pq = []
    l = 0
    ans = 0
    for i in range(1, m+1):
        while l < len(ll) and ll[l][0] <= i:
            heapq.heappush(pq, -ll[l][1])
            l += 1
        if len(pq) > 0:
            ans -= heapq.heappop(pq)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle




import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








N, M = [int(x) for x in input().split()]
AB = []
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    AB.append((A, B))

AB = sorted(AB, key=lambda x: x[0])

idx = 0
available = []
ans = 0
for d in range(1, M + 1):
    while idx < N and AB[idx][0] <= d:
        heapq.heappush(available, -AB[idx][1])
        idx += 1

    if len(available) != 0:
        ans += (-heapq.heappop(available))

print(ans)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0][0]
    su = [x[0]]
    for i in range(len(x)-1):
        if aa != x[i+1][0]:
            a.append(su)
            aa = x[i+1][0]
            su = [x[i+1]]
        else:
            su.append(x[i+1])
    a.append(su)
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))


n,m = l()

a = []

for i in range(n):
    z,x = l()
    a.append([z,x])

a.sort(key = lambda x:(x[0],-x[1]))
kkk = s(a)
co = 0
p = 0
al = []
for i in range(m):
    k = i + 1
    if p <= len(kkk)-1:
        if k >= kkk[p][0][0]:
            for ppp in kkk[p]:
                hq.heappush(al,-ppp[1])
            p += 1
    if len(al) != 0:
        an = hq.heappop(al)
        co -= an 
print(co)

Solution (Python):
import bisect
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = list(range(0,M+1))
for x in C:
    A,B = x[0],x[1]
    ind = bisect.bisect_right(hist,M-A)
    if ind>0:
        hist.pop(ind-1)
        rev += B
print(rev)

Solution (Python):
import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)

Solution (Python):


import heapq

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N, M = readInts()
  tasks = [tuple(readInts()) for _ in range(N)]
  tasks.sort()

  h = []
  cur = 0
  ans = 0
  for m in range(1, M+1):
    while cur < len(tasks) and tasks[cur][0] <= m:
      heapq.heappush(h, -1 * tasks[cur][1])
      cur += 1
    if len(h) > 0:
      ans += -1 * heapq.heappop(h)
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
N, M = list(map(int, input().split()))
ABs = [0] * N
day_dic = {}

for i in range(N):
    ABs[i] = list(map(int, input().split()))

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            day_dic[day] = day
            count += 1
        else:
            esti = day_dic.get(day)
            if esti is None:
                esti = day
            for i in range(esti, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    day_dic[day] = i
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)

Solution (Python):
from heapq import *

N, M = [int(i) for i in input().split()]
L = []
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    L.append((a, -b))
L.sort()

Q = []
cur = 0
ans = 0
for i in range(1, M + 1):
    while cur < N:
        a, b = L[cur]
        if a > i:
            break
        heappush(Q, b)
        cur += 1
    if Q:
        ans -= heappop(Q)
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)  
for _ in range(N):
    A, B = map(int, input().split())
    deadline = M - A
    d[deadline].append(B)

ans = list()
for day in range(M + 1):
    rewards = d.get(day)
    if rewards is None or len(rewards) == 0:
        continue
    
    for reward in rewards:
        if len(ans) <= day:
            heappush(ans, reward)
        else:
            min_reward = heappop(ans)
            if reward > min_reward:
                heappush(ans, reward)
            else:
                heappush(ans, min_reward)

print(sum(ans))

Solution (Python):
import heapq
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = - int(b) 
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
heapq.heapify(vs)

res = 0
for item in arr:
  for v in item:
	  heapq.heappush(vs, v)
  
  if len(vs) == 0:
    continue
    
  maxi = heapq.heappop(vs)
  res += (-1* maxi)
  
print(res)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect


visit = []

def aaa(ind_lim, dame_num):
    global visit
    if ind_lim >= dame_num:
        return -1
    elif visit[ind_lim] == -1:
        return -1
    elif visit[ind_lim] == 0:
        return ind_lim
    else:
        visit[ind_lim] = aaa(visit[ind_lim], dame_num)
        return visit[ind_lim]

def main():
    num, max_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x:(-x[1]))
    

    global visit
    visit = [0 for i in range(max_num + 1)]

    ans = 0

    for i in range(num):
        day, value = data[i]
        ind_lim = day
        
        ind_insert = aaa(ind_lim, max_num + 1)
        if ind_insert != -1:
            visit[ind_insert] = ind_insert + 1
            ans += value

    
    print(ans)







if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import sys
from collections import deque
import heapq
sys.setrecursionlimit(100000000)

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  query = sorted(query,reverse = False)
  query2 = []
  for i in range(n):
    query2 += [query[i][0]]

  ans = 0
  judge = []
  for i in range(m):
    left = bisect.bisect_left(query2,i+1)
    right = bisect.bisect_right(query2,i+1)
    for j in range(left,right):
     b,a = (query[j])
     heapq.heappush(judge, [-a,b])
    
    if len(judge) != 0:
     b,a = heapq.heappop(judge)
     ans += -b
  print(ans)
solve()

Solution (Python):
from operator import itemgetter
N,M = map(int,input().split())

AB = []
for i in range(N):
    Ai,Bi = map(int,input().split())
    AB.append([Ai,Bi])

AB.sort(key=itemgetter(1),reverse=True)
AB.sort(key=itemgetter(0))
from heapq import heappush, heappop
hq = []
i = 0
now = 1
ans = 0
while True:
    if i == N:
        if now <= M:
            if len(hq) == 0:
                break
            ans -= heappop(hq)
            now += 1
            continue
        else:
            break
    if AB[i][0] == now:
        heappush(hq,-AB[i][1])
        i += 1
        continue
    else:
        if now > M:
            break
        if len(hq) == 0:
            now += 1
            continue
        ans -= heappop(hq)
        now += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())

B = [tuple(map(int, input().split())) for _ in range(N)]
B.sort(reverse=True)

import heapq

hq = []
ans = 0
for i in range(1, M+1):
    while B and B[-1][0] == i:
        heapq.heappush(hq, B.pop()[1]*(-1))
    if hq:
        ans -= heapq.heappop(hq)

print(ans)

Solution (Python):
from heapq import heappush, heappop

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

j = 0
h = []
for i in range(1, m + 1):
    while j < len(xys) and xys[j][0] <= i:
        heappush(h, -xys[j][1])
        j += 1
    if h:
        x = -heappop(h)
        
        ans += x

print(ans)

Solution (Python):








import heapq
N, M = [int(i) for i in input().split(" ")]
ABs = []
for _ in range(N):
   A, B = [int(i) for i in input().split(" ")]
   ABs.append([A, B])
ABs.sort(key=lambda ab: (ab[0], -ab[1]))
ans = 0
day = 1
k = 0
pq = []
while day <= M:
  while True:
    if k < len(ABs) and ABs[k][0] <= day:
      heapq.heappush(pq, -ABs[k][1])
      k += 1
    else:
      break
  if pq:
    v = heapq.heappop(pq)
    ans += -v
  day += 1
print(ans)

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
AB_dict = defaultdict(list)
AB = sorted([tuple(map(int, input().split())) for i in range(N)], reverse=True, key=lambda x: x[0])
AB = sorted(AB, reverse=True, key=lambda x: x[1])
EF = [M-i for i in range(10**5+1)]
ans = [0 for i in range(M)]
for i in range(N):
    Ai, Bi = AB[i]
    ans_i = EF[Ai]
    while ans_i >= 0 and ans[ans_i] != 0:
        ans_i -= 1
    if ans_i >= 0:
        ans[ans_i] = max(ans[ans_i], Bi)
        EF[Ai] = ans_i - 1
    else:
        EF[Ai] = ans_i
print(sum(ans))

Solution (Python):


import heapq


def g(Q, n):
    x = 0

    for i in range(n):
        if len(Q) == 0:
            break

        x += -heapq.heappop(Q)

    return x


def f(AB, M):
    lastA = None
    Q = []
    sumOfB = 0

    for a,b in AB:
        if a > M:
            break

        if a != lastA:
            if lastA != None:
                sumOfB += g(Q, a-lastA)

            lastA = a

        heapq.heappush(Q, -b)
            
    if lastA != None:
        sumOfB += g(Q, M-lastA+1)

    return sumOfB


def main():
    N,M = map(int, input().split())
    AB = sorted(list(map(int, input().split())) for i in range(N))

    print(f(AB, M))


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
AB = LIR(N)

parts = [[] for i in range(M)]
for A, B in AB:
    if (A>M):
        continue
    parts[A-1].append(B)

ans = 0

h = []


for i in range(M):
    for part in parts[i]:
        heappush(h, -part)
    if not (h):
        continue
    ans += -heappop(h)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N, M = map( int, input().split())
    L = [(0,0) for _ in range(N)]
    for i in range(N):
        a, b = map( int, input().split())
        L[i] = (b,a)
    L.sort(reverse = True)
    V = [0]*M
    W = [ i for i in range(M)]
    def find(A,x):
        p = A[x]
        if p == x:
            return x
        a = find(A,p)
        A[x] = a
        return a
 
    def union(A, x, y):
        
        if find(A,x) > find(A,y):
            bx, by = find(A,y), find(A,x)
        else:
            bx, by = find(A,x), find(A,y)
        A[y] = bx
        A[by] = bx

    for i in range(N):
        b, a = L[i]
        t = M-a
        if t < 0:
            continue
        if V[t] == 0:
            V[t] = b
            if t > 0:
                if V[t-1] > 0:
                    union(W, t, t-1)
            if t < M-1:
                if V[t+1] > 0:
                    union(W, t, t+1)
            continue
        s = find(W,t)
        if s == 0:
            if V[0] == 0:
                V[0] = b
                if M > 1:
                    if V[1] > 0:
                        union(W, 0, 1)
        else:
            V[s-1] = b
            if s-1 > 0:
                if V[s-2] > 0:
                    union(W, s-1, s-2)
            union(W,s-1,s)
    print( sum(V))
            
            
            
            
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.mini = [i for i in range(n+1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        mini = min(self.mini[x],self.mini[y])
        self.mini[x]=mini
        self.mini[y]=mini
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def main():
    N ,M = ints_raw()
    days = [0]*M
    uft = UnionFind(M)
    ABs = [ints_raw() for _ in range(N)]
    ABs.sort(key=lambda x:x[1],reverse=True)
    ans = 0
    for AB in ABs:
        A,B = AB
        if A > M:
            continue
        else:
            C = M-A
            par = uft.mini[uft.find(C)]

            if days[par] == 0:
                days[par]=1
                ans += B
                
                if par > 0:
                    uft.union(par-1,par)

            
            
            
            
            
    return ans

    
print(main())

Solution (Python):
class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(M)
used_list = [False] * M

reward = 0
for b, a in ab_list:
	index = M - a
	prev_index = None
	while index >= 0:

		if not used_list[index]:
			used_list[index] = True
			reward += b
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1

print(reward)

Solution (Python):
import heapq

n,m = map(int,input().split())

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

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

ans = 0
a = []
j = 0
for i in range(m-1,-1,-1):
  while j<len(ls) and ls[j][0] == m-i:
    heapq.heappush(a,ls[j][1]*(-1))
    j += 1
  
  if a:
    ans += -1*heapq.heappop(a)

print(ans)

Solution (Python):
from collections import defaultdict
from heapq import heappush,heappop
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
arr = [[] for _ in range(M+1)]
for a, b in AB:
    if M-a>=0:
        arr[M-a].append(b)

ans=0
h=[]
for i in reversed(range(M+1)):
    for a in arr[i]:
        heappush(h,-a)
    if len(h)>0:
        ans += (-1)*h[0]
        heappop(h)
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
L = []


for i in range(N):
    A, B = map(int, input().split())
    L.append([A, B])

L = sorted(L, reverse= True)

dp = [0 for i in range(M+1)]
use = [False for i in range(N)]

dp[0] = 0
h = []

for i in range(M):
    while len(L) != 0:
        m = L[-1]
        if m[0] <= i+1:
            heapq.heappush(h, -L.pop(-1)[1])
        else:
            break
    if len(h) != 0: 
        dp[i+1] = dp[i] + -heapq.heappop(h)
    else:
        dp[i+1] = dp[i]

print(dp[M])

Solution (Python):
N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn>M-ab[0]-i:
                break
            D[M-ab[0]-i]+=1
            if D[M-ab[0]-i]==1:
                pay+=ab[1]
                flag=False
                break
            else:
                if i==1:
                    i+=1
                else:
                    i+=D[M-ab[0]-i]-1
            
        if flag:
            mn=M-ab[0]
            
print(pay)

Solution (Python):


import sys

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(bi)

for i in range(m):
    if baito[i]: baito[i].sort()

tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur:
            cur= ref
        else:
            if ref[-1]<=cur[0]:
                cur= ref + cur
            elif cur[-1]<=ref[0]:
                cur= cur + ref
            else:
                cur+= ref
                cur.sort()
    
    if not cur: continue
    tot+= cur.pop()

print( tot )