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 = map(int, input().split())
ABn = [list(map(int, input().split())) for _ in range(N)]
ABn = sorted(ABn)

heap_q = []
reword = 0
j = 0
for i in range(M):
  while j<N and ABn[j][0] <= i+1:
    heapq.heappush(heap_q,-ABn[j][1])
    j+=1
  if len(heap_q) > 0:
    reword += heapq.heappop(heap_q) * (-1)
print(reword)

Solution (Python):
from collections import defaultdict
import heapq
N, M = map(int, input().split())
dct = defaultdict(list)

for i in range(N):
  A, B = map(int, input().split())
  if A > M:
    continue
  dct[M-A].append(-B)

h = []
ans = 0
for i in range(M-1,-1,-1):
  if dct[i]:
    for item in dct[i]:
      heapq.heappush(h,item)
  if h:
    ans += heapq.heappop(h)

print(-ans)

Solution (Python):
N,M = map(int,input().split())
import heapq
from collections import defaultdict
l = []
heapq.heapify(l)
d = defaultdict(list)

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

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

Solution (Python):
from collections import defaultdict
import heapq
N, M = map(int, input().split())
dct = defaultdict(list)

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

h = []
ans = 0
for i in range(1,M+1):
  if dct[i]:
    for item in dct[i]:
      heapq.heappush(h,item)
  if h:
    ans += heapq.heappop(h)

print(-ans)

Solution (Python):
from heapq import heappush, heappop



q = []
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, reverse=True)

    q = []
    answer = 0
    for i in range(m-1, -1, -1):
        while ab and i + ab[-1][0] <= m:
            (a, b) = ab.pop()
            heappush(q, -b)

        if q:
            answer -= heappop(q)

    print(answer)

Solution (Python):
import sys
import heapq

N, M = list(map(int, input().split()))
jobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue
    jobs.append((A, B))

jobs.sort(reverse=True)

q = []
ans = 0
for i in range(1, M + 1):
    while jobs and jobs[-1][0] <= i:
        A, B = jobs.pop()
        heapq.heappush(q, -B)

    if q:
        ans += -heapq.heappop(q)
print(ans)

Solution (Python):
import heapq


class Reverse:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if len(self.hq) == 0:
            return None
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)

    def top(self):
        if self.desc:
            return self.hq[0].val
        else:
            return self.hq[0]

    def __len__(self):
        return len(self.hq)


n, m = map(int, input().split(' '))
ab = []
for _ in range(n):
    a, b = map(int, input().split(' '))
    if a > m:
        continue
    ab.append((a, b))
ab.sort(reverse=True)

ans = 0
h = Heapq([], desc=True)
for i in range(1, m+1):
    while ab and ab[-1][0] <= i:
        a, b = ab.pop()
        h.push(b)
    if h:
        ans += h.pop()
print(ans)

Solution (Python):
import heapq
N, M = list(map(int, input().split()))
days = [[] for _ in range(M + 1)]
for i in range(N):
    a, b = list(map(int, input().split()))
    if a > M: continue
    days[a].append(b)

reward = []
heapq.heapify(reward)

total = 0
for i in range(M)[::-1]:
    tasks = days[M - i]
    for task in tasks:
        heapq.heappush(reward, -1 * task)

    if len(reward) > 0:
        total += heapq.heappop(reward) * (-1)

print(total)

Solution (Python):
import heapq
def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)
 
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)
 
print(ans)

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): 
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(N)]
    heap = []
    AB.sort(key = lambda x:x[0],reverse = True)
    ans = 0
    for i in range(1,M+1):
        while AB and AB[-1][0] <= i:
            heappush(heap,-AB.pop()[1])
        if heap:
            ans -= heappop(heap)

    print(ans)
    
if __name__ == "__main__":
    main() 




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Solution (Python):
import sys
import heapq

N, M = list(map(int, input().split()))
jobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue
    jobs.append((A, B))

jobs.sort(reverse=True)

