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):
class Work:
    count=0
    def __init__(self,payday,money):
        Work.count+=1
        self.count=Work.count
        self.payday=payday
        self.money=money
 
    def __ft__(self,other):
        if self.money>other.money:
            return True
        if self.money==other.money:
            if self.payday<other.payday:
                return True
            if self.payday==other.payday:
                if self.count<other.count:
                    return True
        return False

    def __gt__(self,other):
        if self.money<other.money:
            return True
        if self.money==other.money:
            if self.payday>other.payday:
                return True
            if self.payday==other.payday:
                if self.count>other.count:
                    return True
        return False


n,limit=[int(i) for i in input().split()]


baitolist=[]
for i in range(n):
    payday,money=[int(i) for i in input().split()]
    work=Work(payday,money)
    baitolist.append(work)


summoney=0    
rank=[[] for i in range(limit+1)]
for baito in baitolist:
    if baito.payday<=limit:
        rank[baito.payday].append(baito)

        
import heapq
accessible=[]
count=1


for i in range(limit):
    for baito in rank[count]:
        heapq.heappush(accessible,baito)
    if accessible!=[]:
        dowork=heapq.heappop(accessible)
        summoney+=dowork.money
    count+=1
    
    
print(summoney)

Solution (Python):
import heapq
n,m = map(int, input().split())
job = {}
for i in range(n):
    a,b = map(int, input().split())
    if a not in job.keys():
        job[a] = [(-b,a)]
    else:
        job[a].append((-b,a))
 
hq = []
 
max_income = 0
for i in range(1,m+1):
    if i in job.keys():
        for j in job[i]:
            heapq.heappush(hq,(j))
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i
 
print(max_income)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
n,m = map(int, input().split())
job_list = {}
for i in range(n):
    a,b = map(int, input().split())
    if a in job_list:
        job_list[a].append((-b,a))
    else:
        job_list[a] = [(-b,a)]



hq = []
max_income = 0

for i in range(1,m+1):
    if i in job_list:
        for j in job_list[i]:
            heapq.heappush(hq, j)
    
        
        
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
n,m = map(int, input().split())
job_list = []
for i in range(n):
    a,b = map(int, input().split())
    job_list.append((a,b))
job_list.sort(key=lambda x:x[0])


hq = []
max_income = 0
j = 0
for i in range(1,m+1):
    while j < n and job_list[j][0] <= i:
        heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Solution (Python):
import heapq
n,m = map(int, input().split())
job_list = []
for i in range(n):
    a,b = map(int, input().split())
    job_list.append((a,b))
job_list.sort(key=lambda x:x[0])


hq = []
max_income = 0
j = 0
for i in range(1,m+1):
    while j < n and job_list[j][0] <= i:
        heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Solution (Python):
import heapq
n,m = map(int, input().split())
job_list = []
for i in range(n):
    a,b = map(int, input().split())
    job_list.append((a,b))
job_list.sort(key=lambda x:x[0])


hq = []
max_income = 0
j = 0
for i in range(1,m+1):
    while j < n and job_list[j][0] <= i:
        heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Solution (Python):

import sys, math, fractions, itertools, heapq


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    hq = []
    ans, j = 0, 0
    X = sorted(zip(A, B), key=lambda x: x[0])
    for i in range(1,M+1):
        while (j<N) and (X[j][0] <=i):
            heapq.heappush(hq,-X[j][1])
            j+=1
        if hq:
            ans-=heapq.heappop(hq)
    print(ans)
    return



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))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Solution (Python):

import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

print(ans)

Solution (Python):



from heapq import heappush, heappop

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      s += (-sum([heappop(top) for _ in range(a-k) if len(top) != 0]))
      k = a
    heappush(top, -b)

  s += (-sum([heappop(top) for _ in range(m-k+1) if len(top) != 0]))
  print(s)

if __name__=='__main__':
  main()

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
import heapq
n,m = [int(i) for i in input().split()]
a = [[int(k) for k in input().split()] for _ in range(n)]


a.sort(key=lambda x: (x[0], x[1]))

