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 sys
from heapq import heappop, heappush

input = sys.stdin.readline


def main():
    MAX_A = 10 ** 5
    N, M = map(int, input().split())
    AB = [[] for _ in range(MAX_A + 1)]
    for i in range(N):
        A, B = map(int, input().split())
        AB[A].append(-B)

    p_queue = []
    ans = 0
    for m in range(1, M + 1):
        for b in AB[m]:
            heappush(p_queue, b)
        if p_queue:
            x = heappop(p_queue)
            x *= -1
            ans += x

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


class SegmentTree:
    """Segment Tree class.

    Args:
        N (int): Number of elements
        X (list[int]): List for initialization
        func (callable): Function for interval.
        init_v (int): Initial value that does not affect `func`.
            For example, specify INF when `func = min`.

    References:
        <https://en.wikipedia.org/wiki/Segment_tree>
    """
    def __init__(self, N, X, func, init_v):
        N_ = 1
        while N_ < N: N_ *= 2
        self.N = N_
        self.func = func
        self.init_v = init_v
        self.__build(X)

    def __build(self, X):
        
        self.node = [[self.init_v, -1] for _ in range(2 * self.N)]  

        
        for i, x in enumerate(X, self.N):
            self.node[i] = [x, i - self.N + 1]

        
        for i in range(self.N - 1, 0, -1):
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, i, x):
        """Update the i-th node value to x.

        Args:
            i (int): index (1-based index)
            x (int): udpate value
        """
        i += self.N - 1
        self.node[i][0] = x
        while i > 1:
            i >>= 1
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def query(self, l, r):
        """Query for right half-open interval [l, r).

        Args:
            l (int): index (1-based index)
            r (int): index (1-based index)
        """
        dst_l = [self.init_v, -1]
        dst_r = [self.init_v, -1]
        l += self.N - 1
        r += self.N - 1
        while l < r:
            if l & 1:
                dst_l = self.func(dst_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                dst_r = self.func(self.node[r], dst_r)
            l >>= 1
            r >>= 1
        return self.func(dst_l, dst_r)


def func(a, b):
    return a if a[0] > b[0] else b


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

    AB.sort(key=lambda x: x[0])
    B = [0] * N
    C = [0] * (1 + 10 ** 5)
    for i, (a, b) in enumerate(AB):
        B[i] = b
        C[a] += 1
    C = list(accumulate(C))

    st = SegmentTree(N, B, func, -1)
    ans = 0
    l = 1
    for r in C[1:M + 1]:
        if r == 0:
            continue
        x, i = st.query(l, r + 1)
        if x == -1:
            continue
        ans += x
        st.update(i, -1)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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

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

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

Solution (Python):
import heapq
N,M = map(int,input().split())
lis = [[] for i in range(10**5+10)]
for i in range(N):
    A,B = map(int,input().split())
    lis[A-1].append(-B)
ans = 0
d = []
heapq.heapify(d)
for i in range(M):
    for j in lis[i]:
        heapq.heappush(d,j)
    if len(d) > 0:
        ans += heapq.heappop(d)*-1
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
S = list()
A = [list() for _ in range(M+1)]
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    heapq.heappush(A[a], -b)

ans = 0
for i in range(1, M+1):
    for num in A[i]:
        heapq.heappush(S, num)
    if S == []:
        continue
    ans -= heapq.heappop(S)
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)


import bisect as bi
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        bi.insort(now,b)
    
    if now==[]:continue
    ans+= now[-1]
    del now[-1]


print(ans)

Solution (Python):
def main():
    import heapq
    n,m = map(int,input().split())
    A = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in A.keys():
            A[a] = [b]
        else:
            A[a].append(b)
    J = []
    ans = 0
    for i in range(1,m+1):
        if A.get(i)!=None:
            for k in A[i]:
                heapq.heappush(J,-1*k)
        if len(J)>0:
            ans += -1* heapq.heappop(J)
    print(ans)

if __name__ == "__main__":
    main()

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

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

