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



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-

import heapq

def main2():
    n,m=map(int,input().split())
    jobs_list=[list(map(int,input().split())) for _ in range(n)]
    #breakするタイミングを作るため、Mより大きい値の仕事を作成
    banpei_list=[[i,0] for i in range(1,m+2)]
    #リストの統合
    jobs_list.extend(banpei_list)
    jobs_list=sorted(jobs_list)
    ans=0
    index=0
    que=[]
    while 1:
        day,pay=jobs_list[index]
        #dayがMを超えていればbreak
        if day>m:
            break
        #同じdayのデータが次にもあれば-1倍してheapにpush
        if day==jobs_list[index+1][0]: 
            heapq.heappush(que,-pay)
        #仕事の報酬の最大値を答えに加える
        #前の日のデータからも報酬が良い仕事は選べるようにqueにデータは貯めておく
        else:
            heapq.heappush(que,-pay)
            ans-=heapq.heappop(que)
        index+=1
    print(ans)

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
N, M = list(map(int, input().split()))
A = [0]*N
B = [0]*N
# 日数別にもらえる額を管理
# money = defaultdict(list)
keys = list(range(1, 1+10**5))
# print(keys)
values = [[] for i in range(1, 1+10**5)]
job = dict(zip(keys, values))
for i in range(N):
    a, b = map(int, input().split())
    job[a].append(-b)
    # A[i], B[i] = a, b
# A日後にB円もらえる、M日後に報酬最大化
ans = 0
can_work = []
heapq.heapify(can_work)
for delay in range(1, 1+M):
    for item in job[delay]:
        heapq.heappush(can_work, item)
    # print('delay', delay)
    # print(job)
    if (len(can_work) != 0):
        ans -= heapq.heappop(can_work)

    # for i in range(delay):
    #     print(delay-i)
    #     if len(jpb[delay-i]) != 0:
    #         print('found')
    #         max_money = max(jpb[delay-i])
    #         ans += max_money
    #         jpb[delay-i].remove(max_money)
    #         jpb[delay-i]
    #         break
    #     print('===========')
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ans = 0
import heapq
g = [[] for i in range(100000)]
for i in range(n):
    a,b = map(int,input().split())
    a -= 1
    g[a].append(-b)
for i in range(100000):
    heapq.heapify(g[i])
p = []
heapq.heapify(p)
for i in range(m):
    if len(g[i]) != 0:
        heapq.heappush(p,[heapq.heappop(g[i]),i])
    if len(p) != 0:
        x = heapq.heappop(p)
        ans += -x[0]
        if len(g[x[1]]) != 0:
            heapq.heappush(p,[heapq.heappop(g[x[1]]),x[1]])            
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int, input().split())
lst = []
for i in range(n):
  a,b=map(int, input().split())
  lst.append((-b,a))
lst = sorted(lst, key=lambda x:x[1])

now_idx = 0
queue = []
sum_ = 0
for i in range(1,m+1):
  for j in range(now_idx, n):
    if lst[j][1] <= i:
      heapq.heappush(queue, lst[j])
    else:
      now_idx = j
      break
  else:
    now_idx = n
  if len(queue)>0:
    sum_ -= heapq.heappop(queue)[0]
print(sum_)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
def solve():
    N,M = map(int,input().split())
    day_fee = defaultdict(list)
    for i in range(N):
        a, b = map(int,input().split())
        day_fee[a].append(b)

    fee_heap = []
    heapq.heapify(fee_heap)

    ans = 0
    for day in range(1,M+1):
        for fee in day_fee[day]:
            heapq.heappush(fee_heap, -fee)
        
        if len(fee_heap) != 0:
            ans += -heapq.heappop(fee_heap)
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
d = defaultdict(list)
for i in range(N):
    A, B = map(int, input().split())
    d[A].append(-B)

ans = 0
work = []
for i in range(1, M+1):
    for j in range(len(d[i])):
        heapq.heappush(work, d[i][j])
    if len(work):
        ans -= heapq.heappop(work)
print(ans)

Submission status: Accepted

Solution code:
import heapq # 優先度付きキュー(最小値取り出し)

