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 bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, M, AB):
    ans = 0
    cand = []
    AB.sort(key=lambda x: x[0], reverse=True)
    for i in range(1, M+1):
        while AB and AB[-1][0] <= i:
            _, b = AB.pop()
            heapq.heappush(cand, -b)
        if cand:
            ans -= heapq.heappop(cand)
    return ans 

def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect

sys.setrecursionlimit(10**9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

N, M = LIST()

A = [[] for _ in range(10**4+1)]
for _ in range(N):
    a, b = LIST()
    if a <= M:
        A[b].append(a)

for a in A:
    a.sort(reverse=True)

off = list(range(1, M+1))
ans = 0

i = 10**4
while i > 0:
    for a in A[i]:
        attempt = bisect.bisect_left(off, a)

        if attempt < len(off):
            off.pop(attempt)
            ans += i

    if off == []:
        break;
    else:
        i -= 1

print(ans)

Solution (Python):
import bisect
import heapq

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

task.sort()

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

print(ans)

Solution (Python):
import heapq
N,M = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
AB.sort(key=lambda x:x[0])
index = 0
Works = []
ans = 0

for d in range(1,M+1):
    while 1:
        if index>=N:break
        if AB[index][0]<=d:
            heapq.heappush(Works,-AB[index][1])
            index += 1
        else:
            break
    if Works:
        ans -= heapq.heappop(Works)
print(ans)

Solution (Python):
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ABS = sorted(AB, key=lambda x: -x[1])
ABSS = sorted(ABS, key=lambda x: x[0])



heap = []
ans = 0
chkpos = 0

for i in range(1, M + 1):
  if chkpos < N:
    while ABSS[chkpos][0] <= i:
  
      heapq.heappush(heap, -1 * ABSS[chkpos][1])
      chkpos += 1
      if chkpos >= N:
        break
  
    if len(heap) > 0:
      ans -= heapq.heappop(heap)
  else:
    ans -= heapq.heappop(heap)
print(ans)

Solution (Python):
from heapq import heappush, heappop
n, m = map(int, input().split())
B = [[] for _ in range(m+1)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m: B[a] += [-b]
C = []
s = 0
for i in range(m+1):
    for b in B[i]: heappush(C, b)
    if C: s += heappop(C)
print(-s)

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

heapq.heapify(ABs)
availables = []
ans = 0
for i in range(1, M + 1):
    while ABs:
        a = heapq.heappop(ABs)
        if a[0] == i:
            heapq.heappush(availables, -a[1])
        else:
            heapq.heappush(ABs, a)
            break
    if availables:
        ans -= heapq.heappop(availables)

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



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

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

Solution (Python):







import heapq 
days=[[] for i in range(10**5+1)]
N,M=list(map(int,input().strip().split(' ')))
for _ in range(N):
    a,b=list(map(int,input().strip().split(' ')))
    days[a]+=[b]

ans=0
possible=[]
for i in range(M+1):
    for x in days[i]:
        heapq.heappush(possible,-x)
    if len(possible)==0:
        continue
    MAX_val=heapq.heappop(possible)
    ans+=-MAX_val
print(ans)

Solution (Python):
import heapq
n, m = [int(i) for i in input().split()]
d = [[] for i in range(m+1)]
for i in range(n):
    a, b = [int(_) for _ in input().split()]
    if a <= m:
        d[a].append(b)
ans = 0
cand = []
for i in range(1, m+1):
    for dd in d[i]:
        heapq.heappush(cand, -dd)
    if len(cand) > 0:
        ans += -heapq.heappop(cand)
print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, queue
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())


AB_dict = {}
for ab in AB:
    if ab[0] not in AB_dict.keys():
        AB_dict[ab[0]] = [ab[1]]
    else:
        AB_dict[ab[0]].append(ab[1])




perr(AB_dict)





























        












































ans = 0
tmp = queue.PriorityQueue()
keys = AB_dict.keys()
for i in range(1, M+1):
    
    if i in keys:
        for ab in AB_dict[i]:
            tmp.put((-ab, ab))
        
    perr('tmp')
    perr(tmp)
    if tmp.empty():
        continue
    
    
    
    ans += tmp.get()[1]
print(ans)

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

def main():
    N,M = [int(x) for x in input().split()]
    work = {}
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        if(a in work):
            work[a].append(-b)
        else:
            work[a] = [-b]

    cand = []
    heapq.heapify(cand)
    cnt = 0
    for i in range(1,M+1):
        if(i in work):
            for x in work[i]:
                heapq.heappush(cand,x)
        if(len(cand)==0):
            continue
        x = -heapq.heappop(cand)
        cnt += x

    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
n,m=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  l.append([a,b])
l.sort()
l.append([0,0])
ans=0
k=[]
j=0
for i in range(1,m+1):
  while j<=n and l[j][0]<=i:
    heapq.heappush(k, -1*l[j][1])
    j+=1
  if len(k)!=0:
  	ans+=-1*k[0]
  	heapq.heappop(k)
print(ans)

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+1]

    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[right]:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            else:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            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]) == right[0]:
            return right
        else:
            return left

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)

