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 sys
from heapq import heappush, heappop
input = sys.stdin.readline

def main():
    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.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ab.sort()

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 *
from collections import defaultdict

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

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)

Solution (Python):
import heapq

n,m=map(int,input().split())
jobs=[[] for _ in range(m)]
for i in range(n):
    d,r=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:
        rewards+=-heapq.heappop(heap)

print(rewards)

Solution (Python):

import heapq

n,m=map(int,raw_input().split())
ab=[]
for i in xrange(n):
 l=map(int,raw_input().split())
 ab.append(l)
ab=sorted(ab,reverse=True)
q=[]
res=0
for i in xrange(1,m+1):
 while ab and ab[-1][0]==i:
  heapq.heappush(q,ab.pop()[1]*(-1))
 if q:
  res-=heapq.heappop(q)
print res

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

X = []

for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        X.append((a,b))


X = sorted(X, key=lambda x:(x[0], x[1]), reverse=True)


q = []
ans = 0
for i in range(1, M + 1):
    while X and X[-1][0] <= i:
        _, b = X.pop()
        heappush(q, -b)
    if q:
        ans -= heappop(q)
        
print(ans)

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

def main():
    N, M = map(int, input().split())
    ab = []
    for i in range(N):
        a, b = map(int, input().split())
        if a <= M:
            ab.append([a, b])
    ab = sorted(ab, key=lambda x: (x[0], x[1]))
    
    q = []
    j = 0
    ans = 0
    for i in range(M):
        
        while j < len(ab):
            a, b = ab[j]
            if a <= i+1:
                heapq.heappush(q, (-b, a))
            else:
                break
            j += 1
        
        if len(q) > 0:
            b, a = heapq.heappop(q)
            
            ans += -b
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
from heapq import *
from collections import defaultdict

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

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)

Solution (Python):
import heapq

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

for i in s:
    if i[0] <= M:
        jobs[i[0]-1].append(-i[1])

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

print(rewards)

Solution (Python):
import heapq

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

for i in s:
    if i[0] <= M:
        jobs[i[0]-1].append(-i[1])

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

print(rewards)

Solution (Python):
from heapq import heappush, heappop

def resolve():
    n, m = map(int, input().split())
    jobs = [[] for _ in range(m+1)]
    for i in range(n):
        days, reward = map(int, input().split())
        if days <= m:
            jobs[days].append(-reward)

    res = 0
    heap = []
    
    for i in range(m+1):
        for j in jobs[i]:
            heappush(heap, j)
        if len(heap) > 0:
            res += -heappop(heap)

    print(res)
resolve()

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

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

lst = [list(map(int, input().split())) for s in range(N)]

dic = defaultdict(list)
for a, b in lst:
    dic[a].append(b)

heap = []
heapify(heap)

r = 0
for i in range(1, M + 1):
    can = dic[i]
    while can:
        heappush(heap, -can.pop(0))

    if len(heap) != 0:
        r += heappop(heap) * (-1)

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:
        reword = heapq.heappop(heap)
        rewords += -reword
print(rewords)

Solution (Python):
import heapq
import sys
from collections import defaultdict

input = sys.stdin.readline
N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Solution (Python):
import heapq

N, M = map(int, input().split())
jobs = [[] for _ in range(M+1)]
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Solution (Python):
import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Solution (Python):

import heapq

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = sorted(ab, key=lambda x:(x[0],-x[1]))
q = []

res = 0
idx = 0
for i in range(1,m+1):
    while idx<n and ab[idx][0]<=i:
        heapq.heappush(q,-ab[idx][1])
        idx += 1

    if len(q)>0:
        res += -q[0]
        heapq.heappop(q)

print(res)

Solution (Python):
from heapq import heappush, heappop
n, m = map(int, input().split())

in_dict = {}
for _ in range(n):
    a, b = map(int, input().split())
    in_dict[a] = in_dict.get(a, [])
    in_dict[a].append(b)

heap = []
res = 0
for m_i in range(1, m + 1):
    for i in in_dict.get(m_i, []):
        heappush(heap, -i)
    if heap:
        res += -heappop(heap)

print(res)

Solution (Python):
import heapq
from collections import defaultdict

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

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

print(ans)

Solution (Python):
from collections import defaultdict
import heapq
def main():
    n,m = map(int,input().split())
    dc = defaultdict(list)
    for _ in range(n):
        a,b = map(int,input().split())
        dc[a].append(-b)
    a = []
    ans = 0
    for i in range(1,m+1):
        for j in dc[i]:
            heapq.heappush(a,j)
        if len(a)==0:
            pass
        else:
            ans += -1 * heapq.heappop(a)
    
    print(ans)
            
    


if __name__ == '__main__':
    main()

Solution (Python):
"""
https://atcoder.jp/contests/abc137/submissions/6808061

heapq構造をうまく使っている
「要素を追加」＆「その要素から最小値を取得」といったものを大規模に早く処理したい場合はこのやり方が基本となりそう
"""

import sys
from heapq import heappush, heappop
 
n, m = list(map(int, input().split()))
works = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > m:
        continue
    works.append((a, b))
 
works.sort(reverse=True) 

q = []
ans = 0
for i in range(1, m + 1):
    
    
    while works and works[-1][0] <= i: 
        _, b = works.pop() 
        heappush(q, -b) 
    
    if q:
        b = -heappop(q) 
        ans += b

print(ans)

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue

Mod = 1000000007




def main(): 
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(N)]
    AB.sort(reverse = True)
    heap = []
    ans = 0
    for i in range(1,M+1):
        while AB and AB[-1][0]<=i:
            heappush(heap,-AB.pop()[1])
        if heap:
            ans -= heappop(heap)
    print(ans)
        
if __name__ == "__main__":
    main() 





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Solution (Python):
import heapq as hq


def solve(n, m, jobs):
    """
    n: jobの数
    m: 期限
    jobs: (期日、報酬)のリスト
    """

    jobs.sort()

    sal = 0
    j = 0
    heap = []
    for d in range(1, m + 1):
        while j < n:
            job = jobs[j]
            if job[0] > d:
                break
            hq.heappush(heap, -job[1])
            j += 1
        
        if len(heap) > 0:
            sal = sal - hq.heappop(heap)
    return sal


n, m = [int(x) for x in input().split()]

jobs = []
for _ in range(n):
    a, b = [int(x) for x in input().split()]
    jobs.append((a, b))

print(solve(n, m, jobs))

Solution (Python):
import sys
from heapq import heappush, heappop
 
n, m = list(map(int, input().split()))


works = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > m:
        continue
    works.append((a, b))
 
works.sort(reverse=True)
 
q = []
ans = 0
for i in range(1, m + 1):
    while works and works[-1][0] <= i:
        a, b = works.pop()
        heappush(q, -b)
    
    if q:
        b = -heappop(q)
        ans += b
print(ans)

Solution (Python):
from operator import itemgetter
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key = itemgetter(0))
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):
from heapq import heappush, heappop
 
N,M = map(int,input().split())

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])
 
reward = 0
Q = []
for i in allhiyatoi:
    for j in i:
        heappush(Q,j*-1)
    if len(Q) == 0:
        continue
    reward -= (heappop(Q))

print(reward)

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

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])
 
reward = 0
Q = []
for i in allhiyatoi:
    for j in i:
        heappush(Q,j*-1)
    if len(Q) == 0:
        continue
    reward -= (heappop(Q))

print(reward)