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:
# D - Summer Vacation

import heapq

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

w = [[0] for _ in range(m+1)] 

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

ans = 0
hq = []
for i in range(1, m+1):
    for j in w[i]:
        heapq.heappush(hq, -j)
    ans += heapq.heappop(hq)

print(ans * -1)

Submission status: Accepted

Solution code:
import heapq

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

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

cnd = []
res = 0

for j in range(1, m + 1):
    for e in lis[j]:
        heapq.heappush(cnd, e)
    if cnd:
        res += -heapq.heappop(cnd)
print(res)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
lis = []
for i in range(m + 1):
    lis.append([])

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

cnd = []
heapq.heapify(cnd)
res = 0

for j in range(1, m + 1):
    for e in lis[j]:
        heapq.heappush(cnd, e)
    if cnd:
        res += -heapq.heappop(cnd)
print(res)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(N):
  a,b=map(int,input().split())
  if a>M:
    continue
  else:
    jobs[M-a].append(b)
ans=0
l=[]
for i in range(M-1,-1,-1):
  for j in jobs[i]:
    heapq.heappush(l,-j)
  if len(l):
    ans+=-heapq.heappop(l)
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
# dp = [0] * (M+1)
# data.sort(key=lambda x:x[1], reverse=True)
#
# N0 = 2 ** M.bit_length()
# seg = [0] * (2*N0)
#
# def seg_set(i,x):
#     i = i + N0- 1
#     seg[i] = x
#     while i > 0:
#         i = (i-1) // 2
#         seg[i] = max(seg[i*2+1],seg[i*2+2])
#
# def seg_query(i):
#     i = i + N0 - 1
#     ret = seg[i]
#     while i ^ (i+1) < i+1:
#         i = (i-2) // 2
#         ret = max(ret,seg[i])
#     return ret
#
# for i in range(M+1):
#     seg_set(i,i)
#
# for a,b in data:
#     if a <= M:
#         i = seg_query(M-a+1)
#         if i > 0:
#             dp[i] = b
#             seg_set(i,0)
# print(sum(dp))
data.sort()
p = 0
q = queue.PriorityQueue()
ans = 0
for i in range(1,M+1):
    while p < N:
        if data[p][0] > i : break
        q.put(-data[p][1])
        p += 1
    if not q.empty():
        ans -= q.get()