hq = []
heapq.heapify(hq)
ans = 0
for i in range(1, m+1): 
    if len(d[i]) > 0:
        for j in d[i]:
            heapq.heappush(hq, j*(-1))
    if len(hq) > 0:
        ans += heapq.heappop(hq)*(-1)
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
arubaito = [list(map(int, input().split())) for _ in range(N)]
arubaito.sort()
arubaito2 = [[] for _ in range(M+1)]
for i in range(N):
    if arubaito[i][0] <= M:
        arubaito2[arubaito[i][0]].append(arubaito[i][1])
for i in range(M):
    arubaito2[i].sort(reverse=True)
target = []
ans = 0
heapq.heapify(target)
for i in range(1,M+1):
    for k in arubaito2[i]:
        heapq.heappush(target,k*(-1))
    if len(target) > 0:
        ans += heapq.heappop(target)*(-1)
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
arubaito = [list(map(int, input().split())) for _ in range(N)]
arubaito.sort()
arubaito2 = [[] for _ in range(M+1)]
for i in range(N):
    if arubaito[i][0] <= M:
        arubaito2[arubaito[i][0]].append(arubaito[i][1])
for i in range(M):
    arubaito2[i].sort(reverse=True)
target = []
ans = 0
heapq.heapify(target)
for i in range(1,M+1):
    for k in arubaito2[i]:
        heapq.heappush(target,k*(-1))
    if len(target) > 0:
        ans += heapq.heappop(target)*(-1)
print(ans)

Solution (Python):
import heapq

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

ab = []

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

ab.sort()

d = 1

w = []
heapq.heapify(w)

p = 0
d = 1
i = 0
while d <= m:
    while i < n and ab[i][0] == d:
        a, b = ab[i]
        heapq.heappush(w, -b)
        i += 1
    
        
    if len(w) > 0:
        p -= heapq.heappop(w)

    d += 1


print(p)

Solution (Python):
import heapq
n, m = map(int, input().split())
d = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        d[a-1].append(-b)

t = []
heapq.heapify(t)
ans = 0
for i in range(m):
    for dd in d[i]:
        heapq.heappush(t, dd)
    if t:
        ans += heapq.heappop(t)*(-1)
print(ans)

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

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

total = 0
heap = []
for i in range(M):
    for job in jobs[i]:
        heapq.heappush(heap, job)

    if len(heap) == 0:
        continue
    else:
        total += -heapq.heappop(heap)

print(total)

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

res = 0
temp = []
for i in range(1,M+1):
    for a in data[i]:
        heappush(temp,a)
    if temp:
        res -= heappop(temp)
print(res)

Solution (Python):
from heapq import heappush, heappop

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

day = [[] for _ in range(10 ** 5)]
for a, b in ab:
    day[a - 1].append(b)

work, ans = [], 0
for i in range(m):
    for j in day[i]:
        heappush(work, -j)
    if len(work) > 0:
        ans -= heappop(work)
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)]

day = [[] for _ in range(10 ** 5)]
for a, b in ab:
    day[a - 1].append(b)