q = []
ans = 0
for i in range(1, M + 1):
    while jobs and jobs[-1][0] <= i:
        A, B = jobs.pop()
        heapq.heappush(q, -B)

    if q:
        ans += -heapq.heappop(q)
print(ans)

Solution (Python):
from collections import defaultdict
import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)

total = 0
candidates = []
heapq.heapify(candidates)

for i in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)
    
    if candidates:
        total -= heapq.heappop(candidates)

print(total)

Solution (Python):
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

for i in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

    if candidates:
        total -= heapq.heappop(candidates)

print(total)

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

L = [[int(i) for i in input().split()] for i in range(N)]
L = sorted(L, key=lambda x: -x[0])

h = []
ans = 0
j = N-1
for i in range(M-1, -1, -1):
    while j >= 0 and L[j][0] <= M - i:
        heapq.heappush(h, -L[j][1])
        j -= 1
    if len(h) == 0:
        continue
    ans += -heapq.heappop(h)
print(ans)

Solution (Python):
import heapq
N,M = map(int,input().split())
days = [[] for _ in range(M + 1)]
for n in range(N):
	a,b = map(int,input().split())
	if a > M:
		continue
	days[a].append(-b)

total_reward = 0
q = []
for day in range(M + 1):
	this_day = days[day]
	for reward in this_day:
		heapq.heappush(q,reward)
	if len(q):
		total_reward -= heapq.heappop(q)
print(total_reward)

Solution (Python):
import heapq

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

l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)

l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)

print(ans)

Solution (Python):
N, M = map(int, input().split())
lst = []
for _ in range(N):
    A, B = map(int, input().split())
    lst.append([A, -B])
lst.sort()

ans = 0
index = 0
import heapq
hq = []
for i in range(M):
    while index < N and lst[index][0] <= i + 1:
        heapq.heappush(hq, lst[index][1])
        index += 1
    if len(hq) > 0:
        ans -= heapq.heappop(hq)
    
print (ans)

Solution (Python):
from collections import defaultdict
import heapq

a_dict = defaultdict(lambda: [])
n, m = map(int, input().split())
for _ in range(n):
    a, b = map(int, input().split())
    a_dict[a].append(-b)
ans = 0
heap_list = []
for i in range(1, m + 1):
    for aa in a_dict[i]:
        heapq.heappush(heap_list, aa)
    if len(heap_list) > 0:
        ans -= heapq.heappop(heap_list)
print(ans)

Solution (Python):
from collections import defaultdict
import heapq

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

arbList = defaultdict(lambda: [])

for _ in range(N):
    a, b = map(int, input().split())
    arbList[a].append(-b)

arb = []
ans = 0

for day in range(M + 1):
    for b in arbList[day]:
        heapq.heappush(arb, b)
    if arb:
        ans += heapq.heappop(arb)

print(-ans)

Solution (Python):
from heapq import heappop,heappush

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

AB = [[int(i) for i in input().split()] for j in range(n)]



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



tmp = 0
hq = []
ans = 0

for i in range(1,m+1):
    while tmp <= n-1 and AB[tmp][0] <= i:
        heappush(hq,-AB[tmp][1])
        tmp += 1
    if len(hq) > 0:
        ans += -heappop(hq)
        
print(ans)

Solution (Python):
import heapq

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

AB = [[int(i) for i in input().split()] for j in range(n)]



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



tmp = 0
hq = []
ans = 0

for i in range(1,m+1):
    while tmp <= n-1 and AB[tmp][0] <= i:
        heapq.heappush(hq,-AB[tmp][1])
        tmp += 1
    if len(hq) > 0:
        ans += -heapq.heappop(hq)
        
print(ans)

Solution (Python):
import heapq

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

AB = [[int(i) for i in input().split()] for j in range(n)]



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



tmp = 0
hq = []
ans = 0

for i in range(1,m+1):
    while tmp <= n-1 and AB[tmp][0] <= i:
        heapq.heappush(hq,-AB[tmp][1])
        tmp += 1
    if len(hq) > 0:
        ans += -heapq.heappop(hq)
        
