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:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 優先度付きキュー
# 優先度とフラグを入れ込んだキューで、優先度が大きいものからポップできる
# 優先度が小さいものとする場合は、マイナスでキューにプッシュする
# hp キュー
# hist フラグの履歴（一度読んだものは再度使わない場合）

from heapq import heapify, heappop, heappush, heappushpop

def main():
    N, M = map(int, input().split())
    S = {}
    for i in range(N):
        a,b = map(int,(input().split()))
        if a in S.keys():
            S[a].append((-b,a))
        else:
            S[a]=[(-b,a)]
    hp = []
    heapify(hp)
    ret = 0
    for i in range(1,M+1):
        if i in S:
            for jb in S[i]:
                heappush(hp, jb)
        if len(hp)==0:
            continue
        x = heappop(hp)
        ret += -x[0]
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
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:
    jobs[a].append(b)

pq = []
d = 1
res = 0
for _ in range(M-1, -1, -1):
  for b in jobs[d]:
    heapq.heappush(pq, -b)
  if pq:
    res += -heapq.heappop(pq)
  d += 1

print(res)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
canditates = []
for a in range(1, M+1):
    if a in jobs.keys():
        for b in jobs[a]:
            heapq.heappush(canditates, -b)
    else:
        if not canditates:
            continue
    ans += heapq.heappop(canditates) * (-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = map(int, input().split())
    AB = [[] for _ in range(M)]
    for i in range(N):
        a, b = map(int, input().split())
        if a <= M:
            AB[a - 1].append(b)

    for i in range(M):
        AB[i] = sorted(AB[i])

    # print(AB)

    reward = []
    heapq.heapify(reward)
    ans = 0
    for i in range(M):
        if AB[i]:
            r = (-1) * AB[i].pop(-1)
            heapq.heappush(reward, (r, i))
        if reward:
            r, ind = heapq.heappop(reward)
            ans += (-1) * r
            if AB[ind]:
                r = (-1) * AB[ind].pop(-1)
                heapq.heappush(reward, (r, ind))

    print(ans)


if __name__ == '__main__':
    solve()

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 = []
ans = 0
for i in range(M):
  for b in day[i+1]:
    heapq.heappush(q, b)
  if len(q) > 0:
    ans += -1 * heapq.heappop(q)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
AB = []
for _ in range(N):
    ab = list(map(int, input().split()))
    a,b = ab[0], ab[1]
    AB.append((a,b))
AB.sort()

q = queue.PriorityQueue()
idx = 0
ans = 0
for i in range(1, M+1):
    while True:
        if idx >= N or AB[idx][0] > i:
            break
        b = AB[idx][1]
        q.put((-b, b))
        idx += 1
    if not q.empty():
        ans += q.get()[1]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
from heapq import heapify, heappush, heappushpop


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]

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

    q = []
    heapify(q)

    for i in sorted(dic.keys(), reverse=True):
        for j in sorted(dic[i], reverse=True):
            if len(q) <= m - i:
                heappush(q, j)
            elif q and q[0] < j:
                heappushpop(q, j)

    print(sum(q))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import collections
import heapq
n,m = map(int,raw_input().split(' '))

elems = [map(int, raw_input().split(' ')) for _ in range(n)]
elems.sort(key = lambda x:x[0])
heap = []

j = 0
cumul = 0
for i in range(1,m+1):

	while(j < len(elems) and elems[j][0] <= i): 
		heapq.heappush(heap,-elems[j][1])
		j+=1
	if heap:
		cumul -= heapq.heappop(heap)

print cumul

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 as hp
n,m=map(int,input().split())
AB=[[] for i in range(m+1)]

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

ans=0
l=[]
hp.heapify(l)
for ab in AB:
  for t in ab:
    hp.heappush(l,t)
  if len(l)>0:
    ans-=hp.heappop(l)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

n, m = map(int, input().split())
ans = 0
jobs = defaultdict(list)
to_do = []
heapq.heapify(to_do)
for i in range(n):
    array = list(map(int, input().split()))
    array[1] *= -1
    jobs[array[0]].append(array[1])

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