work, ans = [], 0
for i in range(m):
    for j in day[i]:
        heappush(work, -j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

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

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

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

work, ans = [], 0
for i in range(1, m + 1):
    for j in day[i]:
        heappush(work, -j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

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

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

day = defaultdict(list)
for a, b in ab:
    heappush(day[a], -b)

work, ans = [], 0
for i in range(1, m + 1):
    for j in day[i]:
        heappush(work, j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Solution (Python):
import heapq
import sys
N, M = map(int, input().split())
B = [[] for _ in range(M + 1)]
for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    if a <= M:
        B[a].append(b)

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

Solution (Python):
from heapq import heappush, heappop

n, m = map(int, input().split())
arbeit = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    heappush(arbeit[a-1], -b)

ans = 0
next_vals = []
for i in range(m):
    if any(arbeit[i]):
        b = heappop(arbeit[i])
        heappush(next_vals, (b, i))
    if any(next_vals):
        b, i = heappop(next_vals)
        ans -= b
        if any(arbeit[i]):
            b = heappop(arbeit[i])
            heappush(next_vals, (b, i))
print(ans)

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

Work = []
for i in range(n):
    Work.append(list(map(int, input().split())))
Work.sort(key=lambda x: (x[0], x[1]), reverse=True)


total = 0
job_stock = []

heapq.heapify(job_stock)
for day in range(m, -1, -1):
    allowed_delay = m - day
    try:
        while Work[-1][0] <= allowed_delay:
            delay, money = Work.pop()
            heapq.heappush(job_stock, -money)
    except:
        pass
    if len(job_stock) >= 1:
        job_today = -heapq.heappop(job_stock)
        total += job_today
print(total)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    
    N, M = map(int, input().split())
    
    
    S = list(tuple(map(int, input().split())) for i in range(N)) 

    s=heapify(S)
    q=[]
    tot=0
    for i in range(1,M+1):
        while S and S[0][0]<=i:
            a,b=heappop(S)
            heappush(q,-b)
        if q:
            tot+=-heappop(q)
    print(tot)


if __name__ == "__main__":
    main()

Solution (Python):
from math import factorial as fact
import math
import sys
from itertools import product
import numpy as np
from collections import Counter
import datetime
from collections import deque
from bisect import bisect_left, bisect_right
import heapq




def input1():
	return int(input())


def input2():
	return map(int,input().split())


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


n,m=input2()
AB=[[] for _ in range(m)]


for i in range(n):
	a,b=input2()
	if a-1 < m: 
		AB[a-1].append(-b) 

ans=0
heap=[]
for i in range(m):
	for b in AB[i]:
		heapq.heappush(heap,b)
	
	if len(heap)>0:
		MAX=heapq.heappop(heap)
		ans+= -MAX
print(ans)

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


class MaxHeapObj(object):
  def __init__(self, val):
    self.val = val

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

  def __eq__(self, other):
    return self.val == other.val

  def __str__(self):
    return str(self.val)


class MinHeap(object):
  def __init__(self, L=None):
    if L is None:
      self.h = []
    else:
      heapq.heapify(L)
      self.h = L

  def heappush(self, x):
    heapq.heappush(self.h, x)

  def heappop(self):
    return heapq.heappop(self.h)

  def __getitem__(self, i):
    return self.h[i]

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


class MaxHeap(MinHeap):
  def __init__(self, L=None):
    super(MaxHeap, self).__init__(list(map(lambda x: MaxHeapObj(x), L)))

  def heappush(self, x):
    heapq.heappush(self.h, MaxHeapObj(x))

  def heappop(self):
    return heapq.heappop(self.h).val

  def __getitem__(self, i):
    return self.h[i].val


def main():
  N, M = list(map(int, input().split()))
  L = []
  for i in range(N):
    a, b = map(int, input().split())
    L.append((a, b))
  L = sorted(L)

  H = []
  PQ = MaxHeap(H)
  max_ = 0

  start = 0
  for m in range(M-1, -1, -1):
    res = M - m
    while start < N and L[start][0] == res:
      PQ.heappush(L[start][1])
      start += 1

    if len(PQ):
      now = PQ.heappop()
      max_ += now

  print(max_)


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

Solution (Python):

from heapq import heappop, heappush

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

X.sort(reverse=True)
ans = 0
pq = []
for n in range(M + 1):
    while X and X[-1][0] <= n:
        a, b = X.pop()
        heappush(pq, -b)

    if pq:
        ans -= heappop(pq)

print(ans)

Solution (Python):
N,K=list(map(int,input().split()))
l=[]
for i in range(N):
   l.append(list(map(int,input().split())))
l.sort()
import heapq
X=[]
S=0
ans=0
heapq.heapify(X)
for i in range(1,K+1):
   for j in range(S,N):
      if l[j][0]<=i:
         S+=1
         heapq.heappush(X,l[j][1]*-1)
      else:
         break
   try:
      tmp=heapq.heappop(X)
      ans+=tmp*-1
   except IndexError:
      continue
print(ans)

Solution (Python):
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



class node:
	def __init__(self,a_val, a_parent=None):
		self.val=a_val
		self.parent=a_parent
		self.right=None
		self.left=None

def main2():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) 
	for a, b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		
	print(ret)
	
	
def main():
	n, m = IN()
	st_day=[[] for _ in range(m+1)]
	for n in range(n):
		duration, pay = IN()
		if duration > m:
			continue
		st_day[m-duration].append(pay)
	
	pq=queue.PriorityQueue()
	ret = 0
	for di in range(m+1):
		day=m-di
		for pay in st_day[day]:
			pq.put(-pay)
		if not pq.empty():
			v = pq.get()
			ret -= v
	print(ret)
			
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import heapq
from collections import deque
n,m = map(int,input().split())
A = []
for _ in range(n):
    a,b = map(int,input().split())
    A.append((a,-b))
A.sort()
A = deque(A)
hq = []
ans = 0
for i in range(1,m+1):
    while A:
        if A[0][0] ==i:
            tmp = A.popleft()
            heapq.heappush(hq,tmp[1])
        else:
            break
    if len(hq) == 0:
        continue
    else:
        ans += heapq.heappop(hq)
print(-ans)

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

Solution (Python):
import heapq


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n)]

    AB.sort(key=lambda x: x[0])
    H = []
    ans = 0
    mi = 1
    for a, b in AB:
        while a > mi:
            if len(H) > 0:
                ans += -heapq.heappop(H)

            mi += 1
            if mi > m:
                break

        if a > m:
            break

        heapq.heappush(H, -b)

    while mi <= m and len(H) > 0:
        ans += -heapq.heappop(H)
        mi += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = list(map(int,input().split()))