inf = 10**15
mod = 10**9+7
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort(key = lambda x:x[0], reverse = True)
q = []
heapq.heapify(q)   # ヒープ化
ans = 0
for i in range(1,m+1): # m-i日目からスタートして間に合う仕事
    while ab and ab[-1][0] == i:
        _,val = ab.pop()
        heapq.heappush(q, (-1) * val)
    if q:
        ans += heapq.heappop(q) * (-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
d = defaultdict(list)
for _ in range(N):
    a,b = map(int,input().split())
    d[a].append(b)
Q = [] 
heapify(Q)
s = 0
for i in range(1,M+1):
    li = d[i]
    for k in li:
        heappush(Q,-k)
    if len(Q) == 0:
        continue
    c = heappop(Q)
    s += -c
print(s)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

ABs.sort()

PQ = []
iAB = 0
ans = 0
for rest in range(1, M+1):
    while iAB < N and ABs[iAB][0] <= rest:
        heappush(PQ, -ABs[iAB][1])
        iAB += 1
    if PQ:
        B = -heappop(PQ)
        ans += B

print(ans)

Submission status: Accepted

Solution code:
'''tanon  優先度付きキュー
t(=0 to M-1)日目に仕事を請けることを考えると、Ai>M-tなるiについては、
その仕事を請けるかどうかを考えなくて良い(∵この仕事を請けても、
Ai>M-t⇔Ai+t>Mより報酬はM日目より後にしかもらえません)。
したがって、tを大きい順に見ていくと、
M-1日目にはAi<=1なるiについて、報酬が最大となる仕事iを請けるべき、
M-2日目にはAi<=2なるiについて、まだ請けていない仕事の中で
報酬が最大となる仕事iを請けるべき、
…0日目にはAi<=Mなるiについて、まだ請けていない仕事の中で報酬が
最大となる仕事iを請けるべきであるといえます。
したがって、元の配列をAiの小さい順にソートしておき、
Ai=1の仕事について優先度付きキューに報酬Biを追加し、
優先度付きキューから取ってきた最大値を答えに加え、
次にAi=2の仕事について優先度付きキューに報酬Biを追加し、
優先度付きキューから取ってきた最大値を答えに加え、
…最後にAi=Mの仕事について優先度付きキューに報酬Biを追加し、
優先度付きキューから取ってきた最大値を答えに加えることで、
求める答えが得られます。
'''
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)] 
#すべてのAi=1 to Mについて報酬0の仕事を追加する
#こうすることで、必ずAiに対し、報酬0でも仕事がある⇒空振りがなくなる
arr.extend(arr2)
arr=sorted(arr,key=lambda x:x[0]) #Aiの小さい順にソート
q=[]
ans=0
pos=0
while 1:
 a,b=arr[pos]
 if a>m: #AiがMより大きければその仕事を請ける意味はない
   break
 if a==arr[pos+1][0]: 
  #Aiの値が等しいとき、その仕事を優先度付きキューに追加する
   heapq.heappush(q,-b)#マイナスを付けて、ヒープキューに入れている
 else:
   heapq.heappush(q,-b)
   ans-=heapq.heappop(q)#ヒープキューから最大値を持ってくるのでマイナス
  #Aiの値が変化したとき、そのAiまででの仕事の報酬の最大値を答えに加える
 pos+=1
print(ans)

Submission status: Accepted

Solution code:
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)] #すべてのAi=1 to Mについて報酬0の仕事を追加する
arr.extend(arr2)
arr=sorted(arr,key=lambda x:x[0]) #Aiの小さい順にソート
q=[]
ans=0
pos=0
while 1:
 a,b=arr[pos]
 if a>m: #AiがMより大きければその仕事を請ける意味はない
   break
 if a==arr[pos+1][0]: #Aiの値が等しいとき、その仕事を優先度付きキューに追加する
   heapq.heappush(q,-b)
 else:
   heapq.heappush(q,-b)
   ans-=heapq.heappop(q) #Aiの値が変化したとき、そのAiまででの仕事の報酬の最大値を答えに加える
 pos+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