print(ans)

Solution (Python):
import heapq
from collections import defaultdict
n,m = map(int,input().split())
day = []
d = defaultdict(list)
for i in range(n):
    a,b = map(int,input().split())
    d[a].append(b)
task = []
cost = 0
heapq.heapify(task)
for i in range(1,m+1):
    for j in d[i]:
        heapq.heappush(task,-j)
        
    if task != []:
        c = heapq.heappop(task)
        cost += (-1)*c  
print(cost)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    while j < n and ab[j][0] <= i:
        heappush(hq, -ab[j][1])
        j += 1
    if hq:
        result -= heappop(hq)
print(result)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    while j < n and ab[j][0] <= i:
        heappush(hq, -ab[j][1])
        j += 1
    if hq:
        result -= heappop(hq)
print(result)

Solution (Python):
import heapq

N, M = map(int, input().split())
B = [[] * M for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    B[M - a].append(b)
ans = 0
h = []
for i in range(M - 1, -1, -1):
    for b in B[i]:
        heapq.heappush(h, b * -1)
    if len(h) > 0:
        ans += heapq.heappop(h) * -1
print(ans)

Solution (Python):
import heapq

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

for i in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    jobs[M-a].append(-b)

q = []
heapq.heapify(q)

ans = 0
for i in range(M-1, -1, -1):
    for j in jobs[i]:
        heapq.heappush(q, j)
    if len(q) != 0:
        ans += q[0]
        heapq.heappop(q)

print(-ans)

Solution (Python):
import heapq
import bisect

n,m = map(int,input().split())
ab = [[0,0,0] for _ in range(n)]

for i in range(n):
    a,b = map(int,input().split())
    ab[i] = [-b,a,b]

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



day = 1

ans = 0
pqueue = []

for i in range(n):
    if ab[i][1] > m:
        break

    if ab[i][1] <= day:
        heapq.heappush(pqueue, ab[i])
    else:
        for j in range(day, ab[i][1]):
            if len(pqueue) > 0:
                ans += heapq.heappop(pqueue)[2]
                
                day = ab[i][1]
        heapq.heappush(pqueue, ab[i])
    

for k in range(day, m+1):
    if len(pqueue) > 0:
        ans += heapq.heappop(pqueue)[2]
        
        

print(ans)

Solution (Python):
import heapq

n, m = map(int,input().split())
joblist = {}
for i in range(n):
    a,b = map(int,input().split())
    if a in joblist:
        joblist[a].append(-1*b)
    else:
        joblist[a] = [-1*b]

kouho = []
 
ans =0
 
for i in range(1,m+1):
    if i in joblist:
        for j in joblist[i]:
            heapq.heappush(kouho,j)
    if kouho:
        ans += heapq.heappop(kouho)
 
print(-1*ans)

Solution (Python):
import heapq

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

jobs = {}
for _ in range(N):
  a,b = map(int, input().split())
  if a > M:
    continue
  if M - a in jobs:
    jobs[M-a].append(b)
  else:
    jobs[M-a] = [b]

q = []
heapq.heapify(q)

ans = 0
for i in reversed(range(0, M)):
  if i in jobs.keys():
    for job in jobs[i]:
      heapq.heappush(q, (-job, job))
  
  if len(q) > 0:
    ans += heapq.heappop(q)[1]

print(ans)

Solution (Python):
import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)

Solution (Python):
import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
a = [3, 0, 2, 6]
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)

Solution (Python):
from heapq import heappush, heappop
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)

Solution (Python):
def main(sample_file = ''):

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        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 combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter 
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)
    
    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    
    if sample_file:
        sys.stdin = open(sample_file)
        
    
    

    N, M = R()
    AB = [R() for _ in range(N)]
    AB.sort()
    ans, index = 0, 0
    hp = []
    for left_days in range(1, M+1):
        while index < N and AB[index][0] == left_days:
            a, b = AB[index]
            heappush(hp, -b)
            index += 1
        if hp:
            ans -= heappop(hp)
    print(ans)
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    
    >>> a = 5
    >>> bin_str_a = format(a, '
    >>> print(bin_str_a)
    0b0101 
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

from heapq import *

n,m = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for _ in range(n)]

