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=map(int,input().split())
ab=[[0]*2 for _ in range(n)]


for i in range(n):
    ab[i]=list(map(int,input().split()))
ab.sort()
hq=[]
tmp=0
ans=0
for i in range(1,m+1):
    while tmp<n and ab[tmp][0]==i:
        heapq.heappush(hq,-ab[tmp][1])
        tmp+=1
    if hq:
        ans-=heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
ab=[[0]*2 for _ in range(n)]


for i in range(n):
    ab[i]=list(map(int,input().split()))
ab.sort()
hq=[]
tmp=0
ans=0
for i in range(1,m+1):
    while tmp<n and ab[tmp][0]<=i:
        heapq.heappush(hq,-ab[tmp][1])
        tmp+=1
    if hq:
        ans-=heapq.heappop(hq)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    A, B = [[] for i in range(M)], []
    
    for i in range(N):
        a, b = map(int, input().split())
        if a > M: continue
    
        A[a-1].append(-b)
        
    ans = 0
    
    for i in range(M):
        for a in A[i]: heappush(B, a)
        
        if not B: continue
    
        ans += heappop(B)
        
    print(-ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

A = []
for i in range(N):
    a,b = map(int, input().split())
    A.append((-b,a))
A = sorted(A,key=lambda x:(-x[1], -x[0]))
#この時点で、Aは(-報酬,日付)のタプルで、(-報酬)降順→日付降順になっている

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

for i in range(1,M+1):
    while A and A[-1][1]<=i:
        data = A.pop()
        heapq.heappush(H,data)
    if H:
        ans += -(heapq.heappop(H)[0])

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
ans, available = 0, []
heapq.heapify(available)
heapq.heapify(c)
for i in range(1, m+1):
    while len(c)!=0 and c[0][0]<=i:
        now = heapq.heappop(c)
        heapq.heappush(available,-now[1])
    if len(available) != 0:
        ans -= heapq.heappop(available)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(N):
    if AB[i][0]<=M:
        L[AB[i][0]].append(-AB[i][1])

LL=[]
money=0

for i in range(1,M+1):
    for j in L[i]:
        heapq.heappush(LL,j)
    if len(LL)==0:
        continue
    money+=heapq.heappop(LL)

print(-money)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
Data = [[0,0] for _ in range(N)]
for i in range(N):
    a,b = map(int,input().split())
    Data[i][0] = a
    Data[i][1] = b
Data.sort(key=lambda x:x[0])
Heap = []
heapq.heapify(Heap)

ans = 0
idx = 0
for i in range(1,M+1):
    max1 = 0
    maxindex = -1

    while idx < N:
        a = Data[idx][0]
        b = Data[idx][1]
        if a <= i:
            heapq.heappush(Heap,b*(-1))
            idx += 1
        else:
            break
    if len(Heap) > 0:
        max1 = heapq.heappop(Heap)*(-1)
        ans += max1

print(ans)

Submission status: Accepted

Solution code:



import heapq

class job:
    def set_data(self):
        self.time=1
        self.poi=0
    def __lt__(self, other):
        return self.time<other.time


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

j=[]
for _ in range(n):
    a,b=map(int,input().split())
    p=job()
    p.time=a
    p.poi=-b
    j.append(p)
j.sort()
"""
for i in range(n):
    print(j[i].time,j[i].poi)
"""
h=[]
heapq.heapify(h)
pos=0
ans=0
for date in range(m+1):
    while pos<=n-1:
        if pos<=n-1 and j[pos].time==date:
            heapq.heappush(h,j[pos].poi)
            pos+=1
        else:
            break
    if(len(h)>=1):
        ans+=heapq.heappop(h)
   # print(date,ans)
print(ans*(-1))

Submission status: Accepted

Solution code:
import heapq as hq

N,M=map(int,input().split())
wl=[];hq.heapify(wl) # workList
for i in range(N):
    A,B=map(int,input().split())
    hq.heappush(wl,(A,B))

w=[];hq.heapify(w)
ans=0
for i in range(M): # 0日後からM-1日後まで
    while wl and wl[0][0]<=i+1:
        hq.heappush(w,-hq.heappop(wl)[1])
    if w:
        ans+=-hq.heappop(w)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for _ in range(N):
  a, b = map(int, input().split())
  if a <= M:
    AB[a].append(b) # 消化日数に対しての価値
  
#heapq.heapify(a)  # listを優先度付きキューに

q = []
ans = 0
for B in AB:
  for b in B: # 日数：価値
    heappush(q, -b) # 最大値のため、マイナスをかける
  if q:
    ans -= heappop(q) # マイナスの値を戻す
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

q = []
ans = 0
heapq.heapify(q)
for a in range(m):
    for b in jobs[a]:
        heapq.heappush(q,-b)
    if q:
        ans -= heapq.heappop(q)
 
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(n)]

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