Solution (Python):
import heapq

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

lst.sort(key=lambda x:(x[1]), reverse=True)
lst.sort(key=lambda x:(x[0]), reverse=False)

ans = 0
ind = 0
kouho = []
for i in range(1, m+1):
    tugi = True
    while tugi:
        if ind >= n:
            break
        if lst[ind][0] == i:
            heapq.heappush(kouho, -lst[ind][1])
            ind += 1
        else:
            tugi = False
    try:
        ans += heapq.heappop(kouho) * (-1)
    except:
        IndexError

print(ans)

Solution (Python):
import heapq

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

D = {}
for i in range(N) :
    k,v = L[i]
    if k not in D :
        D[k] = [v]
    else :
        D[k].append(v)

class Heapq :
    def __init__(self, arr, desc=False) :
        if desc :
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
    
    def pop(self) :
        return heapq.heappop(self.hq) * self.sign
    
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
 
    def size(self):
        return len(self.hq)

q = Heapq([], True)
ans = 0
for k in range(1, M+1) :
    if k in D :
        for v in D[k] :
            q.push(v)
    if q.size() :
        ans += q.pop()
print(ans)

Solution (Python):
from heapq import heapify, heappush, heappop
N, M = map(int, input().split())
heap = []
heapify(heap)

A = [[] for i in range(M)]

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

count = 0
for a in A:
    for b in a:
        heappush(heap, -b)
    if len(heap) == 0:
        continue
    num = heappop(heap)
    count += num

print(-count)

Solution (Python):
import heapq

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

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

Solution (Python):


import sys
import heapq

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

tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref: heapq.heapify(ref)
    while ref: heapq.heappush(cur,heapq.heappop(ref))
    
    if not cur: continue
    tot+= heapq.heappop(cur)

print( -tot )

Solution (Python):
import heapq
N, M = map(int, input().split())
H = [[] for _ in range(M)]
for _ in range(N):
  A, B = map(int, input().split())
  if A <= M:
    H[A - 1].append(-B)
Q = []
c = 0
for d in range(M):
  for b in H[d]:
    heapq.heappush(Q, b)
  if Q:
    c -= heapq.heappop(Q)
print(c)

Solution (Python):
import heapq

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

AB.sort(reverse=True, key=lambda x:x[0])
AB.sort(key=lambda x:x[1])



ans = 0
p = 0
h = []
heapq.heapify(h)

for i in range(1, M + 1):
    while p < N and AB[p][1] <= i:
        heapq.heappush(h, -AB[p][0])
        p += 1
    if len(h) != 0:
        ans -= heapq.heappop(h)

print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
H = [[] for _ in range(M)]
for _ in range(N):
  A, B = map(int, input().split())
  if A <= M:
    H[A - 1].append(-B)
Q = []
cnt = 0
for d in range(M):
  for b in H[d]:
    heapq.heappush(Q, b)
  if Q:
    cnt -= heapq.heappop(Q)
print(cnt)

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

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

ans = 0
q = []
for j in range(1, M+1):
    for k in days[j]:
        heapq.heappush(q, -k)

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

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

q = []  
q1 = [] 

for i in range(N):
    day, reward = map(int, input().split())
    heapq.heappush(q,(-day,-reward))

while q:
    d, r = heapq.heappop(q)
    rest = M - len(q1)
    if rest >= -d:
        
        heapq.heappush(q1,-r)
    else:
        
        heapq.heappush(q1,-r)
        heapq.heappop(q1)
        
print(sum(q1))

Solution (Python):
import heapq

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

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

q = []
for i in range(M):
    for b in daylist[i]:
        heapq.heappush(q, -b)
    if q:
        ans += -heapq.heappop(q)
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+5)]
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):
import heapq as pq

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