ab.sort(reverse = True)

q = []
ans = 0
for i in range(m-1,-1,-1):
    while ab and ab[-1][0] + i <= m:
        (a,b) = ab.pop()
        heappush(q,-b)
    
    if q: ans -= heappop(q)

print(ans)

Solution (Python):
n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()

here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    
    ans -= heapq.heappop(pool)
    
  except:
    pass
print(ans)

Solution (Python):
import sys

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

import heapq

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

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            heapq.heappush(ABs[0], b)
    if len(ABs[0]) > 0:
        As -= heapq.heappop(ABs[0])
print(As)

Solution (Python):
import sys

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

import heapq

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

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            heapq.heappush(ABs[0], b)
    if len(ABs[0]) > 0:
        As += heapq.heappop(ABs[0])
print(-As)

Solution (Python):
import heapq

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

for _ in range(N):
    A, B = map(int, input().split())
    if A <= M:
        P[A-1].append(-B)

ans = 0
hq = []
for i in range(M):
    for d in P[i]:
        heapq.heappush(hq, d)
    if len(hq) != 0:
        ans += heapq.heappop(hq)

print(abs(ans))

Solution (Python):
import sys,heapq
input=sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AB=[list(map(int,input().strip().split())) for _ in range(N)]
AB.sort()
n=0
sumB=0
q=[]
for m in range(1,M+1):
    while n<N and AB[n][0]<=m:
        heapq.heappush(q,-AB[n][1])
        n+=1
    if len(q)!=0:
        sumB+=heapq.heappop(q)

print(-sumB)

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N ]

AB += [[10*M,0]]

AB.sort(reverse=True)

from heapq import *

q = []
ans = 0

for i in range(1,M+1):
    a,b = AB[-1]
    while a<=i:
        a,b = AB.pop()
        heappush(q,-b)
        a,b = AB[-1]
    if len(q)>0:
        ans += -heappop(q)
print(ans)

Solution (Python):

from heapq import *

n, m = map(int, input().split())
hp = []
for _ in range(n):
    a, b = map(int, input().split())
    heappush(hp, [a, b])
ans = 0
mx = b
ch = []
a, b = heappop(hp)
flag = 1
for i in range(1, m + 1):
    while a <= i:
        if flag:
            heappush(ch, -b)
            flag = 0
        if not hp:break
        a, b = heappop(hp)
        flag = 1
    if ch:
        ans -= heappop(ch)
print(ans)

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

L = [[int(i) for i in input().split()] for i in range(N)]
L = sorted(L, key=lambda x: -x[0])

h = []
ans = 0
j = N-1
for i in range(M-1, -1, -1):
    while j >= 0 and L[j][0] <= M - i:
        heapq.heappush(h, -L[j][1])
        j -= 1
    if len(h) == 0:
        continue
    ans += -heapq.heappop(h)
print(ans)

Solution (Python):
import heapq

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

for n in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    AB[a].append(0-b)

earn = 0
q = []

for m in range(1, M + 1):

    for job in AB[m]:
        heapq.heappush(q, job)

    if q != []:
        earn += heapq.heappop(q)

print(0-earn)

Solution (Python):
N, M = map(int, input().split())
AB = [(a, b) for _ in range(N) for a, b in [map(int, input().split())] if M - a >= 0]

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

print(sum(x))

Solution (Python):
N, M = map(int, input().split())
AB = [(a, b) for _ in range(N) for a, b in [map(int, input().split())] if M - a >= 0]

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

print(sum(x))

Solution (Python):
N, M = map(int, input().split())
AB = [(a, b) for _ in range(N) for a, b in [map(int, input().split())] if M - a >= 0]

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