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):
def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    
    import heapq
    cands = []
    abidx = 0
    ans = 0
    day = M
    while day > 0:
        
        while abidx < N and AB[abidx][0] <= M-day+1:
            _, point = AB[abidx]
            heapq.heappush(cands, -point)
            abidx += 1
        if len(cands) > 0:
            ans += heapq.heappop(cands)
            
        day -= 1
    print(-ans)


if '__main__' == __name__:
    resolve()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N, M = MAP()
AB = [LIST() for _ in range(N)]
AB.sort(key = lambda x: x[0])

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

print(ans)

Solution (Python):
N, M = map(int, input().split())
AB = [[] for _ in range(10**5+1)]
for _ in range(N):
    a, b = map(int, input().split())
    AB[a].append(b)

import heapq
h = []
heapq.heapify(h)

ans = 0
for a in range(1,M+1):
    for b in AB[a]:
        heapq.heappush(h, -b)
    heapq.heappush(h, 0)
    ans -= heapq.heappop(h)
    
print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os
import heapq


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    
    
    
    
    ab_list = [[] for i in range(100001)]
    for i in ab_s:
        ab_list[i[0]].append(i[1])
    for i in ab_list:
        if len(i) == 0:
            continue
        i.sort()

    a = []
    heapq.heapify(a)

    ans = 0
    
    
    for i in range(1, m + 1):
        
        if len(ab_list[i]) != 0:
            heapq.heappush(a, (-ab_list[i].pop(), i))

        if len(a) != 0:
            act_work = heapq.heappop(a)
            ans += -act_work[0]

            if len(ab_list[act_work[1]]) != 0:
                heapq.heappush(a, (-ab_list[act_work[1]].pop(), act_work[1]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_original_1(self):
        test_input = """3 4
4 210
4 150
3 150"""
        output = """360"""
        self.assertIO(test_input, output)

    def test_original_2(self):
        test_input = """2 1
1 10
1 20
"""
        output = """20"""
        self.assertIO(test_input, output)

    def test_original_3(self):
        test_input = """1 2
1 10
"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_original_4(self):
        test_input = """5 3
4 50
4 50
3 10
3 10
1 10
"""
        output = """20"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

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):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import heapq
import collections

N, M = rl()
daytasks = collections.defaultdict(list)
for i in range(N):
	a, b = rl()
	daytasks[a].append(b)

heap = []
ans = 0
for i in range(1, M+1):
	for t in daytasks[i]:
		heapq.heappush(heap, (-t, i))
	if len(heap) > 0:
		b, a = heapq.heappop(heap)
		b = -b
		ans += b
print(ans)

Solution (Python):
def resolve():    
    import heapq
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n)]
    b=[[] for _ in range(10**5+1)]
    for i,j in ab:
        b[i].append(-j)
    q=[]
    ans=0
    for i in range(1,m+1):
        for j in b[i]:
            heapq.heappush(q,j)
        if q:
            ans+=heapq.heappop(q)
    print(-ans)
        
if __name__ == '__main__':
    resolve()

Solution (Python):
import heapq
x = [[] for _ in range(10**5+1)]
n,m = map(int,input().split())

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

ans = 0
for l in range(1,m+1):
    for k in x[l]:
        heapq.heappush(cur, k*(-1))
    
    if cur != []:
        mi = heapq.heappop(cur)
        ans += mi * (-1)
        
print(ans)

Solution (Python):
from heapq import *
N,M=map(int,input().split())
X=[[] for i in range(M)]
A,B=0,0
for i in range(N):
  A,B=map(int,input().split())
  if A>M:
    continue
  X[-A].append(B)
P=0
Q=[]
heapify(Q)
for i in range(M-1,-1,-1):
  for j in range(len(X[i])):
    heappush(Q,-X[i][j])
  if len(Q):
    P-=heappop(Q)
print(P)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

N, M = map(int,input().split())
work = [[] for _ in range(10**5+1)]
ava = []
ans = 0

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

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

