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

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return


def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return


def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return


def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

def D_():
    def add(i):
        while i <= m+1:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:-x[1])
    bit = [0]*(m+2)
    par = [i for i in range(m+2)]
    rank = [0]*(m+2)
    ans = 0
    for a,b in g:
        i = m-a+1
        if i <= 0:
            continue
        if sum(i) < i:
            ans += b
            if sum(i-1) == sum(i):
                l = i
                r = l+1
            else:
                l = 1
                r = i+1
                while r-l > 1:
                    mid = (l+r)//2
                    if root(mid) == root(i):
                        r = mid
                    else:
                        l = mid
            unite(l,r)
            add(l)
    print(ans)
    return


def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return


def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    for i in range(p):
        ai = a[i]
        if ai:
            b[0] += ai
            k = 1
            for j in range(p):
                c = ai*comb(p-1,j)*k%p
                k *= i
                if k >= p:
                    k %= p
                if j%2:
                    b[p-1-j] += c
                else:
                    b[p-1-j] -= c
                b[p-1-j] %= p
    print(*b)
    return


if __name__ == "__main__":
    D_()

Solution (Python):
import heapq
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
d=[[0]for i in range(b)]
sum=0
for i,j in c:
  if i<=b:
    d[i-1].append(j)
e=[]

for i in d:
  for j in i:
    heapq.heappush(e,-j)
  sum-=heapq.heappop(e)
      
    
  
print(sum)

Solution (Python):
from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        elif q and q[0]<b:heappushpop(q,b)
print(sum(q))

Solution (Python):
import heapq

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

ans = 0
h = []
for d in range(M-1,-1,-1):
    for b in job[d]:
        heapq.heappush(h, (-b,b))
    if len(h) > 0:
        ans += heapq.heappop(h)[1]

print ans

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

W = []  
for _ in range(N):
    W.append(tuple(map(int, input().split())))
W = sorted(W, key=lambda x: (x[0], -x[1]))


a = []
heapq.heapify(a)  

ans = 0
c = 0
for day in range(1, M+1):
    day_c = 0
    while c != N and W[c][0] == day:
        if day_c <= M-day:
            x = W[c][1]
            heapq.heappush(a, -x)  
            day_c += 1
        c += 1
    if len(a) >= 1:
        ans += -heapq.heappop(a)  

print(ans)

Solution (Python):

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

W = []
for _ in range(N):
    W.append(tuple(map(int, input().split())))
W = sorted(W, key=lambda x: (x[0], -x[1]))


a = []
heapq.heapify(a)  

ans = 0
c = 0
for day in range(1, M+1):
    day_c = 0
    while c != N and W[c][0] == day:
        if day_c <= M-day:
            x = W[c][1]
            heapq.heappush(a, -x)  
            day_c += 1
        c += 1
    if len(a) >= 1:
        ans += -heapq.heappop(a)  

print(ans)

Solution (Python):

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

W = []
for _ in range(N):
    W.append(tuple(map(int, input().split())))
W = sorted(W, key=lambda x: (x[0], -x[1]))


a = []
heapq.heapify(a)  

ans = 0
c = 0
for day in range(1, M+1):
    day_c = 0
    while c != N and W[c][0] == day:
        if day_c <= M-day:
            x = W[c][1]
            heapq.heappush(a, -x)  
            day_c += 1
        c += 1
    if len(a) >= 1:
        ans += -heapq.heappop(a)  

print(ans)

Solution (Python):
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*M
v=[[]for _ in q]
z=0
for a,b in t:
	if a<=M:v[a-1]+=[b]
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Solution (Python):
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
v=[[]for _ in'_'*M]
z=0
for a,b in t:
	if a<=M:v[a-1]+=[b]
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Solution (Python):
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,key=lambda x:x[0])
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Solution (Python):
import heapq

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

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

print(ans)

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for a in t[::2]:a>M or v[a-1].append(t[i+1]);i+=2
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Solution (Python):