q=[]
cnt,ans=m-1,0
while cnt>=0:
  for b in koho[cnt]:
    heapq.heappush(q,-b)
  if len(q)>0:
    ans+=heapq.heappop(q)
  cnt-=1
print(-ans)

Submission status: Accepted

Solution code:
from heapq import *
from collections import defaultdict

N, M = map(int, input().split())
arbeits = defaultdict(list)
for _ in range(N):
    a, b = map(int, input().split())
    arbeits[a].append(b)
heap = []
ans = 0
for i in range(1, M+1):
    for b in arbeits[i]:
        heappush(heap, -b)
    if heap:
        ans += - heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
ab = dict()
for _ in range(N):
    A, B = map(int, input().split())
    ab.setdefault(A, []).append(B)
q = []
ans = 0
for i in range(1, M+1):
    for v in ab.get(i, []):
        heapq.heappush(q, v*(-1))
    if q:
        ans += heapq.heappop(q)*(-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
PJ = [[] for _ in range(M)]
for _ in range(N):
	a,b = map(int, input().split())
	if M-a >= 0:
		PJ[M-a].append(b)

q = []
cnt = M-1
ans = 0
while cnt >= 0:
	for b in PJ[cnt]:
		heapq.heappush(q,-b)
	if len(q) > 0:
		src = heapq.heappop(q)
		ans += src
	cnt -= 1
print(-ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq

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

A = []
for i in range(N):
  X = list(map(int, input().split()))
  A.append([X[0], -X[1]])
  
A = sorted(A, key=itemgetter(0,1), reverse=False)
#print(A)
# days, values(minus, asc)

Q = []
heapq.heapify(Q)
ans = 0
x = 1
i = 0
while x <= M:
  # A0がxである要素をキューに追加
  if i < N and A[i][0] == x:
    heapq.heappush(Q, A[i][1])
    i += 1
    continue
  else:
    # 最小値（マイナスかけて最大）を答えに追加して、1日進める
    if len(Q) > 0:
      ans += heapq.heappop(Q) * (-1)
    x += 1
      
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
from collections import defaultdict

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

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

ans = 0
hq = []
heapify(hq)

for i in range(1, 1+m):
    [heappush(hq, num) for num in ab_dict[i]]
    if hq == []:
        continue
    ans -= heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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:
        pass
    else:
        jobs[m - a].append(b)

if len(jobs) == 0:
    print(0)
    exit(0)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
ans = 0
now = 0
heap = []
for rem in range(1,m+1):
  B = 0
  while now < n:
    a,b = ab[now]
    if a > rem:
      break
    heapq.heappush(heap, (-b))
    now += 1
  if len(heap) > 0:
    B = heapq.heappop(heap)
  ans -= B
print(ans)

Submission status: Accepted

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
from bisect import insort_left as in_l 
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
# import heapq

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] 
    rewards_of_appliable_jobs = []
    for i in range(1, m+1):
        for reward in job_list[i]:
            in_l(rewards_of_appliable_jobs, reward) 
        if rewards_of_appliable_jobs: 
            schedule[i] = rewards_of_appliable_jobs[-1]
            rewards_of_appliable_jobs.pop()

    print(sum(schedule))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
import heapq

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] # 当日は報酬0
    q = []
    for i in range(1, m+1):
        for reward in job_list[i]: # 期限i日前にできる仕事の報酬一覧をheqp queueに入れる
            heapq.heappush(q, -reward) 
            # あとで最大値を取り出すために-1かける(heappop()で取り出せるのは最小値)

        if q: # その日できる仕事が一つでもあれば
            # 報酬の最小値(マイナスなので元々の最大値)を取り出して-1をかけ、scheduleにいれる
            schedule[i] = -heapq.heappop(q) # 戻り値を返すと同時にsheduleにいれた報酬値はqから除いている
        else: # できる仕事がなければ
            pass  # その日の報酬は0のまま

    print(sum(schedule))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