Solution (Python):
import heapq

n, m = map(int, input().split())
que = []
for _ in range(n):
    a, b = map(int, input().split())
    que.append((-b, a))
que.sort(key=lambda x: x[1], reverse=True)

def solve(que, m):
    ans = 0
    h = []
    heapq.heapify(h)
    for i in range(1, m + 1):
        while len(que) != 0 and que[-1][1] <= i:
            tmp = que.pop()
            heapq.heappush(h, tmp)
        if len(h) == 0: continue
        tmp = heapq.heappop(h)
        ans -= tmp[0]
    return ans

print(solve(que, m))

Solution (Python):
import collections
import heapq

n, m = map(int, input().split())
que = []
for _ in range(n):
    a, b = map(int, input().split())
    que.append((-b, a))
que.sort(key=lambda x: x[1])
que = collections.deque(que)
h = []
heapq.heapify(h)
ans = 0
for i in range(1, m + 1):
    while len(que) != 0 and que[0][1] <= i:
        tmp = que.popleft()
        heapq.heappush(h, tmp)
    if len(h) == 0: continue
    tmp = heapq.heappop(h)
    ans -= tmp[0]
print(ans)

Solution (Python):
_,m=map(int,input().split())
work=sorted([tuple(map(int,input().split()))for k in range(_)],key=lambda x:(-x[0],x[1]))
from heapq import heapify, heappop, heappush
now=[]

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

Solution (Python):
import heapq
n,m= map(int,input().split())
feeindays = [[] for _ in range(m)]
for i in range(n):
    a,b= map(int,input().split())
    if a<=m:feeindays[a-1]+=[b]
q=[]
heapq.heapify(q)
pay=0
for l in feeindays:
    for c in l:heapq.heappush(q,-c)
    if len(q)!=0:pay+=-1 * heapq.heappop(q)
print(pay)

Solution (Python):
from heapq import heappop, heapify, heappush
from collections import defaultdict
N, M = map(int,input().split())
d = defaultdict(list)
for i in range(N):
    a, b = map(int, input().split())
    d[a].append(b)
h = []
ans = 0
for i in range(1, M+1):
    if len(d[i]) != 0:
        for x in d[i]:
            heappush(h, -x)
    if len(h) != 0:
        ans -= heappop(h)
print(ans)

Solution (Python):
import heapq

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


jobs = []
ans = 0
for i in range(1,m+1):
    for rew in day_rews_l[i]:
        heapq.heappush(jobs, (-1)*rew)
    if jobs:
        rew_i = heapq.heappop(jobs)
        ans += (-1)*rew_i

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    job = [[] for i in range(m+1)]
    for i in range(n):
        a,b = map(int,ipt().split())
        if a <= m:
            job[a].append(-b)
    ma = 0
    hq = []
    for i in range(m+1):
        for j in job[i]:
            hpq.heappush(hq,j)
        if hq:
            ma += hpq.heappop(hq)
    print(-ma)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

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

pq = []
for a, b in X:
    heappush(pq, (a, b))
    
cand = []
ans = 0
for t in range(1, M + 1):
    while pq:
        a, b = heappop(pq)
        if a <= t:
            heappush(cand, -b)
        else:
            heappush(pq, (a, b))
            break

    if cand:
        v = heappop(cand)
        ans += -v

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, M = getNM()
query = [getList() for i in range(N)]

A_list = [[] for i in range(10 ** 5 + 1)]
for a, b in query:
    A_list[a].append(b)

job = []
heapq.heapify(job)

ans = 0
for i in range(1, M + 1):
    for j in A_list[i]:
        heapq.heappush(job, -j)
    if len(job) > 0:
        u = heapq.heappop(job)
        ans += -u
print(ans)

Solution (Python):
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  if a<=m:
    ab[m-a].append(-b)