print (ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq
n, m = map(int, input().split())
jobs = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[m-a].append(b)
ans = 0
l = []
for i in range(m-1, -1, -1):
    for j in jobs[i]:
        heapq.heappush(l, -j)
    if len(l):
        ans += -heapq.heappop(l)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq

n, m = map(int, readline().split())
ab = [[] for _ in range(10 ** 5 + 1)]
for _ in range(n):
    a, b = map(int, readline().split())
    ab[a - 1].append(-b)
ans = 0
q = []
for mm in range(m):
    while ab[mm]:
        heapq.heappush(q, ab[mm].pop())
    if q:
        ans += heapq.heappop(q)
print(-ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)
data.sort(key=lambda x:x[1], reverse=True)

N0 = 2 ** M.bit_length()
seg = [0] * (2*N0)

def seg_set(i,x):
    i = i + N0- 1
    seg[i] = x
    while i > 0:
        i = (i-1) // 2
        seg[i] = max(seg[i*2+1],seg[i*2+2])

def seg_query(i):
    i = i + N0 - 1
    ret = seg[i]
    while i ^ (i+1) < i+1:
        i = (i-2) // 2
        ret = max(ret,seg[i])
    return ret

for i in range(M+1):
    seg_set(i,i)

for a,b in data:
    if a <= M:
        i = seg_query(M-a+1)
        if i > 0:
            dp[i] = b
            seg_set(i,0)
print(sum(dp))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
job = [[] for _ in range(M+1)]
q = []
for i in range(N):
  a, b = map(int, input().split())
  if(a <= M):
    job[a].append(b)
  
ans = 0
for day in range(M+1):
  for value in job[day]:
    heapq.heappush(q, value*(-1))
  if(len(q) > 0):
    ans += heapq.heappop(q)*(-1)
  
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
M = [[] for _ in range(m + 1)]
q = []
for i in range(n):
    a, b = map(int, input().split())
    if a <= m:
        M[m - a] += [b]
for day in range(m + 1):
    for value in M[day]:
        if len(q) <= day:
            heapq.heappush(q, value)
        else:
            heapq.heappushpop(q, value)
print(sum(q))

Submission status: Accepted

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

ans = 0
queue = []
heapq.heapify(queue)
# (M-1)日後から逆算して考える
for i in range(1, m+1):
    for item in albeits[i]:
        heapq.heappush(queue, -item)
    try:
        ans += -heapq.heappop(queue)
    except:
        pass

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
AB = [[] for _ in range(10**5+10)]
for _ in range(N):
	ta, tb = map(int, input().split())
	AB[ta].append(-tb)

ans = 0
q = []
for i in range(1,M+1):
	while AB[i]:
		heapq.heappush(q, AB[i].pop())

	if q:
		ans += heapq.heappop(q)

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

temp_list = []
for _ in range(m + 1):
    temp_list.append([])
for _ in range(n):
    a, b = [int(x) for x in input().split()]
    if a > m:
        continue
    temp_list[a].append(-b)

h = []
ans = 0
for i in range(1, m + 1):
    for b in temp_list[i]:
        heappush(h, b)

    if len(h) == 0:
        continue
    
    ans -= heappop(h)
print(ans)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

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[M-A].append(B)

pq = []
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    L = sorted([lmi() for _ in range(n)], key=lambda x: x[0], reverse=True)
    # print(L)
    h = []
    ans = 0
    for day in range(1, m+1):
        while len(L) != 0 and L[-1][0] == day:
            latency, money = L.pop()
            heappush(h, [-money, latency])
        # print("{} {}".format(day, h))
        if len(h) != 0:
            minus_money, latency = heappop(h)
            ans += - minus_money
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
#from math import floor, ceil
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
#inf = 10**17
#mod = 10**9 + 7

n,m=MI()
Q=[]
heapify(Q)
ar=[[] for i in range(m)]
for i in range(n):
    a,b=MI()
    if a<=m:
        ar[a-1].append(b)
#print(ar)
ans=0
for i in range(m):
    for j in ar[i]:
        heappush(Q,j*(-1))
    if Q:
        s=heappop(Q)*(-1)
        ans+=s
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a = []
ans = 0

for k in range(m - 1, -1, -1):
    i = m - k - 1
    for j in l[i]:
        heapq.heappush(a, (-1) * j)
    if a:
        ans += heapq.heappop(a) * (-1)
        
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a = []
ans = 0

for i in range(m):
    for j in l[i]:
        heapq.heappush(a, (-1) * j)
    if a:
        ans += heapq.heappop(a) * (-1)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


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[M - a].append(b)

heap = []
for day in range(M + 1):
    for job in jobs[day]:
        if len(heap) <= day:
            heappush(heap, job)
        else:
            heappush(heap, job)
            heappop(heap)

print(sum(heap))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


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[M - a].append(b)

heap = []
for day in range(M + 1):
    for job in jobs[day]:
        if len(heap) < day + 1:
            heappush(heap, job)
        else:
            heappush(heap, job)
            heappop(heap)

print(sum(heap))

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappop, heappush, heapify
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N, M = map(int, readline().split())
  AB = [[int(x) for x in readline().split()] for _ in range(N)]
  #i日で報酬が得られるもののリスト
  days = [[0] for _ in range(M)]
  for ab in AB:
    if ab[0]-1>=M:
      continue
    else:
      days[ab[0]-1].append(ab[1])
  stack = deque(days)
  q = []
  ans = 0
  while stack:
    x = stack.popleft()
    for y in x:
      heappush(q,-y)
    z = heappop(q)
    ans += z
  print(-ans)
  
  
      
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    a,b = map(int, input().split())
    AB.append((a,-b))
AB.sort()

Q = []
ans = 0
i = 0

for day in range(M):
    while i<N and AB[i][0] == day+1:
        heappush(Q, AB[i][1])
        i+=1
    if Q:
        ans -= heappop(Q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    a,b = map(int, input().split())
    if a<=M:
        AB.append((a,-b))
    else:
        N-=1
AB.sort()

Q = []
heapify(Q)
ans = 0
i = 0

for day in range(M):
    while i<N and AB[i][0] == day+1:
        heappush(Q, AB[i][1])
        i+=1
    if Q:
        ans -= heappop(Q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    a,b = map(int, input().split())
    if a<=M:
        AB.append((a,-b))
    else:
        N-=1
AB.sort()

Q = []
ans = 0
i = 0

for day in range(M):
    while i<N and AB[i][0] == day+1:
        heappush(Q, AB[i][1])
        i+=1
    if Q:
        ans -= heappop(Q)
print(ans)

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())
    A = M - A
    D[A].append(B)

h = []

su = 0
hlen = 0
for i in range(M-1,-1,-1):
    for b in D[i]:
        heapq.heappush(h,-b)
        hlen += 1
    if hlen:
        su -= heapq.heappop(h)
        hlen -= 1

print(su)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template

N,M = inputlist()
li = []
for i in range(N):
    A,B = inputlist()
    B *= -1
    li.append([A,B])
ans = 0
from heapq import *
li.sort()
k = []
heapify(k)
flag = 0
for i in range(1,M+1):
    if flag == N:
        for t in range(M+1-i):
            ans -= heappop(k)
        break
    while li[flag][0] <= i:
        heappush(k,li[flag][1])
        flag = flag + 1
        if flag == N:
            break
    if len(k)>=1:
        ans -= heappop(k)
print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template

N,M = inputlist()
li = []
for i in range(N):
    A,B = inputlist()
    B *= -1
    li.append([A,B])
ans = 0
from heapq import *
li.sort()
k = []
heapify(k)
flag = 0
for i in range(1,M+1):
    if flag == N:
        for i in range(M+1-i):
            ans -= heappop(k)
        break
    while li[flag][0] <= i:
        heappush(k,li[flag][1])
        flag = flag + 1
        if flag == N:
            break
    if len(k)>=1:
        ans -= heappop(k)
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,-b))
ab.sort()
ans = 0
idx = 0
q = []
for i in range(1,m+1):
    while idx<n and ab[idx][0] ==i:
        a,mb = ab[idx]
        hq.heappush(q,mb)
        idx+=1
    if q!=[]:
        ans += -1*hq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,-b))