import re
from collections import deque
from functools import reduce
from heapq import *
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    
    n, m, *t = map(int, open(0).read().split())

    
    d = [[] for i in range(m+1)]
    for i in range(n):
        a, b = t[2*i], t[2*i+1]
        if a > m:
            continue
        d[a].append(b)

    ans = 0
    tasks = []
    for t in range(m + 1):
        
        for tasksize in d[t]:
            heappush(tasks, -tasksize)
        if tasks:
            
            ans -= heappop(tasks)

    
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import heapq

N, M = map(int, input().split())
AB_list = []
[heapq.heappush(AB_list, list(map(int, input().split()))) for _ in range(N)]
ans = 0
kouho = []

for day in range(1, M + 1):
    if len(AB_list) != 0:
        while AB_list[0][0] <= day:           
            heapq.heappush(kouho, heapq.heappop(AB_list)[1]*(-1))
            if len(AB_list) == 0:
                break
    if len(kouho) != 0:
        ans += heapq.heappop(kouho)

print(ans * (-1))

Solution (Python):
from heapq import heappush, heappop

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

Solution (Python):
import heapq

N, M = map(int, input().split())
AB_list = []
[heapq.heappush(AB_list, list(map(int, input().split()))) for _ in range(N)]
ans = 0
kouho = []

for day in range(1, M + 1):
    if len(AB_list) != 0:
        while AB_list[0][0] <= day:           
            heapq.heappush(kouho, heapq.heappop(AB_list)[1]*(-1))
            if len(AB_list) == 0:
                break
    if len(kouho) != 0:
        ans += heapq.heappop(kouho)

print(ans * (-1))

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for _ in'_'*N:M<t[i]or v[t[i]-1].append(t[i+1]);i+=2
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Solution (Python):
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    if M - a < 0:
        continue
    
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        
        ok = -1
        ng = M - a
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if mid - bit.sum(mid) + 1 != cap:
                ok = mid
            else:
                ng = mid
        bit.add(ok + 1, 1)
print(ans)

Solution (Python):
from heapq import heappush, heappop

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        c[m - a].append(b)
r=0
h = []
for l in reversed(c):
    for x in l:
        heappush(h, -x)
    if h:
        r -= heappop(h) 
print(r)

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for _ in'_'*N:M<t[i]or v[t[i]-1].append(t[i+1]);i+=2
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Solution (Python):
import heapq
maxB = 10 ** 1

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

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

ans, heap, idx, lAB = 0, [], 0, len(AB)
for i in range(M):
    while idx < lAB and AB[idx][1] <= i + 1:
        heapq.heappush(heap, AB[idx])
        idx += 1
    if len(heap) > 0:
        ans += maxB - heapq.heappop(heap)[0]

print(ans)

Solution (Python):
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):M<t[2*i]or v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):
	if t[2*i]<=M:v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Solution (Python):
from heapq import heappush, heappop

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

for i in range(N):
  ab = list(map(int, input().split()))
  
  if ab[0] <= M:
    jobs[ab[0] - 1].append(ab[1])



hq = []
ans = 0
for i in range(M):
  for b in jobs[i]:
    heappush(hq, -1 * b)
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

print(ans)

Solution (Python):
from heapq import heappush, heappop

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

for i in range(N):
  ab = list(map(int, input().split()))
  
  if ab[0] <= M:
    jobs[ab[0] - 1].append(ab[1])



hq = []
ans = 0
for i in range(M):
  for b in jobs[i]:
    heappush(hq, -1 * b)
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

print(ans)

Solution (Python):

from queue import PriorityQueue
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)
pq = PriorityQueue()
ans = 0
for i in range(m)[::-1]:
    for b in jobs[i]:
        pq.put(-b)
    if not pq.empty():
        ans += -pq.get()
print(ans)

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Solution (Python):
from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] <= i:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


if __name__ == '__main__':
    p_d()

Solution (Python):