current = 0
ans = 0
queue = []
for i in range(1,m+1):
    while current < len(a) and a[current][0] <= i:
        heapq.heappush(queue,-a[current][1])
        current += 1
    if len(queue) >= 1:
        temp = heapq.heappop(queue)
        ans += -temp

print(ans)

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


AB.sort()

import heapq

h=[]
ans=0
j=0
for i in range(1,M+1):
    while j<N: 
        
        if AB[j][0]>i:
            break
        else:
            
            
            
            heapq.heappush(h,-AB[j][1])
            j+=1
    
    if h!=[]:
        
        
        
        k=-heapq.heappop(h)
        ans+=k
print(ans)

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

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

hq = []
ans, j = 0, 0

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

Solution (Python):
from heapq import heappush, heappop
 
def main():
    n, m = map(int,input().split())
    
    jobs = []
    for i in range(n):
        day, value = map(int,input().split())
        jobs.append((day, value))

    jobs.sort()
    
    cur, res = 0, 0
    done = []
    h = []
    for i in range(1, m+1):
        while cur < n and jobs[cur][0] <= i:
            heappush(h, -jobs[cur][1])
            cur += 1
        if not h:
            continue
        res -= heappop(h)
 
    print(res)
 
if __name__ == "__main__":
    main()

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

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

print(ans)

Solution (Python):
from heapq import heappush, heappop
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)
ans = 0
j = 0
que = []
for i in range(1, M + 1):
    while j < N and D[j][0] <= i:
        heappush(que, -D[j][1])
        j += 1
    if que:
        ans += -heappop(que)

print(ans)

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

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

print(ans)

Solution (Python):
import heapq
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ABdct = {}
    for _ in range(N):
        A, B = [int(x) for x in stdin.readline().rstrip().split()]
        if A in ABdct:
            ABdct[A].append(B)
        else:
            ABdct[A] = [B]
    ans = 0
    candidate = []
    for i in range(1, M + 1):
        if i in ABdct:
            for b in ABdct[i]:
                heapq.heappush(candidate, -b)
        if not candidate:
            continue
        b = heapq.heappop(candidate)
        b = -b
        ans += b
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


from heapq import heappush, heappop

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



workList = {}
for i in range(n):
    a, b = map(int, input().split())
    if a not in workList:
        workList[a] = [b]
    else:
        workList[a].append(b)

hq = []
sum = 0
for i in range(1, m + 1):
    
    
    if i in workList:
        for w in workList[i]:
            heappush(hq, -w)

    
    if len(hq) > 0:
        val = heappop(hq)
        sum += -val

print(sum)

Solution (Python):


from heapq import heappush, heappop

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


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


hq = []
sum = 0
for i in range(1, m + 1):
    if i in workList:
        for w in workList[i]:
            heappush(hq, w)

    val = None
    if len(hq) > 0:
        val = heappop(hq)
    if val is not None:
        sum += -val

print(sum)

Solution (Python):
import heapq
N, M = [int(x) for x in input().split()]
AB_list = [[] for _ in range(M)]
for _ in range(N):
    A, B = list(map(int, input().split()))
    if (A > M): continue
    AB_list[A-1].append(B)
h = []
ans = 0
for i in range(M):
    for B in AB_list[i]:
        heapq.heappush(h, -B)
    
    if (len(h)):
        ans += -heapq.heappop(h)
print(ans)

Solution (Python):
from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)

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

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

L.sort(key = lambda x:(x[0]))
    
m = []
index = 0
ans = 0
for i in range(1, M + 1):
    c = 0
    for j in range(index, N):
        c += 1
        if L[j][0] <= i:
            heappush(m, -L[j][1])
        else:
            index = j
            c = 0
            break
    index += c
    
    if len(m) != 0:
        ans += heappop(m) * -1

print(ans)

Solution (Python):
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = {}
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a in d1:
      d1[a].append(b)
    else:
      d1[a] = [b]
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    else:
      if _len(d2) == 0:
        continue
    result += maxb
    d2[maxb] -= 1
    if d2[maxb] == 0:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
  print(result)
main()

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)


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

print(rewards)

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

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