X = [[]*3 for i in range(M)]
for i in range(N):
    A,B = list(map(int,input().split()))
    if A>M:
        continue
    else:
        X[M-A].append(B)

import heapq
out = 0
Y = []
heapq.heapify(Y)
for i in range(M):
    P = M-1-i
    Ls = X[P]
    for L in Ls:
        heapq.heappush(Y, -1*L)
    if len(Y)>0:
        Q = heapq.heappop(Y)
        out += -1*Q
print(out)

Solution (Python):
import heapq

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

for i in range(n):
    a, b = map(int, input().split())
    if m-a < 0:
        continue
    else:
        A[m-a].append(b)

available = []

for i in range(m-1, -1, -1):
    for item in A[i]:
        heapq.heappush(available, -item)
    if available:
        ans += -heapq.heappop(available)

print(ans)

Solution (Python):
import heapq

n,m=map(int, input().split())
ab = [[] for i in range(m+1)]
d = []
for i in range(n):
    a,b=map(int, input().split())
    if(not a>m):
        ab[a-1].append(-1*b)
res = 0
cnt = 0

for i in range(m):
    for j in range(len(ab[i])):
        heapq.heappush(d,ab[i][j])
    if(len(d)):
        res+=(heapq.heappop(d))
print(-1*res)

Solution (Python):
import heapq

N, M = list(map(int,input().split()))
A = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append([in1, in2])

A = sorted(A)
ans = 0
day = 1
cnt = 0
x = []

for i in range(M):
    while(cnt < N):
        if A[cnt][0] == day:
            heapq.heappush(x, -A[cnt][1])
            cnt += 1
        else:
            break
    if x:  ans -= heapq.heappop(x)
    day += 1

print(ans)

Solution (Python):
import heapq

N, M = list(map(int,input().split()))
A = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append([in1, in2])

A = sorted(A)
ans = 0
day = 1
cnt = 0
x = []

for i in range(M):
    while(cnt < N):
        if A[cnt][0] == day:
            heapq.heappush(x, -A[cnt][1])
            cnt += 1
        else:
            break
    if x:  ans -= heapq.heappop(x)
    day += 1

print(ans)

Solution (Python):
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,m=map(int, input().split())
    li=[]
    for _ in range(n):
        b,a=map(int, input().split())
        if m-b >= 0:
            li.append([a,m-b])
    li.sort(key=lambda x: x[1])
    h=[]
    for i in li:
        if len(h) >= i[1]+1:
            heapq.heappushpop(h, i[0])
        else:
            heapq.heappush(h, i[0])
    print(sum(h))
    