import heapq

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] # 当日は報酬0
    q = []
    for i in range(1, m+1):
        for reward in job_list[i]: # 期限i日前にできる仕事の報酬一覧をheqp queueに入れる
            heapq.heappush(q, -reward) 
            # あとで最大値を取り出すために-1かける(heappop()で取り出せるのは最小値)

        if q: # その日できる仕事が一つでもあれば
            # 報酬の最小値(マイナスなので元々の最大値)を取り出して-1をかけ、scheduleにいれる
            schedule[i] = -heapq.heappop(q) # 戻り値を返すと同時にq自体も変更している
        else: # できる仕事がなければ
            pass  # その日の報酬は0のまま

    print(sum(schedule))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 
import heapq

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, list()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)
    
    schedule = [0 for _ in range(m+1)] # 当日は報酬0
    q = []
    for i in range(1, m+1):
        for reward in job_list[i]: # 期限i日前にできる仕事の報酬一覧をheqp queueに入れる
            heapq.heappush(q, -reward) 
            # あとで最大値を取り出すために-1かける(heappop()で取り出せるのは最小値)

        if q: # その日できる仕事が一つでもあれば
            # 報酬の最小値(マイナスなので元々の最大値)を取り出して-1をかけ、scheduleにいれる
            schedule[i] = -heapq.heappop(q) # 戻り値を返すと同時にq自体も変更している
        else: # できる仕事がなければ
            pass  # その日の報酬は0のまま

    print(sum(schedule))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

N,M = [int(i) for i in input().split()]
NM = [[int(i) for i in input().split()] for _ in range(N)]
NM.sort(key=lambda x: x[0])
day, i = 1,0
heapL = []
total = 0
heapq.heapify(heapL)

while day <= M:
    while i != N and day == NM[i][0]:
        heapq.heappush(heapL, -NM[i][1])
        i += 1
        
        if i == N:
            break
    
    if heapL:
        total += (-1)*heapq.heappop(heapL)
    
    day += 1
    
print(total)

Submission status: Accepted

Solution code:
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n, m = map(int, input().split(' '))
income = []
for i in range(10**5+1):
  income.append([])
ans = 0

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

# print(n, m)
# print(income)

# tmp = sorted(income, key=lambda x: x[0], reverse=True)
# sorted_income = sorted(tmp, key=lambda x: x[1], reverse=True)

# print(sorted_income)

heap = []
for i in range(1, m+1):
  values = income[i]
  for j in range(len(values)):
    _heappush_max(heap, values[j])
  
  if len(heap) < 1:
    continue
  
  max_value = _heappop_max(heap)
  if max_value:
    ans += max_value
  # print(ans)
  

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

res = 0
tmp = []
for day in range(1, m + 1):
	if day in jobs:
		for b in jobs[day]:
			heappush(tmp, -b)
	else:
		if len(tmp) == 0:
			continue
	res -= heappop(tmp)

print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)

Submission status: Accepted

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

import heapq
import bisect

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

ab = [[int(i) for i in input().split()] for j in range(n)]

ab.sort()

a_li = [-1] * n
b_li = [-1] * n