print(ans)

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

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

reward=defaultdict(lambda: []) 

hq=[]
for _ in range(N):
	a,b=map(int, sys.stdin.readline().split())
	reward[a].append(-1*b)


hq=[]
ans=0
for day in range(M-1,-1,-1):
	for r in reward[M-day]:
		heappush(hq,r)
	if hq:
		t=heappop(hq)
		ans+=t*-1

print ans

Solution (Python):
from collections import defaultdict
import heapq

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

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

h = []
res = 0

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

print(-res)

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

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

h = []
ans = 0

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

Solution (Python):
import heapq

n, maxDays = map(int, input().split())
a = sorted([list(map(int, input().split())) for _ in range(n)])

pq = []
idx = 0
ret = 0
for day in range(maxDays + 1):
    while idx < n and a[idx][0] <= day:
        heapq.heappush(pq, -a[idx][1])
        idx += 1
    if pq:
        ret -= heapq.heappop(pq)

print(ret)

Solution (Python):
import  heapq

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

memo = [[] for _ in range(10**5)]
for _ in range(n):
    a, b = map(int, input().split())
    memo[a-1].append(-b)

pq = []

for i in range(m):
    for j in memo[i]:
        heapq.heappush(pq,j)
    if len(pq):
        ans += -heapq.heappop(pq)

print(ans)

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

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

h = []
ans = 0

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

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

maxA = 10**5

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

PQ = []
ans = 0
for dayRest in range(1, M+1):
    for B in works[dayRest-1]:
        heappush(PQ, B)
    if not PQ: continue
    B = heappop(PQ)
    ans += -B

print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict as dd
N, M = map(int, input().split())
arrs = dd(list)
for _ in range(N):
  a, b = map(int, input().split())
  arrs[a].append(-b)
q = []
ans = 0
for a in range(1, M+1):
  for b in arrs[a]:
    heappush(q, b)
  if len(q):
    ans -= heappop(q)
print(ans)

Solution (Python):
from heapq import heappop,heappush
N,M = map(int,input().split())
job = [list(map(int,input().split())) for _ in range(N)]
job.sort()
H = []
ans = 0
i = 0
for x in range(1,M + 1):
    while i < N and job[i][0] == x:
        add = [-job[i][1],job[i][0]]
        heappush(H,add)
        i += 1
    if len(H) != 0:
        salary,k = heappop(H)
        ans += -1 * salary
print(ans)

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) 
heap = []
rewards = 0
for i in range(M):
    for reward in jobs[i]:
        heapq.heappush(heap,reward)
    if len(heap) != 0:
        r = heapq.heappop(heap)
        rewards += -r
print(rewards)

Solution (Python):
import heapq

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

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

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


print(total)

Solution (Python):
import heapq

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

candidate_queue = []
ans = 0

for i in range(1, M + 1):
    while case:
        if case[-1][0] <= i:
            heapq.heappush(candidate_queue, -case.pop(-1)[1])
        else:
            break

    if candidate_queue:
        ans += -heapq.heappop(candidate_queue)

print(ans)

Solution (Python):
import heapq

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

candidate_queue = []
ans = 0

for i in range(1, M + 1):
    while case:
        if case[-1][0] <= i:
            heapq.heappush(candidate_queue, case.pop(-1)[1] * (-1))
        else:
            break

    if candidate_queue:
        ans += heapq.heappop(candidate_queue) * (-1)

print(ans)

Solution (Python):
import heapq
N_baito,M_days = map(int,input().split())
hosyuList = [[] for _ in range(M_days)]

for _ in range(N_baito):
    days,hosyu = map(int,input().split())
    if days <= M_days:
        hosyuList[days-1].append(hosyu)

workList = []
hosyu = 0
for day in range(M_days):
    for baito in hosyuList[day]:
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)

Solution (Python):
import numpy as np
import heapq
N,M = map(int,input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]

for _ in range(N):
  a,b = map(int,input().split())
  jobs[a].append(b)
ans = 0
heap = []
for d in range(M+1):
  if jobs[d]: 
    for _b in jobs[d]:
      heapq.heappush(heap,-_b) 
  if heap: 
    ans += -heapq.heappop(heap) 