day_to_reward = {}
for a, b in AB:
    if day_to_reward.get(a) is None:
        day_to_reward[a] = [b]
    else:
        day_to_reward[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    for reward in day_to_reward.get(i, []):
        pq.heappush(candidate, - reward)
    if candidate:
        ans += - pq.heappop(candidate)

print(ans)

Solution (Python):
import heapq as hq
def main():
    n,m = map(int,input().split(' '))
    w = [list(map(int,input().split(' '))) for i in range(n)]
    w=sorted(w,reverse=True)
    ans = 0
    l = []
    tmp = 0
    for i in range(1,m+1):
        while w and w[-1][0] <= i:
            hq.heappush(l,-w.pop()[1])
        if l:
            ans -=hq.heappop(l)
    print(ans)

if __name__ == '__main__':
    main()

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

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

heap = []
total = 0
for day in range(1, M + 1):
    for reward in rewards[day]:
        heapq.heappush(heap, -reward)

    if len(heap) > 0:
        max_reward = heapq.heappop(heap)
        total += -max_reward

print(total)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))
ans = 0
h = []
j = 0
for i in range(m)[::-1]:
    while j < n and m - ab[j][0] >= i:
        a,b = ab[j]
        heappush(h,(-b,a))
        j += 1
    if h:
        x,a = heappop(h)
        ans -= x
print(ans)

Solution (Python):
import heapq as pq

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

day_to_reward = {}
for a, b in AB:
    if day_to_reward.get(a) is None:
        day_to_reward[a] = [b]
    else:
        day_to_reward[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    for reward in day_to_reward.get(i, []):
        pq.heappush(candidate, - reward)
    if candidate:
        work_reward = - pq.heappop(candidate)
        ans += work_reward


print(ans)

Solution (Python):
import sys
from pprint import pprint
import heapq

def solve(n, m, a):
  
  cands = []
  ans = 0
  for i in xrange(m+1):
    
    if i in a and len(a[i]) > 0:
      for v in a[i]:
        heapq.heappush(cands, v)

    
    if len(cands) > 0:
      w = heapq.heappop(cands) 
      
      ans += -1 * w

  print(ans)


if __name__ == '__main__':

  n, m = map(int, sys.stdin.readline().strip().split(" "))
  
  a = {}
  
  for _ in xrange(n):
    a_i, b_i = map(int, sys.stdin.readline().strip().split(" "))
    
    
    if a_i not in a:
      a[a_i] = []
    a[a_i].append(-1 * b_i)
  solve(n, m, a)

Solution (Python):
"""
AtCoder
    :author: vierbein
"""
from __future__ import absolute_import, division, print_function



import sys
from heapq import *

def pp(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


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

idx = 0
h = []
res = 0

for rest in range(1, M + 1):
    while idx < N:
        a, b = pairs[idx]
        
        if a <= rest:
            heappush(h, -b)
            idx += 1
        else:
            break
    try:
        res += -heappop(h)
    except IndexError:
        pass

print(res)

Solution (Python):
from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        heappush(q, -jobs.pop(-1)[1])
    if q:
        ans -= heappop(q)
print(ans)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = [None]*N
for i in range(N):
    AB[i] = inpl()
AB.sort(key=lambda x: -x[0])
q = []
ans = 0
for m in range(1,M+1):
    while len(AB) > 0 and AB[-1][0] <= m:
        ab = AB.pop()
        heapq.heappush(q,-ab[1])
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)

Solution (Python):


import math
import sys
import itertools
import heapq
from operator import itemgetter


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


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

x = sorted(x,key=itemgetter(1),reverse = True)
x = sorted(x,key=itemgetter(0))

work = []
j = 0
answer = 0
for i in range(1,m+1,1):
    while j < n and x[j][0] == i:
        heapq.heappush(work,-x[j][1])

        j += 1
    if work:
        answer -= heapq.heappop(work)

print(answer)

Solution (Python):
from heapq import *

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

Solution (Python):
import heapq

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

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

rewords = 0
heap = []

for i in range(M):
    for reword in jobs[i]:
        heapq.heappush(heap, reword)
    if len(heap) >0:
        r = heapq.heappop(heap)
        rewords -= r

print(rewords)

Solution (Python):
import heapq
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
heapq.heapify(lst)
r = []
heapq.heapify(r)
ans = 0
d = 1

while True:
    while True:
        if len(lst) != 0:
            p_lst = heapq.heappop(lst)
            if p_lst[0] <= d:
                heapq.heappush(r, - p_lst[1])
            else:
                heapq.heappush(lst, p_lst)
                break
        else:
            break
    if len(r) != 0:
        ans += - heapq.heappop(r)
    d += 1
    if d > m:
        print(ans)
        exit()

Solution (Python):
import heapq
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = []
heapq.heapify(tmp)

for i in range(M+1):
    if i in C:
        right = C[i]
        for j in right:
            heapq.heappush(tmp,-1*j)
        
    if tmp != []:
        answer += -1*heapq.heappop(tmp)
print(answer)

Solution (Python):
from heapq import heappush, heappop

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

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
r=0
from heapq import heappop,heappush
q=[]
l=[[] for i in range(10**5)]
for a,b in AB:
    l[a-1].append(b)
for i in range(M):
    for e in l[i]:
        heappush(q,-e)
    if len(q)>0:
        r+=-heappop(q)
print(r)

Solution (Python):
from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = []
for _ in range(n):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort(reverse=True)
ans = 0
q = []
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        heappush(q, -jobs.pop()[1])
    if q:
        ans -= heappop(q)
print(ans)

Solution (Python):
from heapq import *

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

Solution (Python):
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    work = [None for _ in range(N)]
    q = []
    heapq.heapify(q)
    for i in range(N):
        a, b = map(int, input().split())
        work[i] = (a, -b)
    
    work.sort()
    ans = 0
    id = 0
    for i in range(M):
        while id < N:
            if work[id][0] <= i + 1:
                heapq.heappush(q, (work[id][1], work[id][0]))
                id += 1
            else: break
        
        if q:
            gain, day = heapq.heappop(q)
            ans -= gain

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import heapq

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

tank = []

p = []

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

q = 0
res = 0

for i in range(m+1):
    while q <= n-1 and p[q][0] <= i:
        heapq.heappush(tank,-p[q][1])
        q += 1
    
    if len(tank) == 0:
        continue
    else:
        res -= heapq.heappop(tank)
    

print(res)

Solution (Python):
import heapq
Heappop=heapq.heappop
Heappush=heapq.heappush
N,M=map(int,input().split())
L=[]
for _ in range(N):
    a,b=map(int,input().split())
    L.append([a,-b])
L.sort()
q=[0]*10**5
ans=0
d=1
memo=0
while d<=M:
    while memo<=N-1:
        a,b=L[memo]
        if d<a:
            break
        else:
            Heappush(q,b)
            memo+=1
    ans-=Heappop(q)
    d+=1
print(ans)

Solution (Python):
import heapq

n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for i in range(n)]
ab = sorted(ab,key=lambda x: x[0],reverse=True)
heap = []
ans = 0
for i in range(1,m+1):
    while True:
        if not ab:
            break
        elif ab[-1][0] <= i:
            x = ab.pop(-1)
            heapq.heappush(heap,x[1]*-1)
        else:
            break
    if heap:
        y = heapq.heappop(heap)
        ans += y*-1