for i in range(n):
    a_li[i] = ab[i][0]
    b_li[i] = ab[i][1]

kouho = []
bfr_idx = 0
ans = 0

for i in range(m):
    day = i + 1
    idx = bisect.bisect_right(a_li,day)
    for j in range(idx-bfr_idx):
        heapq.heappush(kouho,-b_li[bfr_idx+j])
    bfr_idx = idx
    if len(kouho) != 0:
        ans += -heapq.heappop(kouho)

print(ans)

Submission status: Accepted

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

# 入力
N, M = map(int, readline().split())
day_money = [list(map(int, readline().split())) for _ in range(N)]

# 給与支払日までの日数を基準に昇順に並び変える
day_money.sort()

part = []   # 対象日時点で可能な仕事を格納する
count = 0   # どの仕事候補までみたか
out = 0     # 最終的な収入

# 期限までの日数が短い日から順に、その日の仕事を決めていく
for restday in range(1, M + 1):
    while True:
        # 仕事候補を全て見終わっていたら処理を抜ける
        if count >= N:
            break
        # 対象日時点で可能になった仕事を仕事可能リストに追加（partに報酬額を降順で追加）
        if day_money[count][0] == restday:
            heapq.heappush(part, -day_money[count][1])
            count += 1
        else:
            break
    
    # 対象日時点で可能な仕事があれば、一番大きい報酬額の仕事を実施
    if len(part) > 0:
        out += (-heapq.heappop(part))

print(out)

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(key=lambda x: x[0])

    H = []
    I = 0
    ans = 0
    for m in range(M):
        for i in range(I, N):
            if AB[i][0] <= m+1:
                heapq.heappush(H, -AB[i][1])
                I += 1
            else:
                break
        if H:
            ans += -heapq.heappop(H)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
work_list = [[] for m in range(M + 1)]
for n in range(N):
    a, b = map(int, input().split())
    if a <= M:
        work_list[a].append(-b)

Q = [0 for m in range(M)]
ans = 0
for m in range(1, M+1):
    for work in work_list[m]:
        heapq.heappush(Q, work)
    ans += heapq.heappop(Q)

print(-ans)

Submission status: Accepted

Solution code:
#heap
import heapq
n,m = map(int, input().split( ))
J=[]
for _ in range(n):
    ai,bi =map(int,input().split( ))
    J.append((-bi,ai))###

J.sort(key = lambda x:x[1])###
J.append((0,2*m))
day_rev = 1
i = 0
lim = []
ans = 0
while day_rev<=m:
    while J[i][1]<=day_rev:
        heapq.heappush(lim,J[i])
        i+=1
    if lim:
        ch = heapq.heappop(lim)
        ans -= ch[0]
    day_rev+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import math

# 最大のなにか、最小の何かを取り出すときに
n, m = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(n)]
work = sorted(work, key = lambda x:x[0])
hq = []
counter = 0
ans = 0
for i in range(1,m+1):
    while counter < n and work[counter][0] <= i:
        heappush(hq, -1*work[counter][1])
        counter += 1
    try:
        ans -= heappop(hq)
    except:
        continue
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from heapq import heappop,heappush
    n,m=map(int,input().split())
    A=[[] for _ in range(m)]
    for _ in range(n):
        a,b=map(int,input().split())
        if(a>m): continue
        a-=1
        heappush(A[a],(-b,a))
    Q=[]
    res=0
    for i in range(m):
        if(A[i]):
            x=heappop(A[i])
            heappush(Q,x)
        if(Q):
            b,a=heappop(Q)
            res-=b
            if(A[a]):
                x=heappop(A[a])
                heappush(Q,x)
    print(res)
resolve()

Submission status: Accepted

Solution code:
import heapq

n ,m = map(int,input().split())
li = []
for i in range(n):
    x, y= map(int,input().split())
    li.append([x,y])
li.sort()
heap = []

ans = 0
j = 0
for i in range(1, m + 1):
    while j < n and li[j][0] <= i:
        heapq.heappush(heap,-li[j][1])
        j += 1
    if heap:
        ans += -heapq.heappop(heap)
 
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
import sys