print(ans)

Submission status: Accepted

Solution code:
 # AtCoder
import heapq
N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        AB[A].append(B)

hp = []
ans = 0

for B in AB:
    for b in B:
        heapq.heappush(hp, (-1)*b)
    if hp:
        ans += heapq.heappop(hp)*(-1)
print(ans)

Submission status: Accepted

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

# 逆順に見ていく
# A_iの値が小さい順にheapqに追加していく

N,M = map(int,readline().split())
from collections import defaultdict
tasks = defaultdict(list)
for i in range(N):
  a,b = map(int,readline().split())
  tasks[a].append(b)
  
import heapq
q = []
heapq.heapify(q)
ans = 0
for i in range(1,M + 1):
  for task in tasks[i]:
    heapq.heappush(q,-task)
  if q:
    t = heapq.heappop(q)
    ans += (-t)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
import heapq

def solve(N: int, M: int, A: "List[int]"):
    a = sorted(A, reverse=False)
    a = deque(a)
    # ai(day) bi(reward)
    b_cands = []
    heapq.heapify(b_cands)

    ans = 0
    for M in range(M+1):
        while (len(a)!=0) and (a[0][0]==M):
            heapq.heappush(b_cands, -a.popleft()[1])
            # print(b_cands)
        if len(b_cands)>0:
            ans -= heapq.heappop(b_cands)

    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = []

    for i in range(N):
        A.append((int(next(tokens)),int(next(tokens))))
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
AB_s = [list(map(int, input().split())) for _ in range(N)]
MAPperA = {i: [] for i in range(1,M+1)}
# 残り日数ごとのマップを作る
for i, AB in enumerate(AB_s):
    if AB[0] in MAPperA:
        MAPperA[AB[0]].append(AB[1])
excutableJobList = []
heapq.heapify(excutableJobList)
answer = 0
# 短期間でできる仕事からリストを作って追加してそーとして最大値を追加していく
for i in range(1,M+1):
    for j in MAPperA[i]:
        heapq.heappush(excutableJobList, j*-1)
    if excutableJobList:
        answer += heapq.heappop(excutableJobList) * -1
print(answer)

Submission status: Accepted

Solution code:
import heapq  # heapqライブラリのimport
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
lsta=[[] for i in range(10**5+1)]
lst=[]
ans=0
for i in range(N):
 A,B=map(int,input().split())
 lsta[A].append(-B)
heapq.heapify(lst)  # リストを優先度付きキューへ
for i in range(1,M+1):
 for j in lsta[i]:
  heapq.heappush(lst, j)
 if lst!=[]:
  ans+=heapq.heappop(lst)
print(-ans)

Submission status: Accepted

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

AB.sort(key=lambda x: x[0])

import heapq
from collections import deque

AB = deque(AB)

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

for i in range(M):
    while len(AB) > 0 and AB[0][0] <= i+1:
        t = AB.popleft()
        heapq.heappush(task,-t[1])
    if len(task) > 0:
        ans += heapq.heappop(task)
print(-ans)

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(reverse=True)
works=[]
heapq.heapify(works)
ans=0
AB=AB+[[0,0]]
for i in range(1,M+1):
  day=M-i
  latest=i
  while len(AB)>=2 and AB[-2][0]<=latest:
    a,b=AB.pop(-2)
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

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(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop(-1)
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

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(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
heapq.heapify(val)
ans=0
c=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        heapq.heappush(val,(-1)*q[1])
        c+=1
    if c>0:
        ans-=heapq.heappop(val)
        c-=1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
pay = sorted([[-int(i) for i in input().split()] for _ in range(n)])

res = 0
pq = []
for i in range(1, m+1):
    while pay and -pay[-1][0] <= i:
        a, b = pay.pop()
        heapq.heappush(pq, b)
    if pq:
        res -= heapq.heappop(pq)

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
z,*q=[0]*50*M
v=[[]for _ in q]
for a,b in t:v[a-1]+=b,
for i in v[:M]:[heappush(q,-j)for j in i];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)]
z,*q=[0]*50*M
v=[[]for _ in q]
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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(N)]
AB.sort(key=lambda x:-x[0])