class HeapQue(object):
    def __init__(self, iterable, max_heap=False):
        self.sign = -1 if max_heap else 1
        sequence = [self.sign * number for number in iterable]
        heapify(sequence)
        self.heapque = sequence

    def push(self, item):
        heappush(self.heapque, item * self.sign)

    def pop(self):
        try:
            return heappop(self.heapque) * self.sign
        except:
            return 0

N, M = map(int, input().split())
jobs = sorted((tuple(map(int, input().split())) for _ in range(N)), key=lambda t: t[0], reverse=True)
q = HeapQue([], max_heap=True)
total = 0
for i in range(1, M + 1):
    while jobs and jobs[-1][0] == i:
        q.push(jobs.pop()[1])
    total += q.pop()
print(total)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
value = [[] for _ in range(10 ** 5 + 1)]

for _ in range(N):
    a, b = map(int, input().split())
    value[a].append(-1 * b)

koho = value[1]
heapq.heapify(koho)

ans = 0
for i in range(1, M + 1):
    if len(koho) > 0:
        ans += -1 * heapq.heappop(koho)
    if i < M:
        for v in value[i + 1]:
            heapq.heappush(koho, v)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
value = [[] for _ in range(10 ** 5 + 1)]

for _ in range(N):
    a, b = map(int, input().split())
    value[a].append(-1 * b)

koho = value[1]
heapq.heapify(koho)

ans = 0
for i in range(1, M + 1):
    if len(koho) > 0:
        ans += -1 * heapq.heappop(koho)
    if i < M:
        for v in value[i + 1]:
            heapq.heappush(koho, v)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    job =[[] for _ in range(m)]
    for i in range(n):
        a,b=map(int,input().split())
        if a-1 < m:
            job[a-1].append(-b) # b:asc, -b:desc
    
    res = 0
    q = []
    from heapq import heappop, heappush
    for i in range(m):
        for j in job[i]:
            heappush(q, j)
        if len(q) > 0:
            res += heappop(q) * -1 # -b -> b
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]
ABs.sort(reverse = True)

works = []
reward = 0
for i in range(1, M+1):
	while ABs and ABs[-1][0] <= i:
		heapq.heappush(works, -ABs.pop()[1])
	if works:
		reward -= heapq.heappop(works)
        
print(reward)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
B = [[] for _ in range(m)]
for i in range(n):
    a,b = map(int,input().split())
    if 1 <= a <= m:
        B[a-1].append(b)
task = []
heapq.heapify(task)
ans = 0
for i in range(m):
    for t in B[i]:
        heapq.heappush(task,-t)
    if task:
        ans += heapq.heappop(task)
print(-ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush 
def main():
    N, M, *m = map(int, read().split())
    tasks = [[] for _ in range(M)]
    for a, b in zip(m[::2], m[1::2]):
        if M-a>=0:
            tasks[M-a].append(b)
    s = 0
    h = []
    for i in [i for i in range(M)][::-1]:
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s-=heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush 
def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    tasks = [[] for _ in range(M)]
    for a, b in zip(m, m):
        if M-a>=0:
            tasks[M-a].append(b)
    s = 0
    h = []
    for i in [i for i in range(M)][::-1]:
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s-=heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush 
def main():
    N, M = map(int, readline().split())
    tasks = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, readline().split())
        if M-a<0:
            continue
        tasks[M-a].append(b)
    s = 0
    h = []
    for i in [i for i in range(M)][::-1]:
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s-=heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush 
def main():
    N, M = map(int, readline().split())
    tasks = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, readline().split())
        if M-a<0:
            continue
        tasks[M-a].append(b)
    s = 0
    h = []
    for i in [i for i in range(M)][::-1]:
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s+=-heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heapify, heappush 
def main():
    N, M = map(int, readline().split())
    tasks = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, readline().split())
        if M-a<0:
            continue
        tasks[M-a].append(b)
    s = 0
    h = []
    for i in [i for i in range(M)][::-1]:
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s+=-heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heapify, heappush 
def main():
    N, M = map(int, readline().split())
    tasks = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, readline().split())
        if M-a<0:
            continue
        tasks[M-a].append(b)
    s = 0
    h = []
    for i in reversed(range(M)):
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s+=-heappop(h)
    print(s)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as hp

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

