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:
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)

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

Submission status: Accepted

Solution code:
import heapq

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

q=[]
ans=0
j=0
for i in range(m):
    while j <= n-1:
        if ab[j][0]<=i+1:
            heapq.heappush(q,-ab[j][1])
        else:
            break
        j+=1
    if len(q)!=0:
        ans-=heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a = [[] for i in range(100000)]
d = []
heapq.heapify(d)

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

#print(a)

ans = 0
for i in range(m):
    for j in range(len(a[i])):
        heapq.heappush(d,a[i][j])
    if d != []:
        ans -= heapq.heappop(d)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a_b_list.sort()
task_list = [0] * (M+1)

heap = []
index = 0
for day in range(1, M+1):
    while index < N:
        if a_b_list[index][0] == day:
            heapq.heappush(heap, a_b_list[index][1] * -1)
            index += 1
        else:
            break
    if len(heap) != 0:
        task_list[day] = heapq.heappop(heap)

#print(task_list)
print(sum(task_list) * -1)


# for a,b in a_b_list:
# #    print(a, b)
#     if task_list[a] == 0:
# #        print("append")
#         task_list[a] = b
#     else:
# #        print("NOT append")
#         index = a + 1
#         while index <= M:
#             if task_list[index] == 0:
#                 task_list[index] = b
#                 break
#             index += 1
# print(sum(task_list))
# #print(task_list)

Submission status: Accepted

Solution code:
#input
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]

#output
import heapq

#点数配列の用意
point = 0
hq = []
#M-i日目(1 <= i <= M)に働ける仕事の中で、Bが最大のものを選ぶ
for A in range(1, M+1):
    if A in jobs:
        for B in jobs[A]:
            heapq.heappush(hq, -B)
    else:
        if len(hq) == 0:
            continue
    point += -heapq.heappop(hq)

print(point)

Submission status: Accepted

Solution code:
import heapq
import sys

h = []
n,m = list(map(int,input().split(" ")))



nums = []
for i in range(n):
    a,b = list(map(int,input().split(" ")))
    nums.append((a,b))
nums.sort(key=lambda x:x[0])

d = 1
ans = 0
st = 0
flag = True
for d in range(1,m+1):
    for i in range(st,n ):
        if nums[i][0] > d:
            st = i
            break
        else:
            if flag:
                heapq.heappush(h,-nums[i][1])
            if st == n-1:
                flag = False

    if h:
        ans -= heapq.heappop(h)


print(ans)

Submission status: Accepted

Solution code:
import heapq

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

c = [[]for i in range(10**5+10)]

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


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

for i in range(m):
    for x in c[i+1]:
        heapq.heappush(h,x)
    if h:
        ans += heapq.heappop(h)