if __name__=='__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

def readinput():
    n,m=map(int,input().split())
    a=[]
    b=[]
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append(ai)
        b.append(bi)
    return n,m,a,b

def main(n,m,a,b):
    jobList=[]
    for i in range(10**5+1):
        jobList.append([])
    for i in range(n):
        jobList[a[i]].append(b[i])

    goodjobs=[]
    earn=0
    for d in range(1,m+1):
        for job in jobList[d]:
            heappush(goodjobs,-job)
        
        if len(goodjobs)>0:
            earn+=heappop(goodjobs)
    return -earn

if __name__=='__main__':
    n,m,a,b=readinput()
    ans=main(n,m,a,b)
    print(ans)

Solution (Python):
import heapq

n, m = map(int, input().split())
x = [[] for _ in range(m + 1)]
y = []
heapq.heapify(y)
for i in range(1, m + 1):
    heapq.heapify(x[i])
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        heapq.heappush(x[a], -b)
ans = 0
for i in range(1, m + 1):
    if x[i]:
        s = heapq.heappop(x[i])
        heapq.heappush(y, [s, i])
    if y:
        s, t = heapq.heappop(y)
        ans -= s
        if x[t]:
            s = heapq.heappop(x[t])
            heapq.heappush(y, [s, t])
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop, heappush
N, M = map(int, sys.stdin.readline().split())
A = defaultdict(list)
for line in sys.stdin:
    a, b = map(int, line.split())
    if a <= M:
    	A[M-a].append(b)

ans = 0
q = []
for i, B in sorted(A.items()):
    for b in B:
        heappush(q, b)
        ans += b
    while len(q) > i+1:
        b = heappop(q)
        ans -= b
print(ans)

Solution (Python):
import sys
from heapq import heappop, heappush
N, M = map(int, sys.stdin.readline().split())
A = [[] for _ in [0]*M]
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > M:
        continue
    A[M-a].append(b)

ans = 0
q = []
for i, B in enumerate(A):
    for b in B:
        heappush(q, b)
        ans += b
    while len(q) > i+1:
        b = heappop(q)
        ans -= b
print(ans)

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

lines = []
for line in sys.stdin:
    lines.append(line.rstrip('\r\n'))

n,m = lines[0].split()
n = int(n)
m = int(m)

a=[]
for i in range(n):
    x,y = lines[i+1].split()
    x = int(x)
    y = int(y)*(-1)
    a.append((x,y))
a.sort()
a.append((0,0))

h = []

cur = 0
summ = 0
for i in range(1,m+1):
    while(cur<n and a[cur][0]<=i):
        heappush(h,a[cur][1])
        cur+=1
    if(len(h)>0):
        summ+=heappop(h)*(-1)
print(summ)

Solution (Python):
import sys
readline = sys.stdin.readline
 
N,M = map(int,readline().split())
from collections import defaultdict
tasks = defaultdict(list)
for i in range(N):
  a,b = map(int,readline().split())
  tasks[a].append(b)
  
import heapq as hq
q = []
ans = 0
for i in range(1, M + 1):
  newtask = tasks[i]
  for t in newtask:
    hq.heappush(q,-t)
  if q:
    ans += -hq.heappop(q)
 
print(ans)

Solution (Python):
def main():
    import heapq
    n,m = map(int,input().split())
    job = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in job.keys():
            job[a] = [b]
        else:
            job[a].append(b)
    ans = 0
    hp = []
    for i in range(1,m+1):
        if i in job.keys():
            for j in range(len(job[i])):
                heapq.heappush(hp,-1*job[i][j])
        if len(hp)>0:
            ans += -1*heapq.heappop(hp)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

n,m = map(int, input().split())
ab = [[] * (m+1) for i in range(m+1)]
for i in range(n):
  a,b = map(int, input().split())
  if m - a < 0:
    continue
  ab[a].append(b)

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