ab.sort() #日が短い順に
ans = 0
idx = 0
q = []
for i in range(1,m+1):
    while idx<n and ab[idx][0] ==i:
        a,mb = ab[idx]
        hq.heappush(q,mb)
        idx+=1
    if q!=[]:
        ans += -1*hq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq
import queue

n,m=map(int,input().split())
L=[]
for inp in range(n):
    a,b=map(int,input().split())
    L.append((a,b))
L.sort(reverse=True)

pq=[]
heapq.heapify(pq)

    
ans=0
for i in range(1,m+1):
    while len(L)>0 and L[-1][0]==i:
        heapq.heappush(pq,L.pop()[1]*-1)
    #print(pq)
    if len(pq)==0:
        continue
    else:    
        ans-=heapq.heappop(pq)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
 
N,M = map(int,input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i],B[i] = map(int,input().split())
AB = [[] for _ in range(M+1)] # A に対する B
for a,b in zip(A,B):
    if a <= M:
        AB[a].append(b)
        
q = []
answer = 0

for day in AB:
    # 制限より短いものからも選べるように全文pushして一番良いものだけpopする
    for pay in day:
        heappush(q,-pay)
    if len(q) > 0:
        answer += -heappop(q)
        
print(answer)

Submission status: Accepted

Solution code:
import heapq

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

AB = sorted(AB)

# 後ろから見て優先度付きキューで取り出す
n = 0
heapq.heapify(kouho)
for i in range(1, M+1):
    if n < N:
        while AB[n][0] <= i:
            heapq.heappush(kouho, AB[n][1] * (-1))
            n += 1
            if n >= N:
                break
    
    if kouho:
        b = heapq.heappop(kouho)
        ans += b*(-1)
    
print(ans)

Submission status: Accepted