import re
from collections import deque
from functools import reduce
from heapq import heappop
from heapq import heappush
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    
    if wint == 1:
        
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    
    (n, m) = hints()[0]
    ab_s = hints(n)

    

    
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = []
    ti = 0
    for t in range(m + 1):
        
        while ti < n and ab_s[ti][0] == t:
            a, b = ab_s[ti]
            ti += 1
            heappush(tasks, -b)
        if tasks:
            
            ans -= heappop(tasks)

    
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        elif q and q[0]<b:heappushpop(q,b)
print(sum(q))

Solution (Python):
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:
		v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:
		heappush(q,-j)
	b=0
	if len(q):
		b=heappop(q)
	z-=b
print(z)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re

from scipy.misc import comb





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    N, M = l_inpl()
    AB = []
    for _ in range(N):
        AB.append(l_inpl())


    AB.sort(reverse=True)

    q = []
    ans = 0

    for remain_day in range(1, M+1):
        while True:
            if len(AB) > 0 and AB[-1][0] <= remain_day:
                _, b = AB.pop()
                heappush(q, -b)
            else:
                break
        if q:
            ans += -heappop(q)
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int,input().split())
A_B = [[0] for i in range(M)]
for i in range(N):
  A, B = map(int,input().split())
  if A <= M:
    A_B[A-1].append(-B)
  
import heapq
q = []
ans = 0
heapq.heapify(q)

for i in range(M):
  for j in A_B[i]:
    heapq.heappush(q, j)
  ans -= heapq.heappop(q)
  
print(ans)

Solution (Python):


import re
from collections import deque
from functools import reduce
from heapq import heappop
from heapq import heappush
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    
    if wint == 1:
        
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    
    (n, m) = hints()[0]
    ab_s = hints(n)

    

    
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = []
    for t in range(m + 1):
        
        while ab_s and ab_s[0][0] == t:
            a, b = ab_s.pop(0)
            heappush(tasks, -b)
        if tasks:
            
            ans -= heappop(tasks)

    
    print(ans)


if __name__ == '__main__':
    solve()

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

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

h = []
reward = 0

for day in range(1, M+1):
  bb = A.get(day)
  if bb:
    for x in bb:
      heapq.heappush(h, -x)
  if h:
    reward += heapq.heappop(h)
    
print(-reward)

Solution (Python):
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

AB.sort(key=lambda ab: (ab[0], -ab[1]))

heap = []
abi = 0
ans = 0
for i in range(1, M + 1):
    
    while abi < N and AB[abi][0] <= i:
        a, b = AB[abi]
        heapq.heappush(heap, (-b, a))
        abi += 1
    if heap:
        b, a = heapq.heappop(heap)
        ans += -b
print(ans)

Solution (Python):

import sys
import heapq
from collections import deque


def solve(N: int, M: int, work: "List[List[int]]"):
    wq = deque(work)
    paytree = []
    ans = 0

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

    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    work = [] 
    for _ in range(N):
        work.append([int(next(tokens)), int(next(tokens))])
    solve(N, M, sorted(work))

if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値とindex(同値があった場合は一番左)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        
        for i in range(n2):
            self.index[i+n2] = i
        
        for i in range(n2-1, -1, -1):
            
            self.index[i] = self.index[i*2]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[left]:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            else:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        
        if r <= a or b <= l:
            return (self.init, -1)
        
        if a <= l and r <= b:
            return (self.tree[k], self.index[k])
        
        m = (l + r) // 2
        left = self._get_val(a, b, k << 1, l, m)
        right = self._get_val(a, b, (k << 1) + 1, m, r)
        if self.func(left[0], right[0]) == left[0]:
            return left
        else:
            return right

N, M = MAP()
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

sti = SegTreeIndex(10**5+1, max, -INF)
for i in range(10**5+1):
    days[i].sort()
    if len(days[i]):
        sti.update(i, days[i][-1])

ans = 0
for i in range(M-1, -1, -1):
    val, idx = sti.get_val(0, M-i+1)
    if val == -INF:
        continue
    ans += val
    days[idx].pop(-1)
    if len(days[idx]):
        sti.update(idx, days[idx][-1])
    else:
        sti.update(idx, -INF)
print(ans)