for i in range( N ):
  a, b = map( int, input().split() )
  if a - 1 < M:
    if L[ a - 1 ] == []:
      L[ a - 1 ] = [ b ]
    else:
      L[ a - 1 ].append( b )
      
ret = 0
C = []
hp.heapify( C )
for i in range( M ):
  for i in L[i]:
    hp.heappush( C, -i)
  if C != []:
    ret -= hp.heappop( C )

print( ret )

Submission status: Accepted

Solution code:
#137-d
import heapq as hp

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

lists=[[] for _ in range(m)]
for i in range(n):
    a,b = [int(i) for i in input().split()]
    if a<=m:
        lists[a-1].append(b)
        
h = []
hp.heapify(h)

ans= 0
for i in range(m):
    for v in lists[i]:
        hp.heappush(h,-v)
    if len(h)>0:
        ans -= hp.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

dic = {}
n, m = map(int, input().split())
for _ in range(n):
  a, b = map(int, input().split())
  if dic.get(a) is not None:
    dic[a].append(-b)
  else:
    dic[a] = [-b,]

ans = 0
bite = []
for i in range(1, m+1):
  if dic.get(i) is not None:
    #bite = bite + dic[i]
    for val in dic[i]:
      heapq.heappush(bite, val)
  if len(bite) > 0:
    #heapq.heapify(bite)
    ans += heapq.heappop(bite)
print(ans*-1)

Submission status: Accepted

Solution code:
import heapq

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

works.sort()
day = 1
ans = 0
candidates = []
for work in works:
    if work[0] == day:
        heapq.heappush(candidates,-work[1])
    else:
        if M < work[0]:
            break
        while day < work[0]:
            if candidates:
                ans += -heapq.heappop(candidates)
            day += 1
        heapq.heappush(candidates,-work[1])

while day <= M:
    if candidates:
        ans += -heapq.heappop(candidates)
    day += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
jobs = [[] for i in range(M)]
count = 0
h = []
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jobs[A-1].append(B*(-1))
heapq.heapify(h)
for i in range(M):
    if jobs[i]:
        for job in jobs[i]:
            heapq.heappush(h,job)
    if h:
        count -= heapq.heappop(h)
print(count)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
A = []
for _ in range(n):
    a,b = mi()
    A.append([a,b])
A.sort()

import heapq
a = []
ima = 0
ans = 0
for i in range(1,m+1):
    while True:
        if ima == n:
            break
        if A[ima][0] <= i:
            heapq.heappush(a,-A[ima][1])
            ima += 1
        else:
            break
    if a:
        ans += heapq.heappop(a)*-1
print(ans)

Submission status: Accepted

Solution code:
from heapq import*
(n,m),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:m]:
  for j in i:heappush(q,-j)
  z-=heappop(q)
print(z)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))

from heapq import heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)

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

Submission status: Accepted

Solution code:
N, M = [int(s) for s in input().split()]
rewards = list(filter(lambda x: x[0] <= M
                , sorted([[int(s) for s in input().split()] for _ in range(N)])))[::-1]

import heapq
a = []
heapq.heapify(a)

sums = 0
for day in reversed(range(M)):
    while(rewards):
        if M-day >= rewards[-1][0]:
            r = rewards.pop()
            heapq.heappush(a, -1 * r[1])
        else:
            break
    
    if a:
        sums += -1 * heapq.heappop(a)

print(sums)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq

N, M = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(N)]
pairs.sort(key = itemgetter(0))

heap = []
reward = 0
index_of_pairs = 0   
for i in range(1, M+1):
    while index_of_pairs < N and pairs[index_of_pairs][0] <= i:
        heapq.heappush(heap, -pairs[index_of_pairs][1])
        index_of_pairs += 1
    if heap:
        reward -= heapq.heappop(heap)

print(reward)

Submission status: Accepted

Solution code:
#137D
def main():
    import sys
    import heapq as h
    from collections import defaultdict
    N, M = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    D = defaultdict(list)
    for i in range(N):
        D[L[i][0]-1].append(-L[i][1])
    
    #print(D)
    ans = 0
    tmp=[]
    h.heapify(tmp)
    for d in range(M):
        for b in D[d]:
            h.heappush(tmp, b)
        #print(tmp)
        if tmp:
            ans += h.heappop(tmp)
        
    print(-ans)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque


def main():
    N, M = list(map(int, input().split(' ')))
    tasks = list()
    for _ in range(N):
        req_day, reward = list(map(int, input().split(' ')))
        latest_start_day = M - req_day
        tasks.append((-reward, latest_start_day))
    # sort by desc order of latest_start_day
    tasks.sort(key=lambda t: t[1], reverse=True)
    tasks = deque(tasks)
    task_que = []
    neg_reward = 0
    for d in range(M, -1, -1):
        while len(tasks) > 0 and tasks[0][1] >= d:
            heapq.heappush(task_que, tasks.popleft())
        if len(task_que) == 0:
            continue
        # do task first with local max reward
        task = heapq.heappop(task_que)
        neg_reward += task[0]
    print(-neg_reward)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
day = {i+1: [] for i in range(M)}
for a, b in ab:
  if a <= M:
    day[a] += [-b]
q = []
heapq.heapify(q)
pay = 0
for i in range(M):
  for b in day[i+1]:
    heapq.heappush(q, b)
  if len(q) > 0:
    pay += -heapq.heappop(q)

print(pay)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
D = {i+1: [] for i in range(M)}
for _ in range(N):
  A, B = map(int, input().split())
  if A <= M:
    D[A].append(B)
rew = 0
pq = []
for i in range(M):
  for j in D[i+1]:
    heappush(pq, -j)
  if pq != []:
    rew += -heappop(pq)
print(rew)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)
from heapq import heapify,heappop,heappush

def main():
    N,M = map(int,input().split())
    works = [tuple(map(int,input().split())) for _ in range(N)]
    works.sort(key = lambda x:x[0])
    q = []
    ans = 0
    j = 0
    for i in range(M):
        while j < N and works[j][0] <= i + 1:
            heappush(q,-works[j][1])
            j += 1
        if q:
            p = heappop(q)
            ans -= p
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    D = defaultdict(list)
    for i in range(N):
        A, B = map(int, input().split())
        D[A].append(-1 * B)
    R = []
    answer = 0
    for i in range(1, M + 1):
        if len(D[i]) > 0:
            d = D[i]
            for t in d:
                heapq.heappush(R, t)
        if R:
            answer += heapq.heappop(R)

    print(-1 * answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

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


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    d = {i: [] for i in range(M + 1)}
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        d[a].append(b)

    ans = 0
    q = []
    heapq.heapify(q)
    for i in range(M, 0, -1):
        a = M - i + 1
        for b in d[a]:
            heapq.heappush(q, -b)
        if q:
            b = heapq.heappop(q)
            ans += -b

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
task=[[0] for _ in range(m+1)]

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

task=task[::-1]

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

for i in range(m,-1,-1):
    cnt=0
    for j in task[i]:
        heapq.heappush(tmp,-j)
    cnt=heapq.heappop(tmp)
    ans-=cnt
print(ans)

Submission status: Accepted

Solution code:
def main():
    import heapq
    n,m = map(int,input().split())
    jobs = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in jobs.keys():
            jobs[a] = [b]
        else:
            jobs[a] += [b]
    ob = []
    ans = 0
    for i in range(1,m+1):
        if i in jobs.keys():
            for j in range(len(jobs[i])):
                heapq.heappush(ob,-1*jobs[i][j])
        if len(ob)>0:
            ans += heapq.heappop(ob)*-1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
lt=sorted(list(f()) for _ in range(n))[::-1]
from heapq import *
q,s=[],0
for i in range(m):
  while lt and lt[-1][0]<i+2: a,b=lt.pop(); heappush(q,-b)
  if q: s-=heappop(q)
print(s)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m=f()
lt=sorted(tuple(map(int,input().split())) for _ in range(n))[::-1]
from heapq import *
q=[]
s=t=0
while t<m:
  t+=1
  while lt and lt[-1][0]==t:
    a,b=lt.pop()
    heappush(q,-b)
  if q: s-=heappop(q)
print(s)

Submission status: Accepted

Solution code:
import heapq

#N is numbers of BAITO, M is limit of days
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
 
#print(inp)  
 
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)