print(ans)

Solution (Python):
class SegTree:
    init_val = -1  

    def __init__(self, init_l):
        self.n = len(init_l)
        self.n0 = 2 ** (self.n - 1).bit_length()  
        self.l = [self.init_val] * 2 * self.n0  
        for i in range(self.n):
            self.l[i + self.n0 - 1] = init_l[i]
        for i in range(self.n0 - 2, -1, -1):
            self.l[i] = self.func(self.l[2 * i + 1], self.l[2 * i + 2])

    
    def func(self, x, y):
        return max(x, y)

    def update(self, i, new):
        i += self.n0 - 1
        self.l[i] = new
        while i + 1:
            i = (i - 1) // 2
            self.l[i] = self.func(self.l[i * 2 + 1], self.l[i * 2 + 2])

    
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n0)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.init_val
        if a <= l and r <= b:
            return self.l[k]
        vl = self._query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self._query(a, b, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ba = []
for _ in range(n):
    a, b = map(int, input().split())
    ba.append([b, a])
ba.sort(reverse=True)
days = [x for x in range(m)]
ans = 0
s = SegTree(days)
for x in ba:
    a = x[1]
    b = x[0]
    lim = m - a
    if lim < 0:
        continue
    d = s.query(0, lim+1)
    if d >= 0:
        ans += b
        s.update(d, -1)
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
r_jobs = list(reversed(jobs[:]))
ans = 0
q = []
cnt = 0
l = len(jobs)
for i in range(m+1):
    while cnt < l:
        if r_jobs[cnt][0] == i:
            heapq.heappush(q, -jobs.pop()[1])
            cnt += 1
        else:
            break

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

print(ans)

Solution (Python):
import os,re,sys,operator
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

setrecursionlimit(10**6)

n,m=map(int,stdin.readline().rstrip().split())
l=[[] for _ in range(m)]
h=[]
heapq.heapify(h)
for i in range(n):
    a,b=map(int,stdin.readline().rstrip().split())
    if a>m:
        continue
    l[m-a].append(b)
ans=0
for i in range(m-1,-1,-1):
    for j in l[i]:
        heapq.heappush(h,-j)
    if len(h)!=0:
        ans+=-(heapq.heappop(h))
print(ans)

Solution (Python):
n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

Solution (Python):
from heapq import *
N,M = [int(x) for x in input().split()]

dic = {}
for m in range(1,M+1):
    dic.setdefault(m,[])
for _ in range(N):
    A,B = [int(x) for x in input().split()]
    if A <= M: dic.setdefault(A, []).append(B)

h = []
ans = 0
for m in dic.keys():
    for b in dic[m]:
        heappush(h, -b)
    if h:
        ans += -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=[]
r=0
for d in range(M):
  for v in H[d]:
    heapq.heappush(Q, v)
  if Q:
    r -= heapq.heappop(Q)
print(r)

Solution (Python):
import sys
import heapq

N,M = map(int,sys.stdin.readline().split())
jobList={}
for i in range(N):
  a,b = map(int,sys.stdin.readline().split())
  if a in jobList:
    jobList[a].append(b)
  else:
    jobList[a]=[b]
    
heapList=[]
heapq.heapify(heapList)
ans=0
for i in range (1,M+1):
  if i in jobList:
    for val in jobList[i]:
      heapq.heappush(heapList,val*-1)
  if len(heapList)>0:
    ans+=heapq.heappop(heapList)
print(ans*-1)

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

heap = []
ans = 0
for i in range(m+1):
    if jobs[i]:
        for x in jobs[i]:
            heapq.heappush(heap,-x)
    if heap:
        ans += -heapq.heappop(heap)


print(ans)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N, M = map(int, input().split())
parttime = []

for i in range(N):
	a, b = map(int, input().split())
	parttime.append((a, b))
	
parttime.sort()
index = 0
ans = 0
myheap = []

for day in range(M, -1, -1):
	for i in range(index, N):
		if (parttime[i][0] + day) <= M:
			heapq.heappush(myheap, -parttime[i][1])
			index = i + 1
		else:
			index = i
			break
			
	if myheap:
		ans -= heapq.heappop(myheap)
		
print(ans)

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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

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

for i in range(M + 1):
	for j in jobs[i]:
		heapq.heappush(myheap, -j)
			
	if myheap:
		ans -= heapq.heappop(myheap)
		
print(ans)

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


n, m = map(int, input().split())
tmp = [ [] for _ in range(10 ** 5 + 1) ]
for _ in range(n):
    a, b = map(int, input().split())
    tmp[a].append(b)

h = []
ans = 0
for i in range(1, m+1):
    for bb in tmp[i]:
        heappush(h, -bb)
    if h:
        ans += -heappop(h)
print(ans)

Solution (Python):
import heapq

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

heap = []
ans = 0

for i in range(M+1):
    
    if jobs[i]:
        for x in jobs[i]:
            heapq.heappush(heap,-x)
    
    if heap:
        ans += -heapq.heappop(heap)

print(ans)

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

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

count = 0
current = []

for day in range(1, M + 1):
    if day in AB:
    	for work in AB[day]:
            heapq.heappush(current, -work)

    
    if len(current) > 0:
        count += -heapq.heappop(current)

print(count)

Solution (Python):
import  heapq
 
N, M = map(int, input().split())
data = [[int(x) for x in input().split()] for i in range(N)]
data.sort(reverse=True, key=lambda x: (-x[0], x[1]))
 
day = M
reward = 0
 

q = []
i = 0
for d in range(1, M + 1):
    for t in range(i, N):
        if data[t][0] > d:
            break
        i += 1
        heapq.heappush(q, -1 * data[t][1])
    if q:
        reward += heapq.heappop(q)
 
print(-1 * reward)

Solution (Python):
import heapq


N,M=map(int,input().split())
 
i=0
inp ={}
while i<N:
  readTime,inCome=map(int,input().split())
  if readTime in inp:
    inp[readTime].append(-inCome)
  else:
    inp[readTime]=[-inCome]
  
  i=i+1
 

 
result=0
pool=[]
heapq.heapify(pool)
i=1
while i<=M:
  if i in inp:
    for k in inp[i]:
      heapq.heappush(pool,k)
  if len(pool)>0:
    result=result-heapq.heappop(pool)
  i=i+1
 
print(result)

Solution (Python):
from heapq import heappop, heappush

n, m = map(int, input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]

for _ in range(n):
    day, reward = map(int, input().split())
    jobs[day].append(reward)

q = []
ans = 0
for i in range(m + 1):
    if jobs[i]:
        for reward in jobs[i]:
            heappush(q, -reward)
    if q:
        ans += -heappop(q)

print(ans)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],-B[i]])
a.sort(key = lambda x:(x[0]))

