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 Node:
    
    def __init__(self, i):
        self.end = i + 1
        self.days = {i}


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

ans = 0
schedule = {}


def concat(node1, node2, x):
    if len(node1.days) < len(node2.days):
        node1, node2 = node2, node1
    else:
        node1.end = node2.end
    node1.days |= node2.days
    for i in node2.days:
        schedule[i] = node1
    schedule[x] = node1
    node1.days.add(x)

BA.sort(reverse=True)
for b, a in BA:
    x = a
    if a in schedule:
        x = schedule[a].end
    if x > M:
        continue
    ans += b
    if x - 1 in schedule:
        w1 = schedule[x - 1]
        if x + 1 in schedule:
            w2 = schedule[x + 1]
            concat(w1, w2, x)
        else:
            schedule[x] = w1
            w1.end += 1
            w1.days.add(x)
    elif x + 1 in schedule:
        w2 = schedule[x + 1]
        schedule[x] = w2
        w2.days.add(x)
    else:
        schedule[x] = Node(x)
print(ans)

Solution (Python):
import heapq

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



ans = 0
work = []
for i in range(M):
    remain = i + 1
    
    while len(AB) > 0:
        ab = heapq.heappop(AB)
        if ab[0] > remain:
            heapq.heappush(AB, ab)
            break
        heapq.heappush(work, (-ab[1], ab[0]))
    if len(work) == 0:
        continue
    v = heapq.heappop(work)
    ans -= v[0]
    
print(ans)

Solution (Python):
import heapq
N,M=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(N)]
l.sort(reverse=True)

h=[]
ans=0
for i in range(1,M+1):
    while l and l[-1][0]==i:
        heapq.heappush(h,l.pop()[1]*(-1))
    if h:
        ans-=heapq.heappop(h)
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)


ans = 0
heap = []

for i in range(M) :
    

    for hou in jobs[i] :
        heapq.heappush(heap, hou)
    if len(heap) > 0 :
        thou = heapq.heappop(heap)
        ans += -thou

print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
lst = []
for _ in range(N):
    A, B = map(int, input().split())
    lst.append([A, -B])
lst.sort()

ans = 0
index = 0
hq = []
for i in range(M):
    while index < N and lst[index][0] <= i + 1:
        heapq.heappush(hq, lst[index][1])
        index += 1
    
    if len(hq) > 0:
        ans -= heapq.heappop(hq)
    
print(ans)

Solution (Python):
import heapq
n,m=map(int, input().split())
jobs=[[] for i in range(m)]
for i in range(n):
    a,b=map(int, input().split())
    if a > m:
        continue
    jobs[m-a].append(b)
q=[]
ans=0
for i in range(m,0,-1):
    for job in jobs[i-1]:
        heapq.heappush(q, -job)
    if len(q) > 0:
        ans += (-heapq.heappop(q))
print(ans)

Solution (Python):
from sys import stdin
from collections import deque
import heapq


N, M = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
AB.sort(key=lambda x: (x[0], -x[1]))
work = [deque([]) for _ in range(M + 1)]

for ab in AB:
    if ab[0] <= M:
        work[ab[0]].append(ab[1])

ans = 0
day = 1
available_work = []
while day <= M:
    for w in work[day]:
        heapq.heappush(available_work, -w)
    if len(available_work) > 0:
        ans += heapq.heappop(available_work)
    day += 1

print(-ans)

Solution (Python):
import bisect
N,M = map(int,input().split())
A = []
for _ in range(N):
    a,b = map(int,input().split())
    if a<=M: A.append([a,b])
A.sort(reverse=True)
import heapq
h = []
ans = 0
for m in range(1,M+1):
    while A and A[-1][0] == m:
        heapq.heappush(h, A.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)

Solution (Python):
import heapq
n,m = map(int,input().split())
hq = []
ab = []
for i in range(n):
    ab.append([int(_) for _ in input().split()])
ab.sort(key = lambda x:(x[0],-x[1]))
ab.append([m+1,-1])
now = 1
ans = 0
idx = 0
while now <= m:
    while ab[idx][0] <= now:
        heapq.heappush(hq,-ab[idx][1])
        idx += 1
    if hq != []:
        ans -= heapq.heappop(hq)
    now += 1
print(ans)

Solution (Python):
import heapq

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

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

print(ans)

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

import heapq

n, m = map(int, input().split())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))
a.sort()
a.append([m+1, 0])

h = []
ptrA = 0
ans = 0
for i in range(m):
	while a[ptrA][0] <= i + 1:
		heapq.heappush(h, a[ptrA][1] * (-1))
		ptrA += 1
	if len(h) > 0:
		ans += heapq.heappop(h)
print(-ans)

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

Solution (Python):

import heapq

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
jobs = {}
for job in AB:
    if job[0] in jobs:
        jobs[job[0]].append(job[1])
    else:
        jobs[job[0]] = [job[1]]

hq = []
reword_sum = 0
for i in range(1, M + 1):
    if i in jobs:
        for reword in jobs[i]:
            heapq.heappush(hq, -reword)

    if len(hq):
        reword_sum += heapq.heappop(hq)

print(-reword_sum)

Solution (Python):
import sys
import heapq

N, M = list(map(int, input().split()))
possiblyValidJobs = {}
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue

    if A in possiblyValidJobs:
        possiblyValidJobs[A].append(B)
    else:
        possiblyValidJobs[A] = [B]

validJobsOnThisDay = []
ans = 0
for daysBeforeDeadline in range(1, M + 1):
    if daysBeforeDeadline in possiblyValidJobs:
        for wage in possiblyValidJobs[daysBeforeDeadline]:
            heapq.heappush(validJobsOnThisDay, -wage)
    if validJobsOnThisDay:
        ans += -heapq.heappop(validJobsOnThisDay)
print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]

jobs.sort()

money = []
ans = 0

i = 0

for limit in range(1, m + 1):
    
    while i < n and jobs[i][0] <= limit:
        a = jobs[i][0]
        b = jobs[i][1]
        
        heapq.heappush(money, -b)
        i += 1
    
    if money != []:
        ans -= heapq.heappop(money)

print(ans)