ans = 0
h = []

for day in range(1, M+1):
	while AB and AB[-1][0] == day:
		heappush(h, -AB.pop()[1])

	if h:
		ans -= heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
dic = {}
for i in range(n):
    ai, bi = map(int, input().split())
    if ai in dic:
        dic[ai].append(bi)
    else:
        dic[ai] = [bi]

for key in dic.keys():
    dic[key] = sorted(dic[key])

ans = 0
hp = []
heapq.heapify(hp)
for i in range(1, m+1):
    if i in dic:
        heapq.heappush(hp, (-dic[i].pop(), i))
    if hp != []:
        maxi = heapq.heappop(hp)
        ans += -maxi[0]
        if dic[maxi[1]] != []:
            heapq.heappush(hp, (-dic[maxi[1]].pop(), maxi[1]))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

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

que = []
ans = 0
for d in range(1, M + 1):
    while AB and AB[-1][0] <= d:
        heappush(que, -AB.pop()[1])
    if que:
        ans += heappop(que)
print(-ans)

Submission status: Accepted

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

n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
#AB.sort(key = lambda x:(-x[0], -x[1]))
AB.sort(reverse=True)
#print(AB)

h = []
import heapq
heapq.heapify(h)
ans = 0
for i in reversed(range(m)):
    while AB:
        a, b = AB.pop()
        if i+a > m:
            AB.append((a, b))
            break
        else:
            heapq.heappush(h, (-b, a))
    #print(i, h)
    if h:
        b, a = heapq.heappop(h)
        b = b*(-1)
        ans += b
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from heapq import *

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

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

pq = []
ans = 0

for i in range(M, -1, -1):
    for v in d[M-i]:
        heappush(pq, -v)
    
    if len(pq)>0:
        ans += -heappop(pq)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappush, heappop


def solve():
    n, m = MI()

    jobs = [[] for _ in range(m)]
    for i in range(n):
        a, b = MI()
        if m-a >= 0:
            jobs[m-a].append(b)

    # print(jobs)
    hp = []
    heapify(hp)
    ans = 0
    for i in range(m-1, -1, -1):
        js = jobs[i]
        for j in js:
            heappush(hp, -j)

        if len(hp) > 0:
            ans += -heappop(hp)
    print(ans)





if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n)]
  grp=[[]for _ in range(m+1)]
  for a,b in ab:
    if a>m:
      continue
    grp[a].append(b)
  for i,grpi in enumerate(grp):
    grpi.sort()
  import heapq
  maxs=[]
  heapq.heapify(maxs)
  ans=0
  for i in range(1,m+1):
    if len(grp[i])>0:
      heapq.heappush(maxs,[-grp[i].pop(),i])
    if len(maxs)>0:
      v,j=heapq.heappop(maxs)
      ans-=v
      if len(grp[j])>0:
        heapq.heappush(maxs,[-grp[j].pop(),j])

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

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
AB=t3(n)

d=defaultdict(list)
for a,b in AB:
    d[a].append(b)

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

Submission status: Accepted

Solution code:
import _heapq as heapq
n, m = [int(i) for i in input().split()]
ab = []
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    ab.append([a, -b])
ab.sort()
j = 0
ans=0
h = []
for i in range(1, m + 1):
    while j<n and ab[j][0] <= i:
        heapq.heappush(h, ab[j][1])
        j += 1
    if h:
        ans += heapq.heappop(h)
print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
N, M = map(int, input().split())
dates = [[] for _ in range(10**5+1)]
for i in range(N):
    x,y = map(int, input().split())
    dates[x].append(y)

h = []
heapify(h)
ans = 0
for i in range(1,M+1):
    for b in dates[i]:
        heappush(h,-b)
    if len(h):
        ans -= heappop(h)