from bisect import bisect_left, bisect_right
import heapq

ans = 0
p = 0
h = []

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

print(ans)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

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

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

print(ans)

Solution (Python):
from heapq import heappush, heappop

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

tasks.sort()

q = []
p = 0
ans = 0
for i in range(1, M+1):
    while p < N and tasks[p][0] <= i:
        heappush(q, -tasks[p][1])
        p += 1
    if len(q) == 0:
        continue
    ans -= heappop(q)

print(ans)

Solution (Python):
n,m = map(int,input().split())
import heapq
from collections import defaultdict
dic = defaultdict(list)
l = []
heapq.heapify(l)
for i in range(n):
    a,b=map(int,input().split())
    b = -b
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    for i in dic[i+1]:
        heapq.heappush(l,i)
    if len(l) ==0 : M = 0
    else:
        
        M = heapq.heappop(l)
        s += -M
print(s)

Solution (Python):
n,m = map(int,input().split())
import heapq
from collections import defaultdict
dic = defaultdict(list)
l = []
heapq.heapify(l)
for i in range(n):
    a,b=map(int,input().split())
    b = -b
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    for i in dic[i+1]:
        heapq.heappush(l,i)
    if len(l) ==0 : M = 0
    else:
        
        M = heapq.heappop(l)
        s += -M
print(s)