print(-ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Aug 21 23:12:22 2019

@author: Yamazaki Kenichi
"""
import heapq

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

AB.sort()

q = [0 for _ in range(max(M,N))]
j = 0
ans = 0
for i in range(1,M+1):
    while j < N and AB[j][0] == i:
        heapq.heappush(q,-AB[j][1])
        j += 1
    ans += (-heapq.heappop(q))
#    print(i,j,ans,q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
table = [list(map(int, input().split())) for i in range(N)]
table.sort(key=lambda x:x[0])
Q = []
ans = 0
j = 0
for i in range(1,M+1):
  while j <= N-1:
    A, B = table[j]
    if A <= i:
      heappush(Q,-B)
      j += 1
    else:
      break
  if Q:
    ans += -1*heappop(Q)
print(ans)

Submission status: Accepted

Solution code:
import heapq

MAX = 10**5+1
N, M = map(int, input().split())
works = [[] for _ in range(MAX)]
for _ in range(N):
  day, reward = map(int, input().split())
  works[day].append(reward)
hp = []
ans = 0
for day in range(1, M+1):
  if len(works[day]) > 0:
    for reward in works[day]:
      heapq.heappush(hp, -reward)
  if len(hp) > 0:
    ans += -heapq.heappop(hp)
print(ans)

Submission status: Accepted

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
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 heapq
from operator import itemgetter

N,M = map(int,input().split())
AB = []
hq = []
heapq.heapify(hq)
ans = 0

for i in range(N):
    tmpA,tmpB = map(int,input().split())
    if tmpA <= M:
        AB.append([tmpA,tmpB])

AB2 = sorted(AB,key = itemgetter(0))  
maxlen = len(AB2)
last = 0

for i in range(1,M+1):
    for j in range(last,maxlen):
        if AB2[j][0] == i:
            heapq.heappush(hq,-AB2[j][1])

            if j == maxlen -1:
                if len(hq) >= 1:
                    ans += -heapq.heappop(hq)

        else:
            last = j
            if len(hq) >= 1:
                ans += -heapq.heappop(hq)
            break

print(ans)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M= MI()
    works = []
    for _ in range(N):
        date,money = map(int,input().split())
        works.append((-money,date))
    works.sort(key = itemgetter(1),reverse = True)

    ans =0

    pri_queue = []
    for date in range(M):
        while works and works[-1][1] -1 <= date:
            heappush(pri_queue,works.pop())
        if pri_queue:
            ans += -heappop(pri_queue)[0]

    print(ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(reverse=True)
h=[]
# print(ab)
ans=0
for i in range(m):
    while(ab and ab[-1][0]<=i+1):
        heapq.heappush(h,-ab[-1][1])
        ab.pop()
    if h:
        ans-=heapq.heappop(h)
    # print(ab)
    # print(ans)


print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline
n, limit = map(int, input().split())
dic = defaultdict(list)

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

L = []
ans = 0
for i in range(limit+1):
    for val in dic[i]:
        heapq.heappush(L, -val)
    if len(L):
        ans -= heapq.heappop(L)
print(ans)

Submission status: Accepted

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

N, M = map(int,input().split())
work_list = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    work_list[temp[0]].append(temp[1])

sum = 0
works = []

for i in work_list:
    for j in i:
        heappush(works, -1*j)
    if len(works) == 0:
        continue
    sum -= (heappop(works))

print(sum)

Submission status: Accepted

Solution code:
from queue import PriorityQueue
N, M = map(int, input().split())  # N件のアルバイト, M日後までに欲しい

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

for i in range(N):
    a, b = map(int, input().split())
    if a > M:  # M日後にもらえる仕事ならok
        continue
    jobs_list[a].append(b)

pq = PriorityQueue()

ans = 0

for jobs in jobs_list:
    for job in jobs:
        pq.put(-job)  # min-heapであるから、マイナスにして追加する
    if not pq.empty():  # pqに要素があるなら仕事を一つ行う
        ans += -(pq.get())

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

N,M = (int(i) for i in input().split())
a = [0] *N
b = [0] *N
T = []
list = [[] for i in range(M+1)]

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

k = 0
ans = 0
for j in range(1,M+1):
    for i in list[j]:
        heappush(T,-1 * i)
    if T != []:
        ans += -1 * heappop(T)

print(ans)

Submission status: Accepted

Solution code:
from queue import PriorityQueue
N, M = map(int, input().split())  # N件の仕事, M日後までに得られる報酬

jobs = [[] for _ in range(M)]  # 締め切りごとに仕事を格納する二重配列

for i in range(N):  # N件の仕事を見て行く
    a, b = map(int, input().split())
    if a > M:  # a日後にもらえる、そのaが期日のMよりも大きかったらスルー
        continue
    jobs[M-a].append(b)
    # 報酬がもらえるまでに時間がかかる仕事は、小さいindexに格納されていく
    # PriorityQueueに追加するときはjobsの後ろから見ていく

ans = 0
pq = PriorityQueue()

for i in range(M-1, -1, -1):  # jobsの後ろから見ていく
    for b in jobs[i]:
        pq.put(-b)  # min-heapだからマイナスに追加する

    if not pq.empty():
        ans += -(pq.get())

print(ans)

Submission status: Accepted

Solution code:
from queue import PriorityQueue


N, M = map(int, input().split())  # N件の日雇いアルバイト, M日後までに貯めれるお金

jobs = [[] for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())  # a日後に報酬bがもらえる
    if a > M:  # M日後までにもらえない仕事はスルー
        continue
    jobs[M-a].append(b)  # a日後に報酬がもらえるアルバイト一覧が完成していく
    # jobsは後ろのindexの方に、締め切りが近い仕事が溜まっている

pq = PriorityQueue()
ans = 0
for i in range(M-1, -1, -1):  # 後ろから見ていく
    for b in jobs[i]:  # 締め切りが近い仕事一覧
        pq.put(-b)  # pythonのpqは値が小さい方が優先度が高い？
    # 締め切りが近い仕事一覧をpqに追加し終えたあとに、報酬が一番大きいものを選ぶ
    if not pq.empty():  # 空のpqに対して要素を取り出すような指示を出すとエラーが起きてしまう
        ans += -(pq.get())

print(ans)

Submission status: Accepted

Solution code:
from heapq import *

n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n)]
bites = [[] for _ in range(m)]
for a, b in abab :
    if a <= m : bites[a-1].append(-b)
    
ans = 0
board = []
for bite in bites:
    for b in bite : heappush(board, b)
    if board : ans -= heappop(board)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

res = 0
heap = []

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

print(res)

Submission status: Accepted

Solution code:
import heapq

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

a = [0] * n
b = [0] * n
info = [[] for _ in range(m+1)]

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

l = []
count = 0

for j in range(1,m+1):
    for x in info[j]:
        heapq.heappush(l,-x)
    if l != []:
        count += -heapq.heappop(l)

print(count)

Submission status: Accepted

Solution code:
import heapq

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

hq = []

ans = 0
for A in range(1, M+1):
    for B in W[A]:
        heapq.heappush(hq, -B)
    if hq:
        B = heapq.heappop(hq)
        ans -= B
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

hq = []

ans, ct, idx = 0, 0, 0
for A in range(1, M+1):
    for B in W[A]:
        heapq.heappush(hq, -B)
    if hq:
        B = heapq.heappop(hq)
        ans -= B
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
from heapq import heappop, heappush
sys.setrecursionlimit(20000000)
input = sys.stdin.readline


def main():
    n, limit = map(int, input().split())
    
    jobs = defaultdict(deque)

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

    money = 0
    available_jobs = []

    for d in range(1, limit+1):
        if d in jobs:
            for j in jobs[d]:
                heappush(available_jobs, -j)

        if available_jobs:
            money += -heappop(available_jobs)

    print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n,m = map(int,input().split())
jobs = [[] for i in range(100001)]
for i in range(n):
    a1,b1 = map(int,input().split())
    jobs[a1].append(b1)

reward = 0
heapsort = []
for daysLeft in range(1,m+1):
    if len(jobs[daysLeft]) != 0:
        for i in jobs[daysLeft]:
            heappush(heapsort,-i)
    if len(heapsort) > 0:
        reward += -heappop(heapsort)
print(reward)

Submission status: Accepted

Solution code:
# D - Summer Vacation ★
from collections import defaultdict
from heapq import heappush, heappop

_input = list(map(int, input().split()))
n = _input[0]
m = _input[1]
jobs = defaultdict(list)

# かかる日数ごとに報酬をまとめる
for i in range(n):
    a, b = list(map(int, input().split()))
    if a <= m:
        jobs[a].append(b)

# M-1日目、M-2日目…と後ろから順に得られる報酬が多い仕事を割り振っていく
# ※日数制限があったほうが埋めやすいので
reward = 0
heapsort = []
for daysLeft in range(1, m + 1):
    if daysLeft in jobs:
        for b in jobs[daysLeft]:
            heappush(heapsort, -b)
    if len(heapsort) > 0:
        reward += -heappop(heapsort)
print(reward)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
dict = {}
keys = set([])
for i in range(N):
    a, b = map(int, input().split())
    if a in keys:
        dict[a].append(b)
    else:
        keys.add(a)
        dict[a] = [b]


cand = []
cand_num = 0
val = 0
for a in range(1, M + 1):
    # insert values in cand
    if a in keys:
        for b in dict[a]:
            heapq.heappush(cand, (-b, a))
            cand_num += 1

    if cand_num != 0:
        (b_0, a_0)= heapq.heappop(cand)
        cand_num -= 1
        val += -b_0
    else:
        pass

print(val)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, map, range
  readline = stdin.readline
  from heapq import heappush, heappop
  n, m = map(int, readline().split())
  jobs = {}
  for _ in range(n):
    a, b = map(int, readline().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)
main()

Submission status: Accepted

Solution code:
import math

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

jobs = []
for i in range(n):
	day, reward = map(int, input().split())
	if m- day + 1 > 0:
		jobs.append((m - day + 1, reward))

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

def find(i):
	global parent
	while i != parent[i]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i 

def union(x, y):	# small, big
	global parent
	parent_x = find(x)
	parent_y = find(y)
	parent[parent_y] = parent_x

parent = [i for i in range(m+1)]

def job_sequencing(jobs):
	global parent 
	n = len(jobs)

	total_rewards = 0
	for job in jobs:
		available_slot = find(job[0])
		if available_slot > 0:
			union(available_slot-1, available_slot)
			total_rewards += job[1]
	return total_rewards
print(job_sequencing(jobs))

Submission status: Accepted

Solution code:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] == len(self.T):
      return len(self.T)
    if self.T[x] < 0: return x
    k = self.root(self.T[x])
    self.T[x] = k
    return k

  def merge(self, x, y):
    if y >= len(self.T):
      self.T[-1] = len(self.T)
      return True
    a = self.root(x)
    b = self.root(y)
    self.T[a] = b
    return True


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

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

ans = 0
T = Union(M)
for i in range(N):
  if AB[i][0] > M:
    continue
  t = AB[i][0] - 1
  k = T.root(t)
  if t == k:
    ans += AB[i][1]
    T.merge(t, t + 1)
  else:
    t = k
    if t < M:
      ans += AB[i][1]
      T.merge(t, t + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)

n, m = input().split(' ')
N = int(n)
M = int(m)

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

# 報酬がi日後までにもらえるタスクの中(pool)で報酬が最大ものを選んでいく。
# 最大 M-1 回働ける
index = 0
pool = []
rewords = 0
for i in range(M):
    day = i + 1

    while index < N and day >= int(sorted_ab[index][0]):
        heappush(pool, -sorted_ab[index][1])
        index += 1
    # pool の中にある仕事の中から最大の報酬のものを選ぶ
    if pool:
        rewords += -heappop(pool)

print(rewords)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

List = sorted(List, key=lambda x: x[0])

hq = []
acc = 0
i = 0
j = 1
while j<M+1:
    while i<N and List[i][0]==j:
        heappush(hq, -List[i][1])
        i+=1
    if len(hq)>0:
        acc+=heappop(hq)*(-1)
    j+=1

print(acc)

Submission status: Accepted

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

import heapq

def main():  
    N,M=map(int, input().split())
    B=[[] for _ in range(M+1)]
    heapq.heapify(B)
    for i in range(N):
        a,b=map(int, input().split())
        if a > M: continue
        B[a].append(-b)
    max=[]
    heapq.heapify(max)
    ans=0
    for i in range(1, M+1):
        for j in B[i]:
            heapq.heappush(max, j)
        if len(max) != 0:
            ans+=heapq.heappop(max)
    print(-ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# works[i] : M-i日に報酬が得られるリスト
works = [[] for _ in range(10**6)]

for _ in range(N):
    A, B = map(int,input().split())
    # 報酬が得られる日付に応じて格納
    works[A].append(B)

hq = []
ans = 0

for i in range(1,M+1):
    # M-i日から降順に仕事の候補リストを作る
    for w in works[i]:
        # 大きいものから選びたいのでマイナスをかける
        heappush(hq, -w)
    # M-i日の時点で報酬が最大の仕事を選ぶ
    if hq:
        ans += -heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from bisect import bisect
from collections import deque
inf = 10**5


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

ans = 0
hq = []

for i in range(M-1,-1,-1):
    index = bisect(info, [M-i,inf])
    for _ in range(index):
        A, B = info.popleft()
        heappush(hq, -B)
    if hq:
        B = -heappop(hq)
        ans += B

print(ans)

Submission status: Accepted

Solution code:
import heapq
from bisect import bisect_left
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
b = 0
hq = []
ans = 0
for d in range(1, m + 1):
    idx = bisect_left(l, [d + 1, -1])
    for i in range(b, idx):
        heapq.heappush(hq, -l[i][1])
    if hq:
        ans += -heapq.heappop(hq)
    b = idx
print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

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

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
job_list = [[] for _ in range(m)]
for _ in range(n):
    k, v = map(int, input().split())
    if k-1 < m:
        job_list[k-1].append(-v)

q = []
ans = 0
for i in range(m):
    for push_item in job_list[i]:
        heapq.heappush(q, push_item)
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq

# M日後までに得られる報酬
n, m = map(int, input().split())

# A日後に報酬B

task_list = []

for _ in range(n):
    a, b = map(int, input().split())
    task_list.append((a, b))

task_list = sorted(task_list,key=lambda x:x[0])

j = 0
hq = []
ans = 0

for i in range(1, m+1):
    # 残り1, 2, 3, 4...
    while j < n and task_list[j][0] <= i:
        heapq.heappush(hq, -task_list[j][1])
        j += 1
    if len(hq):
        ans += heapq.heappop(hq)

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

task_list = []

for _ in range(n):
  a, b = map(int, input().split())
  task_list.append((a, b))

task_list = sorted(task_list, key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, m+1):
  while j < n and task_list[j][0] <= i:
    heappush(hq, -task_list[j][1])
    j += 1
  if len(hq):
    ans += -heappop(hq)
  
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
l=[[] for i in range(m+1)]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    ab.append(tmp)
    a,b=tmp
    if a<=m:
        l[a].append(b)
import heapq
q=[]
ans=0
for i in range(1,1+m):
    for j in l[i]:
        heapq.heappush(q,-j)
    if q:
        ans-=heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
lst = [[] for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    if a-1 < M:
        lst[a-1].append(-b)
        
total = 0
heap = []

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

jobs = {i:[] for i in range(1, M+1)}


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

ans = 0
heap = []
for day in range(1,M+1):
  lis = jobs[day]
  for pay in lis:
    heappush(heap, -pay)
  if len(heap) != 0:
    ans += -heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
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 len(hq):
    ans += -heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
 
dc = defaultdict(list)
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    dc[a].append(b)

ans = 0
cands = []
for i in range(1,m+1):
    for j in dc[i]:
        heapq.heappush(cands, -j)
    if len(cands) > 0:
        ans += heapq.heappop(cands)*(-1)
    # print("---",cands)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from operator import itemgetter


def main(n, m, works):
    backward = sorted(works, key=itemgetter(0), reverse=True)
    q = []
    score = 0
    for i in range(1, m + 1):
        while backward and backward[-1][0] <= i:
            a, b = backward.pop()
            heappush(q, -b)
            # print(q)
        if q:
            b = -heappop(q)
            score += b

    return score


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

print(main(n, m, works))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
W = [tuple(map(int, input().split())) for i in range(N)]
W.sort()
h = []

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

print(ans)

Submission status: Accepted

Solution code:
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.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)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
l=[[] for i in range(M+1)]
#print(l)
for i in range(N):
  a,b=map(int,input().split())
  if a<=M:
  #print(a,b)
  #print(l[a])
    l[a].append(b)
#print(l)
ans=0
que=[]
for i in range(1,M+1):
  for j in l[i]:
    heapq.heappush(que,-j)
  if len(que)>0:
    #print(i,que)
    ans-=heapq.heappop(que)
    
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

list_work = []
for n in range(N):
  a,b = map(int,input().split())
  list_work.append([a,b])  

list_work.sort(reverse=True)
q = []
ans = 0


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

print(ans)

Submission status: Accepted

Solution code:
#46 ABC137D
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ab=sorted(ab, key=lambda x:x[0])
import heapq
i=0
heap=[]
res=[]
for x in range(1,m+1):
	while(i<n):
		if ab[i][0]==x:
			heapq.heappush(heap,-ab[i][1])
			i+=1
		else:
			break
	if len(heap)>0:
		res.append(heapq.heappop(heap))
print(-sum(res))

Submission status: Accepted

Solution code:
import heapq


def solve(m, work_map):
    days = work_map.keys()
    ans = 0
    priority_queue = []

    for day in range(1, m + 1):
        if day in days:
            for value in work_map[day]:
                heapq.heappush(priority_queue, -value)
        if len(priority_queue):
            value = -heapq.heappop(priority_queue)
            ans += value

    return ans


def main():
    n, m = map(int, input().split())

    work_map = {}
    # time O(N)
    for i in range(n):
        day, value = list(map(int, input().split()))
        if day > m:
            continue
        if day in work_map.keys():
            work_map[day].append(value)
        else:
            work_map[day] = [value]

    ans = solve(m, work_map)
    print(ans)


main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int,input().split())
d = {}
for i in range(n):
    a,b = map(int,input().split())
    if not a in d:
        d[a] = []
    d[a].append(b)
que = []
ans = 0
for i in range(1,m+1):
    if i in d:
        for dx in d[i]:
            heapq.heappush(que,-dx)
    if len(que)>0:
        ans -= heapq.heappop(que)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()

job_dict = defaultdict(lambda: list())
for i in range(N):
    d, r = read_int()
    job_dict[d].append(-r)


hq = []
heapq.heapify(hq)

def solve():
    ans = 0
    for i in range(1, M + 1):
        for j in job_dict[i]:
            heapq.heappush(hq, j)
        if hq:
            ans += - heapq.heappop(hq)
    return ans

if __name__ == "__main__":
    print(solve())