input = sys.stdin.readline

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

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

ans = 0
hq = []
heapq.heapify(hq)
    
for i in range(1, M+1):
    [heapq.heappush(hq, num) for num in ab_dict[i]]
    if hq == []:continue
    ans -= heapq.heappop(hq)
    
print(ans)

Submission status: Accepted

Solution code:
import 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:
# coding: utf-8
# Your code here!

import heapq
from collections import defaultdict
baito = defaultdict(list)
n,m = map(int,input().split())

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

ans = 0
sl = []
heapq.heapify(sl)
for a in range(m):
    for b in baito[a]:
        heapq.heappush(sl, -b)
    if len(sl) > 0:
        ans -= heapq.heappop(sl)
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
X = []
for _ in range(N):
    a, b = map(int, input().split())
    X.append((a, b))
X = sorted(X)

i = 0
j = 1
H = []
hpush = lambda x: heappush(H, -x)
hpop = lambda: -heappop(H)

ans = 0
for j in range(M+1):
    while i < len(X) and X[i][0] <= j:
        hpush(X[i][1])
        i += 1
    if H: ans += hpop()

print(ans)

Submission status: Accepted

Solution code:
L=lambda:list(map(int,input().split()));n,m=L();t=sorted([L()for _ in range(n)]+[[float("inf")]]);import heapq as q;h=[];a=j=0
for i in range(t[0][0],m+1):
  while t[j][0]==i:q.heappush(h,-t[j][1]);j+=1
  if h:a-=q.heappop(h)
print(a)

Submission status: Accepted

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

ans=0
q=[]
for i in range(1,m+1):
    for v in c[i]:
        heapq.heappush(q,v)
    if q:
        ans-=heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
def solve():
    N, M = list(map(int, input().split()))
    plan = []
    for _ in range(N):
        plan.append(list(map(int, input().split())))
    task = {}
    for p in plan:
      if p[0] in task.keys():
        task[p[0]].append(-p[1])
      else:
        task[p[0]] = [-p[1]]
    choices = []
    res = 0
    d = task.keys()
    for day in range(1, M+1):
        if day in d:
            for j in task[day]:
                hq.heappush(choices, j)
        if len(choices) > 0:
            res += - hq.heappop(choices)
    print(res)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))

n, m = MAP()
bef = []
for i in range(n):
    a, b = MAP()
    bef.append([a, b])
candi = []
res = 0
heapq.heapify(bef)
heapq.heapify(candi)

for i in range(m):
    while True:
        if len(bef) == 0:
            break
        temp = heapq.heappop(bef)
        if temp[0] > i+1:
            heapq.heappush(bef, temp)
            break
        heapq.heappush(candi, temp[1] * -1)
    if len(candi) != 0:
        res += heapq.heappop(candi)*-1

print(res)

Submission status: Accepted

Solution code:
import heapq as h
n,m=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x:x[0])
hq=[]
x=0;d=0
for i in range(1,m+1):
  while d<n and a[d][0]<=i:
    h.heappush(hq,-a[d][1])
    d+=1
  if len(hq):
    x+=-h.heappop(hq)
print(x)

Submission status: Accepted

Solution code:
N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
import heapq
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(-b)
    
def add(q_,add_):
    for i in range(len(add_)):
        heapq.heappush(q_,add_[i])

def kouho(A,B,M):
    kouho_list = [[] for i in range(M+1)]
    for i in range(len(A)):
        if(A[i]<=M):
            kouho_list[A[i]].append(B[i])
    return kouho_list

q = []
heapq.heapify(q)
sum_money = 0

kouho_list = kouho(A,B,M)
for m in range(1,M+1):
    kouho_ = kouho_list[m]
    add(q,kouho_)
    #print(q)
    if(len(q)>0):
        sum_money += -heapq.heappop(q)