Solution (Python):
import heapq
n, m = map(int, input().split())
limit = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        
        continue
    
    limit[m-a].append(b)

available = []
ans = 0
for i in range(m-1, -1, -1):
    
    for item in limit[i]:
        heapq.heappush(available, -item)
    if available:
        ans += -heapq.heappop(available)
print(ans)

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    B = [[] for _ in range(m)]
    for _ in range(n):
        a, b = map(int, input().split())
        if m - a >= 0:
            B[m - a].append(b)

    que = []
    res = 0
    for i in reversed(range(m)):
        for b in B[i]:
            heappush(que, -b)
        if que:
            res += heappop(que) * (-1)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import heapq

def main():
    N, M = map(int, input().split())
    a_to_b = {}
    for i in range(N):
        a, b = map(int, input().split())
        if a <= M:
            if a not in a_to_b:
                a_to_b[a] = []
            a_to_b[a].append(b)

    res = 0
    h = []
    for i in range(1,M+1):
        if i in a_to_b:
            b_list = a_to_b[i]
            for bi in b_list:
                heapq.heappush(h, (-1)*bi)
        if len(h) > 0:
            res -= heapq.heappop(h)

    print(res)


if __name__ == "__main__":
    main()

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

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

print(ans)

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

N, M = map(int, input().split())
D = defaultdict(list)

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

H = []
ans = [0]*(M+1)

for i in range(1, M+1):
  for j in D[i]:
    heappush(H, -j)
  if H:
    a = heappop(H)
    ans[i] = -a

print(sum(ans))

Solution (Python):
import sys



from collections import Counter
import heapq
from collections import deque

def input():
    return sys.stdin.readline().rstrip()


def main():
    N,M = map(int,input().split())
    A =[]
    for i in range(N):
        a,b = map(int,input().split())
        A.append((a,-b))
    A.sort()
    A = deque(A)

    h = []
    ans =0
    for i in range(1,M+1):

        while A:
            if A[0][0] ==i:
                temp = A.popleft()
                heapq.heappush(h,temp[1])
            else:
                break

        if len(h)==0:
            continue
        else:
            ans += heapq.heappop(h)


    print(-ans)







if __name__ == "__main__":
    main()

Solution (Python):

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for n in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1): 
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1]) 
        j += 1
    if len(hq):
        ans += - heappop(hq) 
print(ans)

Solution (Python):
import heapq

n, m = map(int,input().split())
ab = [[0] * 2 for i in range(n)]
for i in range(n):
    a, b = map(int,input().split())
    ab[i][0], ab[i][1] = a, -1*b
heapq.heapify(ab)

b = [0]
heapq.heapify(b)
ans = 0
for i in range(1, m+1):
    while ab:
        tmp = heapq.heappop(ab)
        if tmp[0] <= i:
            heapq.heappush(b, tmp[1])    
        else:
            heapq.heappush(ab, tmp)
            break
    if b:
        ans -= heapq.heappop(b)
print(ans)

Solution (Python):
import heapq

n, m = map(int,input().split())
ab = [[0] * 2 for i in range(n)]
for i in range(n):
    a, b = map(int,input().split())
    ab[i][0], ab[i][1] = a, -1*b
heapq.heapify(ab)

b = [0]
heapq.heapify(b)
ans = 0
for i in range(1, m+1):
    while ab:
        tmp = heapq.heappop(ab)
        if tmp[0] <= i:
            heapq.heappush(b, tmp[1])    
        else:
            heapq.heappush(ab, tmp)
            break
    if b:
        ans -= heapq.heappop(b)
print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

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

AB = []
for i in range(N):
    a,b = LI()
    AB.append((a,-b))

from operator import itemgetter

AB = sorted(AB,key = itemgetter(0))

import heapq

L = []
heapq.heapify(L)

ans = 0
r = 0
for i in range(1,M+1):
    for j in range(r,N):
        if AB[j][0] == i:
            heapq.heappush(L,AB[j][1])
        else:
            r = j
            break
    if len(L) >= 1:
        ans -= heapq.heappop(L)

print(ans)