print(ans)

Solution (Python):

import sys
import collections
from operator import itemgetter
import heapq


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    jobs_time = collections.defaultdict(list)
    for a,b in zip(A,B):
        jobs_time[b].append(a)

    jobs_time = sorted(jobs_time.items(),reverse=True)
    job_list = [0] * M

    for k,v in jobs_time: 
        v.sort()
        st = -1
        for vv in v:
            if vv <= M:
                for i in range(max(st,vv-1),len(job_list)):
                    if job_list[i] < k:
                        job_list[i] = k
                        st = min(i+1,len(job_list))
                        break
            else:
                break

        if all(j>0 for j in job_list):
            break

    print(sum(job_list))

    return

def solve2(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((b,a))

    jobs_time = sorted(jobs_time,key=itemgetter(0,1),reverse=True)
    
    job_list = [0] * M
    job_cnt = 0
    res = 0
    end = len(job_list)
    for b,a in jobs_time: 
        if a <= M:
            for i in range(a-1,end):
                if job_list[i] < b:
                    if job_list[i] == 0:
                        job_cnt += 1
                    else:
                        res -= job_list[i]
                    job_list[i] = b
                    res += b
                    break
            if job_cnt >= len(job_list):
                break

            for i in range(end-1,-1,-1):
                if job_list[i] == 0:
                    end = i + 1
                    break

    print(res)

def solve3(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((a,b))
    jobs_time = sorted(jobs_time,key=itemgetter(0))

    job_list = []
    res = 0
    js = 0
    
    for i in range(M):
        for j in range(js,N):
            if jobs_time[j][0] == (i+1):
                heapq.heappush(job_list,(- jobs_time[j][1], jobs_time[j][1]))
            elif jobs_time[j][0] > (i+1):
                js = j
                break

        if len(job_list) > 0:
            _,b = heapq.heappop(job_list)
            res += b

    print(res)




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

if __name__ == '__main__':
    main()