ans=0
l=[]
for i in range(m-1,-1,-1):
  for b in ab[i]:
    heappush(l,b)

  if l:
    ans-=heappop(l)

print(ans)

Solution (Python):
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

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

ans=0
time=0
l=[]
for i in range(m):
  for b in ab[i]:
    heappush(l,b)
  if l:
    ans-=heappop(l)

print(ans)

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(10**5)]
    for i in range(N):
        a, b = map(int, input().split())
        AB[a-1].append(b)
    
    q = []
    ans = 0
    i = 0
    while i < M:
        for ab in AB[i]:
            heappush(q,-ab)
        if q:
            ans -= heappop(q)
        i += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda x:x[0])
counter = 0
content = 0
ans = 0
h = []
heapq.heapify(h)
for i in range(m):
  while counter < n and ab[counter][0]==i+1:
    heapq.heappush(h,-ab[counter][1])
    counter+=1
    content+=1
  if content != 0:
    ans-=heapq.heappop(h)
    content-=1
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()
W = ILL(N)

W.sort(reverse=True)

ans = 0
q = []
for i in range(M+1):
  while W:
    if W[-1][0] > i: break
    d,v = W.pop()
    heapq.heappush(q,-v)
  if q:
    ans -= q[0]
    heapq.heappop(q)
print(ans)

Solution (Python):


from heapq import *
n,m=map(int,input().split())

ab=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    
    if a<=m:
        ab[a-1].append(b)
x=[]
l=0
ans=0
for i in range(m-1,-1,-1):
    for j in ab[m-1-i]:
        heappush(x,-j)
        l+=1
    if l:
        l-=1
        ans+=heappop(x)
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())
    AB = [[] for _ in range(m)]
    for _ in range(n):
        a, b = map(int, input().split())
        if a <= m:
            AB[m - a].append(b)

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


if __name__ == '__main__':
    resolve()

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

import heapq
q = []
ans = 0
heapq.heapify(q)
for i in range(1,m+1):
    for v in V[i]:
        heapq.heappush(q,v)

    if len(q) == 0:
        pass
    else:
        ans -= heapq.heappop(q)
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[[] for i in range(10**5)]
for i in range(N):
    a,b=map(int,input().split())
    l[a-1].append(b)
h=[]
import heapq
a=0
for i in range(M):
    for j in l[i]:
        heapq.heappush(h,-j)
    if h:
        a-=heapq.heappop(h)
print(a)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()

from heapq import heappop, heappush
days = [[] for _ in range(M)]
for _ in range(N):
    a, b = mapint()
    if a>M:
        continue
    days[a-1].append(-b)

queue = []

ans = 0
for i in range(M):
    lis = days[i]
    for b in lis:
        heappush(queue, b)
    if queue:
        ans += heappop(queue)

print(-ans)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = deque([])
B = deque([])
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.popleft()
            heapq.heappush(q,B.popleft()*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)

Solution (Python):
import heapq
from collections import deque
N,M = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
A = [(-A[i][1],A[i][0]) for i in range(N)]
A = deque(A)
heap = []
cnt = 0
for i in range(M-1,-1,-1):
    k = M-i
    while len(A)>0 and A[0][1]<=k:
        heapq.heappush(heap,A.popleft())
    if len(heap)>0:
        b,a = heapq.heappop(heap)
        b = -b
        cnt += b
print(cnt)

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


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
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)]
class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    

    
    N, M = map(int, input().split())
    
    
    S = list(tuple(map(int, input().split())) for i in range(N)) 
    S.sort(key=itemgetter(1),reverse=True)
    
    ans=0
    fil=[1 for i in range(M)]

    tot=M
    bit=BIT(M)
    bit.initialize(fil)
    for s in S:
        a,b=s
        if a>M:continue
        
        
        
        t=bit.get_sum(a-1)
        
        if t>=tot:
            continue

        x=bit.find_kth_element(t+1)
        
        bit.add(x,-1)
        ans+=b
        tot-=1

    print(ans)
    


        