print(ans)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]


AB.sort(reverse=True)

import heapq
hq = []
ans = 0
for i in range(1,M+1):
    # n日 (n : 1-M) 後に受け取れる仕事を優先度つきキューに入れる
    # 高いものを優先的に出したいので負にしておく
    while AB and AB[-1][0] <= i:
        a,b = AB.pop()
        heapq.heappush(hq, -b)
    # 可能な仕事があれば, 一番高い仕事を行う
    #  - 値が負なので減算する
    if hq:
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush as sushi
    from heapq import heappop as tempra
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i - m < 1:
            l[i].append(-j)

    w = []
    h = []
    for i in range(1, m + 1):
        for j in l[i]:
            sushi(h, j)
        if h:
            x = tempra(h)
            w.append(x)

    print(-sum(w))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush as sushi
    from heapq import heappop as tempra
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i <= m:
            l[i].append(-j)

    w = []
    h = []
    for i in range(1, m + 1):
        for j in l[i]:
            sushi(h, j)
        if len(h) > 0:
            x = tempra(h)
            w.append(x)

    print(-sum(w))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import heapq
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i <= m:
            heapq.heappush(l[i], -j)
    
    ans = 0
    h = []
    for i in range(1, m + 1):
        for j in l[i]:
            heapq.heappush(h, j)
        if len(h) > 0:
            x = heapq.heappop(h)
            ans += x

    print(-ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import heapq
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i <= m:
            l[i].append(-j)

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

    print(-ans)


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)]
ab.sort(key = lambda x : x[0])
q = []
heapq.heapify(q)
ind = 0
ans = 0
for i in range(1,m+1):
    ok = True
    while ok:
        if  ind <= n-1 and ab[ind][0] <= i:
            heapq.heappush(q, -1 * ab[ind][1])
            ind += 1
        else:
            ok = False
    if len(q) >= 1:
        ans -= heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
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 # M日の期間を越えるような仕事は請けない
    jobs[a].append(-b)

heap = []
salary = 0

for day in range(1, M + 1):
  for i in jobs[day]:
    heapq.heappush(heap, i)

  if len(heap) > 0:
    salary += abs(heapq.heappop(heap)) # heappopは常に最小のもの(一番絶対値の大きい)を返す

print(salary)

Submission status: Accepted

Solution code:
import heapq


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

Work.sort()
now = 1
Q = []
ans = 0
for day, reward in Work:
    if day > M:
        break
    if now > M:
        break
    if day == now:
        heapq.heappush(Q, -reward)
    else:
        while day - now > 1:
            if len(Q) > 0:
                a = heapq.heappop(Q)
                ans += a
            now += 1
        if len(Q) > 0:
            a = heapq.heappop(Q)
            ans += a
        heapq.heappush(Q, -reward)
        now = day
while M - now >= 0:
    if len(Q) > 0:
        a = heapq.heappop(Q)
        ans += a
    now += 1