Submission status: Accepted

Solution code:
import heapq


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

AB.sort()
ans = 0 
q = []
heapq.heapify(q)
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 q:
        p = -heapq.heappop(q)
        ans += p
print(ans)

Submission status: Accepted

Solution code:
# 参考　yy4さん
from heapq import heappush, heappop
import sys    
input = sys.stdin.readline    
n, m = map(int, input().split())
    
vmax = pow(10, 5)
jobs = {i:[] for i in range(1,vmax + 1)}
for _ in range(n):
    a, b = map(int, input().split())
    jobs[a].append(-b)
    

ans =0
hq = []
for i in range(1, m + 1):
    for j in jobs[i]:
        heappush(hq, j)
    if hq:
        v = heappop(hq)
        v *= -1
        ans += v
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N,M=map(int,input().split())
item=[list(map(int,input().split())) for i in range(N)]
item.sort(key=lambda x:x[0])
que=[]
heapify(que)
ans=0
j=0
for i in range(1,M+1):
    while(j<N and item[j][0]<=i):
        heappush(que,-item[j][1])
        j+=1
    if que:
        ans+=-heappop(que)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a-1 < m:
        jobs[a-1].append(-b)

heap = []
ans = 0
for i in range(m):
    for reword in jobs[i]:
        heapq.heappush(heap, reword)
    if len(heap) > 0:
        b = heapq.heappop(heap)
        ans += -b
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
jobs=[]
for i in range(n):
    a,b=map(int,input().split())
    jobs.append((a,-b))
jobs.sort(reverse=True)

import heapq
hp=[]
ans=0
for i in range(1,m+1):
    while jobs and jobs[-1][0]<=i:
        heapq.heappush(hp,jobs.pop()[1])
    if hp:
        ans-=heapq.heappop(hp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *

readline = sys.stdin.readline
N, M = map(int, readline().split())
days = [[] for _ in range(M)]
for _ in range(N):
    a, b = map(int, readline().split())
    if a <= M:
        days[a-1].append(b)
ans = 0
hq = []
heapify(hq)
for day in days:
    for pay in day:
        heappush(hq, -pay)
    if hq:
        ans += -heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop


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

jobs = defaultdict(list)
for _ in range(N):
    A, B = map(int, input().split())
    jobs[A].append(-B)

available_jobs = []
total_pay = 0
for day in range(1, M + 1):
    for pay in jobs[day]:
        heappush(available_jobs, pay)
    if available_jobs:
        total_pay -= heappop(available_jobs)
print(total_pay)

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline

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

ablist=[]
for i in range(N):
  A,B=map(int,input().split())
  ablist.append((A,B))
ablist.sort(reverse=True)
  
hq=[]
answer=0
for i in reversed(range(M)):
  while ablist:
    a,b=ablist[-1]
    if i+a<=M:
      ablist.pop()
      heapq.heappush(hq,((-b,a)))
    else:
      break
  
  if hq:
    mb,a=heapq.heappop(hq)
    answer-=mb
    #print(i,a+i,-mb)
    
print(answer)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
jobs = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    jobs[M-A].append(B)
ans = 0
q = []
heapq.heapify(q)
for i in range(M-1, -1, -1):
    for item in jobs[i]:
        heapq.heappush(q, item * (-1))
    if q:
        ans += heapq.heappop(q) * (-1)
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N,M = map(int,input().split())
l = [[0] for _ in range(M+1)] 
for _ in range(N):
    a, b = map(int, input().split())
    if a<=M:
        l[a].append(b)

ans = 0
h = []

for i in range(1,M+1):
  for j in l[i]:
    heappush(h, -j)
  ans += heappop(h)
ans *= -1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
W=[list(map(int,input().split())) for _ in range(N)]
a=[[i,0] for i in range(1,M+2)]
W.extend(a)
W.sort()
q=[]
ans=0
for i,j in W:
    if i>M+1:
        break
    if j!=0:
        heapq.heappush(q,-j)
    else:
        heapq.heappush(q,-j)
        ans-=heapq.heappop(q)
print(ans)