if __name__ == "__main__":
    main()

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

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

x = 0
res = 0

hq = []
heapq.heapify(hq)

for i in range(M):
    for j in range(x, N):
        if AB[j][0] > i+1:
            x = j
            break
        heapq.heappush(hq, AB[j][1]*-1)
    else:
        x = N
    
    if hq:
        res += heapq.heappop(hq)*-1

print(res)

Solution (Python):
from heapq import heapify, heappop, heappush
N,M = map(int,input().split())
A = [[] for _ in range(M+1)]

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

ans = 0
L = []
for day in range(1,M+1):
  for t in A[day]:
    heappush(L,-t)
  
  if not L:
    continue
  temp = heappop(L)
  ans += -temp
print(ans)

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

N,M=map(int,input().split())
A,B,C = [0]*N,[0]*N,[0]*N
for i in range(N):
    A[i],B[i] = map(int,input().split())
    C[i]=[A[i],B[i]]
C.sort()
C=deque(C)

a=[]
heapify(a)
ans=0

for i in range(M,-1,-1):
    while C:
        if C[0][0]<=M-i:
            heappush(a,(-1)*C[0][1])
            C.popleft()
        else:
            break
    if len(a)>0:
        p = heappop(a)
        ans += (-1)*p
        
print(ans)

Solution (Python):
import sys









input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        
        return max(lch, rch)

    def unit(self):
        return -INF

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def solve():
    n, m = getList()
    baito = []
    for i in range(n):
        a, b = getList()
        baito.append((b, a))

    baito.sort(reverse=True)
    st = Segtree_op(m)
    for i in range(m):
        st.update(i, i)

    ans = 0
    for kin, hi in (baito):
        if hi > m:
            continue
        tgt = st.query(0, m - hi + 1)
        if tgt != -INF:
            ans += kin
            st.update(tgt,-INF)

    
    
    
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    
    solve()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
jobs = [inpl() for _ in range(n)]
jobs.sort()
can = []
ind = 0
res = 0
for i in range(1,m+1):
    while ind < n:
        a,b = jobs[ind]
        if a == i:
            heappush(can,-b)
            ind += 1
            continue
        break
    if can != []:
        res -= heappop(can)
print(res)

Solution (Python):
import heapq
n,m=map(int,input().split())
d=[]
for i in range(n):
  a,b=map(int,input().split())
  d.append([a,b])
d=sorted(d, key=lambda student: student[0])
pointer=0
queue=[]
ans=0
for i in range(m+1):
  while pointer<n and d[pointer][0]==i:
    heapq.heappush(queue,-d[pointer][1])
    pointer+=1
    if pointer>=n:
      break
  if queue:
    ans+=heapq.heappop(queue)
print(-ans)

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

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]+[[100000000,0]]
for i in range(m):ab.append([i+1,0])
ab.sort()
from heapq import heappop,heappush
h=[]
j=0
ans=0
for i in range(1,m+1):
  while ab[j][0]<=i:
    heappush(h,-ab[j][1])
    j+=1
  ans-=heappop(h)
print(ans)

Solution (Python):
import heapq

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

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

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

print(-ans)

Solution (Python):
import heapq
from collections import defaultdict

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

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

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

print(ans)

Solution (Python):
import heapq
n,m = map(int,input().split())
b_list = [[] for _ in range(10**5+10)]

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

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

print(ans)

Solution (Python):
import heapq
n , m = map(int,input().split())
kouho = [[] for i in range(m)]
for i in range(n):
    a , b = map(int,input().split())
    if a <= m:
        kouho[a-1].append(-b)
ans = 0
p = []
heapq.heapify(p)

for i in range(m):

    for j in kouho[i]:
        heapq.heappush(p,j)
    if p:
        ans -= heapq.heappop(p)
print(ans)

Solution (Python):
import heapq
n , m = map(int, input().split())
ab=[[] for i in range(10**5)]

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

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