print(-ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq



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

    # day日目に選択可能になる選択肢をまとめて管理しておく。
    jobs = [[] for _ in range(M + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        jobs[a].append(b)

    heap = []
    salary = 0

    # M日目から遡っていく。
    for day in range(1, M + 1):
        # 選択可能になる選択肢をエンキュー(取り出す時に最大値が欲しいのでマイナスにする。)
        for i in jobs[day]:
            heapq.heappush(heap, -i)
        # ヒープが空でなければ最も良い選択肢を取得、マイナスを戻す。
        if len(heap) > 0:
            salary += abs(heapq.heappop(heap))

    print(salary)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
def main():
    n,m=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(n)]
    AB.sort(reverse=True)
    H=[]
    ans=0
    for i in range(1,m+1):
        while AB and AB[-1][0]<=i:
            a,b=AB.pop()
            heapq.heappush(H,(-b,a))
        if H:
            bb,aa=heapq.heappop(H)
            ans-=bb
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
Bl=[[] for i in range(10**5+5)]

for i in range(N):
    A,B=nm()
    Bl[A].append(-B)

now=[]
if(Bl[0]!=[]):
    for i in range(len(Bl[0])):
        heapq.heappush(now,Bl[0][i])

ans=0
for i in range(1,M+2):
    if(now!=[]):
        max_val=heapq.heappop(now)
        ans+=max_val
    if(Bl[i]!=[]):
        for j in range(len(Bl[i])):
            heapq.heappush(now,Bl[i][j])

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.buffer.readline
n, m = map(int, input().split())
AB = []
AB = [list(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda x: [-x[0], -x[1]])
ans = 0
kouho = []
for d in range(1, m + 1):
    while AB and AB[-1][0] <= d:
        a, b = AB.pop()
        heappush(kouho, (-b, a))
    if kouho:
        p, q = heappop(kouho)
        ans += -p
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

AB = []

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

AB.sort(reverse=True)

q = []
cnt = 0
for i in range(1, M+1):
    while len(AB) > 0 and AB[-1][0] <= i:
        tmp = AB.pop()
        heapq.heappush(q, -tmp[1])
    if len(q) > 0:
        max_val = -heapq.heappop(q)
        cnt += max_val

print(cnt)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n,m=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    if a>m:continue
    l.append((a,b))

l.sort(reverse=True)

q=[]
ans=0

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
d = []
for _ in range(n):
    a, b = map(int, input().split())
    d.append((m - a, b))
d.sort()
ans = 0
q = []
for i in range(m - 1, -1, -1):
    while d and d[-1][0] == i:
        heappush(q, -d.pop()[1])
    if q:
        ans -= heappop(q)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
L=[[] for _ in range(m)]
for _ in range(n):
  a,b=map(int,input().split())
  if a<=m:
    L[m-a].append(b)
s=0
h=[]
for i in range(m-1,-1,-1):
  for l in L[i][::-1]:
    heappush(h,-l)
  if len(h)>0:
    s-=heappop(h)
print(s)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import heapq

readline = stdin.buffer.readline

INF = 10 ** 10

# M日後まで得られる報酬の合計の最大値
N, M = [int(x) for x in readline().split()]

#Ai日後にBiの金
#AB = [tuple(map(int, readline().split())) for _ in range(N)]

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

for _ in range(N):
    A, B = [int(x) for x in readline().split()]
    if A <= M:
        jobs[A].append(B)

# priority queue
pq = [] 

ans = 0

# i = 1 to M
for i in range(1, M+1):
    for job in jobs[i]:
        heapq.heappush(pq, -job)
    
    if(pq):
        ans += -heapq.heappop(pq)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

Submission status: Accepted

Solution code:
#import bisect
import heapq
from collections import deque
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
heapq.heapify(pys)
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            heapq.heappush(pys,-j)
    if pys:
        sum-=heapq.heappop(pys)

print(sum)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
ma = {}
for _ in range(n):
    a,b = map(int,input().split())
    start = a
    if start<0:
        continue
    if start in ma:
        ma[start].append(-b)
    else:
        ma[start] = [-b]
li = []
heapq.heapify(li)
ans_li = []
#print(li,ma)
for i in range(m):
    if i+1 in ma:
        for m in ma[i+1]:
            heapq.heappush(li, m)
    if len(li)>0:
        tmp = heapq.heappop(li)
        ans_li.append(-tmp)
        #print(tmp)
print(sum(ans_li))

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    d[a-1].append(-b)
cnt = 0
a = []
heapq.heapify(a)
for i in range(m):
    for j in d[i]:
        heapq.heappush(a, j)
    if a:
        cnt += -heapq.heappop(a)
print(cnt)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
num = sorted([list(map(int, input().split())) for i in range(n)], key = lambda x: x[0])

s = []
j = 0
count = 0
heapq.heapify(s)

for i in range(1, m + 1):
  while (j < n and num[j][0] <= i):
    heapq.heappush(s, num[j][1] * (-1))
    j += 1
  if(len(s)):
    count += heapq.heappop(s) * (-1)

print(count)