print(sum_money)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N,M = map(int,input().split())
jobs = sorted((tuple(map(int,input().split())) for _ in range(N)), reverse=True)

def it():
    q = []
    for d in range(1,M+1):
        while jobs and jobs[-1][0] <= d:
            a,b = jobs.pop()
            heappush(q, -b)
        if q:
            yield -heappop(q)

print(sum(it()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from operator import itemgetter
from heapq import heappop,heappush

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    kyuujinn = [[] for _ in range(M+1)]
    
    for i in range(N):
        if A[i] <= M:
            kyuujinn[A[i]].append(B[i])

    answer =0
    heapque = []
    for k in kyuujinn:
        if k:
            for kk in k:
                heappush(heapque,-kk)
        
        if heapque:
            work = heappop(heapque)
            answer-= work
    print(answer)
    
    return


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 = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
job ={}
for _ in range(N):
  a, b = map(int, input().split())
  job.setdefault(a, []).append(-1*b)
reward = 0
import heapq
joblist =[]
for i in range(M):
  try:
    job_temp=job[i+1]
    for i in range(len(job_temp)):
      heapq.heappush(joblist, job_temp[i])
  except KeyError:
    pass
  try:
    choice = heapq.heappop(joblist)
  except IndexError:
    choice = 0
  reward += choice
print(-1*reward)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
ab = [list(map(int,input().split())) for i in range(N)]
ab = sorted(ab, key = lambda x:x[0])
tgt = []
heapq.heapify(tgt)
count = 0
profit = 0
for m in range(M-1,-1,-1):
    for i in range(count, len(ab)):
        if ab[i][0] == M-m:
            heapq.heappush(tgt, -ab[i][1])
            count += 1
        else:
            break
    if len(tgt) != 0:
        getval = -heapq.heappop(tgt)
        profit += getval
print(profit)

Submission status: Accepted

Solution code:
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, M = LI()
AB = [[] for i in range(N)]
ABm = [[] for _ in range(M+1)]
for i in range(N):
    AB[i] = LI()
    if AB[i][0]<=M:
        ABm[AB[i][0]].append(AB[i][1])
#AB.sort(key=lambda x: x[1],reverse = True)
#print(ABm)
ans = []
cou = []
heapq.heapify(cou)
loop = M
for i in range(loop):
    for j in ABm[i+1]:
        heapq.heappush(cou, -j)
#    print(cou)
    if cou:
        ans.append(heapq.heappop(cou)*(-1))

#print(ans)
if ans:
    print(sum(ans))
else:
    print(0)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
l=[[] for _ in range(m)]
for _ in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(b)
ans=0
w=[]
for i in range(m):
  for j in l[i]:
    heapq.heappush(w,-j)
  if w!=[]:
    ans-=heapq.heappop(w)
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 = sorted(AB,key=lambda x:x[0])
dp = [0 for _ in range(M)]
p = 0
q = []
for a,b in AB:
    n = a-1
    if n > M-1:
        break
    if n != p:
        while q and p < n:
            dp[p] = heapq.heappop(q)
            p += 1
        p = n
    heapq.heappush(q,b*(-1))
while q and p < M:
    dp[p] = heapq.heappop(q)
    p += 1
print(sum(dp)*(-1))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
a.sort()
x=[1 for i in range(m)]
ans=0
q=[]
cnt=0
for i in range(1,m+1):
    for j in range(cnt,n):
        if a[j][0]==i:
            heapq.heappush(q,-a[j][1])
            cnt+=1
        else:
            break
 
    if len(q)!=0:
        ans+=-heapq.heappop(q)
        
            

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ab.sort(reverse=True)
    ls = []
    heapq.heapify(ls)
    t = 0
    for i in range(1, m + 1):
        while True:
            if len(ab) != 0:
                if ab[-1][0] <= i:
                    heapq.heappush(ls, -ab.pop()[1])
                else:
                    break
            else:
                break
        if len(ls) != 0:
            t -= heapq.heappop(ls)
    print(t)


if __name__ == '__main__':
    solve()