Solution code:
jobs, limit = map(int, input().split())
fees = [[] for _ in range(limit)]
for _ in range(jobs):
    day, fee = map(int, input().split())
    if day - 1 < limit:
        fees[day - 1] += [fee]
        
import heapq  # heapqライブラリのimport

res = 0
array = []
for fee_list in fees:
    [heapq.heappush(array, -f) for f in fee_list]
    if len(array) > 0:
        res += -heapq.heappop(array)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
work = [0]*n
for i in range(n):
  work[i] = list(map(int, input().split()))

work.sort()
k = 0
workable = []
heapq.heapify(workable)
ans = 0
for i in range(m):
  while k < n:
    if work[k][0] <= i+1:
      heapq.heappush(workable, -work[k][1])
      k += 1
    else:
      break
  if workable:
    ans += -heapq.heappop(workable)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [[] for _ in range(10**5)]
for i in range(n):
	a,b = map(int,input().split())
	a -= 1
	ab[a].append(b)

import heapq

q = []
heapq.heapify(q)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush
import bisect

N, M = map(int, input().split())
AB = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)])
A = [x for x, y in AB]

hq = []
heapify(hq)

count = 0

for i in range(1, M + 1):
    c_1 = bisect.bisect_left(A, i)
    c_2 = bisect.bisect_right(A, i)
    if c_2 - c_1 != 0:
        for j in range(c_1, c_2):
            heappush(hq, -AB[j][1])
    
    if hq:
        count += -heappop(hq)
    
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import *
n, m = map(int, input().split())
a = sorted([list(map(int, input().split()))for _ in range(n)])
a.append([10**9])
r,j,x=0,0,[]
heapify(x)
for i in range(m):
    while a[j][0]<=i+1:heappush(x,-a[j][1]);j+=1
    if x:r-=heappop(x)
print(r)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a = sorted([list(map(int, input().split())) for _ in range(n)])
r,j,x=0,0,[]
heapq.heapify(x)
for i in range(m):
    while j < n and a[j][0] <= i+1:
        heapq.heappush(x, -a[j][1])
        j += 1
    if x:
        r -= heapq.heappop(x)
print(r)

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()
result, j = 0, 0
x = []
heapq.heapify(x)
for i in range(1, m+1):
    while j < n and ab[j][0] <= i:
        heapq.heappush(x, -ab[j][1])
        j += 1
    if len(x)!=0:
        result -= heapq.heappop(x)
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 02:06:07 2020

@author: Kanaru Sato
"""

import heapq

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

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

##print(albeit)
Heap = [0]
sum = 0
for i in range(m):
    day = i+1
    for money in albeit[day]:
        heapq.heappush(Heap, money)
    if Heap[0] != 0:
        daymax = heapq.heappop(Heap)*-1
        sum += daymax

print(sum)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from heapq import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
3 4
4 3
4 1
2 2
'''

def solve(l,m):
	n = len(l)
	L = [[] for i in range(10**5+1)]
	for i in l:
		d,r = i
		L[d].append(r)
	ans = 0
	hp = []
	for i in range(1,m+1):
		for j in L[i]:
			heappush(hp,-j)
		if(hp):
			ans -= heappop(hp)
	return ans

N,M = list(map(int, stdin.readline().rstrip().split()))
l = []
for _ in range(N):
	a,b = list(map(int, stdin.readline().rstrip().split()))
	l.append([a,b])
ans = solve(l,M)
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
import heapq


def submit():
    n, m = map(int, input().split())
    jobs = defaultdict(list)
    job_q = []

    # jobs[a] : a日後に報酬をもらえる仕事についてヒープ
    for _ in range(n):
        a, b = map(int, input().split())
        heapq.heappush(jobs[a], -b)

    # 1日前~m日前について、えらぶべきjobを選択する
    ans = 0
    for i in range(1, m + 1):
        # print("jobs", jobs)
        # print("jobq", job_q)
        if jobs[i]: # 今日期限の仕事について、最大報酬の仕事を候補に入れる
            heapq.heappush(job_q, (heapq.heappop(jobs[i]), i))
        
        # 仕事の候補がある
        if job_q:
            pay, day = heapq.heappop(job_q)
            ans -= pay
            if jobs[day]: # 仕事をしたことにした日の次のjobを候補に追加
                heapq.heappush(job_q, (heapq.heappop(jobs[day]), day))
    print(ans)
            
            
submit()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, nDays = map(int, input().split())
a = sorted(tuple(map(int, input().split())) for _ in range(n))
ret = 0
pq = []
pos = 0
for day in range(nDays + 1):
    while pos < n and a[pos][0] <= day:
        heappush(pq, -a[pos][1])
        pos += 1
    if pq:
        ret -= heappop(pq)
print(ret)

Submission status: Accepted

Solution code:
import heapq
from heapq import heappush, heappop

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
l = [[] for i in range(10**5)]

for a,b in ab:
    l[a-1].append(-b)
heap = []

ans = 0
for i in range(m):
    for j in l[i]:
        heappush(heap,j)
    if len(heap) == 0:
        continue
    ans += -(heappop(heap))
    
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
work = [[] for i in range(100001)]
for i in range(N):
    A,B = map(int,input().split())
    work[A].append(B)
q = []
ans = 0
heapq.heapify(q)
for m in range(1,M+1):
    #print(work[m])

    for b in work[m]:
        heapq.heappush(q,-b)
    if len(q) != 0:
        s = heapq.heappop(q)
        #print(s)
        ans += -s
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

i = 0
q = []
ret = 0
for d in range(1, m + 1):
    while i < len(ab) and ab[i][0] <= d:
        heapq.heappush(q, -ab[i][1])
        i += 1
    if len(q) > 0:
        ret -= heapq.heappop(q)
print(ret)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

lists=[[] for _ in range(m+1)]
#lists[i]=i日後にお金を得られる時

for _ in range(n):
    a,b=map(int,input().split())
    #a日後に報酬ｂである
    if 1<=a<=m:
        lists[a].append(b)
    else:
        pass
    
import heapq


heap=[]
heapq.heapify(heap)

ans=0

for i in range(1,m+1):
    for some in lists[i]:
        #i日後にお金を手に入れられる
        heapq.heappush(heap,-some)
    if heap:
        x=heapq.heappop(heap)
        x=x*(-1)
        ans+=x
        
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

lists=[[] for _ in range(m+1)]
#lists[i]=i日後にお金を得られる時

for _ in range(n):
    a,b=map(int,input().split())
    #a日後に報酬ｂである
    if 1<=a<=m:
        lists[a].append(b)
    else:
        pass
    
import heapq


heap=[]
heapq.heapify(heap)

ans=0

for i in range(1,m+1):
    for some in lists[i]:
        #i日後にお金を手に入れられる
        heapq.heappush(heap,-some)
    if heap:
        x=heapq.heappop(heap)
        x=x*(-1)
        ans+=x
        
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import math
import io
import sys

n, m = map(int, input().split())
pay = []
for _ in range(n):
    a, b = map(int, input().split())
    pay.append((a, b))
pay = sorted(pay, reverse=True)
q = []
ans = 0
for i in range(1, m+1):
    while pay and pay[-1][0] <= i:
        a, b = pay.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())
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(X)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

A.sort()
K = []
heapq.heapify(K)

j = 0
ans = 0
for i in range(1,M+1):
    if j == N:
        for i in range(M+1-i):
            ans += heapq.heappop(K)*(-1)
        break
    while(A[j][0] <= i):
        heapq.heappush(K, -A[j][1])
        j += 1
        if j == N:
            break
    if len(K) >= 1:
        ans += heapq.heappop(K)*(-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import heapq

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

work = [[] for _ in range(10**5+1)]
for i in range(n):
    ta, tb = map(int, input().split())
    work[ta].append(tb)

total = 0
cand = []

for d in range(1, m+1):
    for w in work[d]:
        #後で最大値を取り出したいので-1倍して追加
        #（複数の要素も一気にpush）
        heapq.heappush(cand, -w) 
        
    if len(cand) > 0:
        #-1倍して最大値として取得
        total += heapq.heappop(cand)*(-1) 
        
print(total)