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
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
for i in range(N):
    llab=list(map(int,input().split()))
    lab.append(llab)
lab.sort(key=lambda ab:ab[0])
hq=[]
ind=0
ans=0
for i in range(M):
    for j in range(ind,N):
        if lab[j][0]==i+1:
            heapq.heappush(hq,-lab[j][1])
        else:
            ind=j
            break
    if hq:
            ans-=heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import heapq

######## Wrapper for Max Heap ############
class MaxHeap:
    def __init__(self, H = []):
        self.heapify(H)

    def heapify(self, H):
        self._neg_heap = [ -a for a in H ] # マイナスをかける
        heapq.heapify( self._neg_heap )

    def push(self, value):
        heapq.heappush(self._neg_heap, -value)

    def pop(self):
        return (-1) * heapq.heappop(self._neg_heap)

    def __len__(self):
        return len(self._neg_heap)

# 入力を取得
N, M = [int(x) for x in input().split()]
AB = [None] * N  # AB[i] = [報酬までの日数, 報酬]
for i in range(N):
    AB[i] = [int(x) for x in input().split()]

AB.sort(key = lambda x: x[0]) # 報酬までの日数でソート

heap = MaxHeap() # 報酬額のMax heap
total = 0
j = 0  # 仕事を指すindex

for i in range(1, M + 1):
    while j < N and (AB[j][0]) <= i:  # i日後までに報酬が得られる仕事について
        heap.push(AB[j][1]) # 報酬額をpush
        j += 1
    if len(heap) > 0:
        total += heap.pop() # 最高額をpop

print(total)

Submission status: Accepted

Solution code:
#鈴木に教わった

import heapq

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

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

for j in range(N):
    if A[j]<=M:
        L[A[j]].append(B[j])   #O(N)

ans=0
rest=[]
for k in range(1,M+1):  #O(M*logN)
    for x in L[k]:
        heapq.heappush(rest,-x)
    if rest:     #restが空だとエラーが起きる
        ans+=-heapq.heappop(rest)

print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():

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

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

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

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
for i in range(N):
    llab=list(map(int,input().split()))
    lab.append(llab)
lab.sort(key=lambda ab:ab[0])
hq=[]
ind=0
ans=0
#print(lab)
#c=0
for i in range(M):
    if hq:
            ans-=heapq.heappop(hq)
    for j in range(ind,N):
        #if f==0:
        #print(i,j,lab[j][0])
        if lab[j][0]==i+1:
            heapq.heappush(hq,-lab[j][1])#
        else:
            ind=j
            #j=N-1#これダメ、抜けられていない
            break
        #c+=1
    #if hq:
    #        ans-=heapq.heappop(hq)
    #print(hq)
#print(c)
if hq:
    ans-=heapq.heappop(hq)
print(ans)
#for i in range(3):
#    i=3
#    print(12345)

Submission status: Accepted

Solution code:
import bisect
 
 
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)
memo = [x for x in range(N)]
ans = 0
for a, b in AB:
    if M < a:
        continue
    Ma = M - a
    i = bisect.bisect_right(memo, Ma)
    if i > 0:
        del memo[i - 1]
        ans += b
print(ans)

Submission status: Accepted

Solution code:
import bisect


N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)
memo = [x for x in range(N)]
ans = 0
for a, b in AB:
    if M < a:
        continue
    Ma = M - a
    i = bisect.bisect_right(memo, Ma)
    if i > 0:
        del memo[i - 1]
        ans += b
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
L = [[int(a) for a in input().split()] for _ in range(N)]

import heapq

L.sort()
h = []
ans = [0]*(M)
i = 0
j = 0
d = 0
while i < M and d < M:
    i += 1
    while j < N and L[j][0] <= i:
        heapq.heappush(h, [-L[j][1], L[j][0]])
        j += 1
    if h:
        temp = heapq.heappop(h)
        ans[i-1] = -temp[0]
    
if N < M:
    ans.sort(reverse=True)
    c = 0
    for i in range(N):
        c += ans[i]
    print(c)
else:
    print(sum(ans))

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.readline
n, m = map(int, input().split())
works = []
dct = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    dct[a].append(-b)

hq = []
res = 0
for i in range(1, m+1):
    for item in dct[i]:
        heappush(hq, item)
    if hq:
        res += heappop(hq)

print(-res)

Submission status: Accepted

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

#list型のdistを初期化 works[key]:{list}になっている
works = defaultdict(list)
for i in range(n):
    a, b = list(map(int, input().split()))
    #a日後にお金が振り込まれる物のlistを作成
    works[a].append(b)
candidate = []
ans = 0
heapq.heapify(candidate)
for i in range(1,m+1):
    for j in works[i]:
        heapq.heappush(candidate, -j)
    if len(candidate) != 0:
        ans += heapq.heappop(candidate)

print(-ans)

Submission status: Accepted

Solution code:
from collections import defaultdict 
import heapq
N,M = map(int, input().split())


"""
最終日から、現在選べるアルバイトの中から最も稼ぎの大きいものから選んでいく
"""
works = defaultdict(list)
for i in range(N):
    a,b = map(int, input().split())
    works[a].append(b)


candidates = []
ans = 0
for i in range(M):
    for money in works[i+1]:
        heapq.heappush(candidates, -money)
    
    if len(candidates) > 0: ans += heapq.heappop(candidates)

print(-ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    n,m = map(int,input().split())
    lb = [[] for _ in range(10**5+5)]
    for _ in range(n):
        a,b = map(int,input().split())
        lb[a].append(b)
    res = 0
    q = []
    heapq.heapify(q)
    for i in range(1,m+1):
        for b in lb[i]:
            heapq.heappush(q,b * (-1))
        if q:
            res += heapq.heappop(q) * (-1)

    print(res)

main()

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,input().split())
lb = [[] for _ in range(10**5+5)]
for _ in range(n):
    a,b = map(int,input().split())
    lb[a].append(b)
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb[i]:
        heapq.heappush(q,b * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]

import heapq
AB_dict = {}
for i in range(M):
    AB_dict[i + 1] = []
for i in range(N):
    if AB[i][0] > M:
        continue
    AB_dict[AB[i][0]].append(-AB[i][1])

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

Submission status: Accepted

Solution code:
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 a < m+1:
    ab[a].append(b)
lst = []
now = 0
ans = 0
heapq.heapify(lst)
for i in range(1,m+1):
  for j in ab[i]:
    heapq.heappush(lst,-j)
  #heapq.heapify(lst)
  if lst:
    ans -= heapq.heappop(lst)
print(ans)

Submission status: Accepted

Solution code:
from functools import cmp_to_key
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()
sum = 0
D = 0
li = []
i = 0
heapq.heapify(li)
for D in range(1,M+1):
    while(True):
        if i >= N:
            break
        if AB[i][0] <= D:
            heapq.heappush(li,-AB[i][1])
            i = i + 1
        else:
            break
    if len(li) > 0:
        sum = sum - heapq.heappop(li)

print(sum)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m=map(int,input().split())
li=[[]for i in range(10**5+1)]
for i in range(n):
    a,b=map(int,input().split())
    li[a].append(b)
li2=[]
#print(li)
ans=0
for i in range(1,m+1):
    for x in li[i]:
        heappush(li2,-x)
    if li2:
        ans+=heappop(li2)
    #print(li2)
   # print(ans)
print(-ans)

Submission status: Accepted

Solution code:
import heapq

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

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

ans = 0
hp = []

for i in range(M):

    for reward in jobs[i]:
        heapq.heappush(hp, reward)

    if len(hp) > 0:
        reward = heapq.heappop(hp)
        ans += -reward

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M = map(int,readline().split())
m = map(int,read().split())
AB = [[] for _ in range(M+1)] # A に対する B
for a,b in zip(m,m):
    if a <= M:
        AB[a].append(b)

"""
・逆再生。最終日から順に、扱える仕事が増えていく。
"""

q = []
answer = 0
for B in AB:
    for b in B:
        heappush(q,-b)
    if q:
        answer -= heappop(q)

print(answer)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
heapq.heapify(tmp)

for rest_days in range(1, M+1):
    for x in income[rest_days]:
        heapq.heappush(tmp, x)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m=map(int,input().split())
li=[[]for i in range(10**5+1)]
for i in range(n):
    a,b=map(int,input().split())
    li[a].append(b)

li2=[]
ans=0
for i in range(1,m+1):
    for x in li[i]:
        heappush(li2,-x)
    if li2:
        ans+=heappop(li2)
print(-ans)

Submission status: Accepted

Solution code:

import heapq

#制約の厳しい方からみていく
#残り1日、残り2日ってかんじでうしろから見ていく
#N件のバイト,M日後までに得られる報酬の最大値
#間に合う日数の中で最大報酬のものを選ぶ
#⇒最大のものを選ぶ⇒優先度付きキュー
N,M = map(int,input().split())
#A日後に報酬B
AB =[]
for i in range(N):
    AB.append(list(map(int,input().split())))

#日数が少ない順でソート
AB = sorted(AB)

ans = 0
count = 0
q=[]

for i in range(1,M+1): #残り日数から考える
    while ( count < N) and (AB[count][0] <= i):
        heapq.heappush(q, (-1) * AB[count][1])
        count += 1
    if len(q):
        ans += (-1) * heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

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

import heapq
Q = []
ABidx = 0
ans = 0

for lastday in range(M + 1):
	while(ABidx < len(AB) and AB[ABidx][0] <= lastday):
		heapq.heappush(Q, -1*AB[ABidx][1])
		ABidx += 1
	if(len(Q) > 0):
		ans += -1 * heapq.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 _ in range(n):
    a, b = map(int, input().split())
    d[a].append(-b)

hq = []
reword = 0

for i in range(1, m + 1):
    if i in d:
        for item in d[i]:
            heapq.heappush(hq, item)
    if hq:
        reword += heapq.heappop(hq)

print(-1 * reword)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

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

    print(ans)

    


main()

Submission status: Accepted

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


def main():
    N, M = [int(x) for x in input().strip().split()]
    w_list = [[int(x) for x in input().strip().split()] for _ in range(N)]
    w_list = sorted(w_list, key=lambda x: (x[0], -x[1]))

    ans = 0
    w_idx = 0
    value_list = []
    for day in range(1, M+1):
        if w_idx < len(w_list):
            while w_list[w_idx][0] == day:
                heapq.heappush(value_list, -w_list[w_idx][1])
                w_idx += 1
                if w_idx >= len(w_list):
                    break
        if len(value_list) > 0:
            ans -= heapq.heappop(value_list)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import exit
from collections import deque
import heapq
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[0])
    income = 0
    jobs = deque(jobs)
    hp = []
    for day in range(m):
        while len(jobs) != 0 and jobs[0][0] <= day + 1:
            job = jobs[0]
            heapq.heappush(hp, - job[1])
            jobs.popleft()
        if hp != []:
            income -= heapq.heappop(hp)
    
    print(income)

Submission status: Accepted

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

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

ans = 0
hq = []

for i in range(M):
    for j in jobs[i]:
        heappush(hq, j)
    if hq:
        ans += -heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())

mem = [[0] for _ in range(10**5+1)]
for _ in range(N):
    a, b = map(int, input().split())
    mem[a].append(-b)

x = mem[1].copy()

ans = 0
for i in range(1, M+1):
    if i == 1:
        heapq.heapify(x)
    else:
        for d in mem[i]:
            heapq.heappush(x, d)

    if len(x) <= 0:
        continue
    ans -= heapq.heappop(x)


print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

for i in range(0, n):
  tmp = list(map(int, (input().split())))
  if tmp[0] > m:
    continue
  else:
    job[tmp[0]].append(-tmp[1])

score = 0
tjob = []
for i in range(1, m+1):
  for j in job[i]:
    heapq.heappush(tjob, j)
  if len(tjob) == 0:
    continue
  else:
    score -= heapq.heappop(tjob)

print (score)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lis = [[] for _ in range(M)]
sum = 0
for i in range(N):
    a,b = map(int,input().split())
    if a-1 < M:
        lis[a-1].append(-b)
import heapq
heap = []
for i in range(M):
    for e in lis[i]:
        heapq.heappush(heap,e)
    if len (heap) > 0:
        tmp = heapq.heappop(heap)
        sum += -tmp


    
print(sum)

Submission status: Accepted

Solution code:
# 優先度付きキュー
from heapq import heappush, heappop

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

jobs = {}
for _ in range(N):
    A, B = map(int, input().split())
    if A in jobs:
        jobs[A].append(B)
    else:
        jobs[A] = [B]

result = 0
candidates = []
for a in range(1, M + 1):
    if a in jobs:
        for b in jobs[a]:
            heappush(candidates, -b)
    else:
        if len(candidates) == 0:
            continue
    result += -heappop(candidates)
print(result)

Submission status: Accepted

Solution code:
# 優先度付きキュー
from sys import exit
from heapq import heappush, heappop

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

jobs = {}
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        exit
    if A in jobs:
        jobs[A].append(B)
    else:
        jobs[A] = [B]

result = 0
candidates = []
for a in range(1, M + 1):
    if a in jobs:
        for b in jobs[a]:
            heappush(candidates, -b)
    else:
        if len(candidates) == 0:
            continue
    result += -heappop(candidates)
print(result)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A_B_list = [ [0] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    else:
        A_B_list[A - 1].append(B)
ans = 0
hq = []
for A_B in A_B_list:
    for B in A_B:
        heapq.heappush(hq, -B)
    ans += -heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  6 07:53:11 2019

@author: avina
"""
from queue import PriorityQueue as Q
n,m = map(int, input().split())
l = []
for i in range(n):
    a,b = map(int, input().split())
    l.append((a,b))
l.sort()
ans = 0
a = Q()
nxt = 0
for i in range(0,m+1):
    while nxt < n and l[nxt][0] == i:
        a.put(-l[nxt][1])
        nxt+=1
    
    if a.qsize() != 0:
        b = a.get()
        ans+=(-1*b)
        #print(b)
        
        
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
# Ai>Mのものは最初から除外
# Aiが最小のものから順に選ぶ

# index = A(day-1), element = B(reword)
schedule = [[] for _ in range(m)]
for _ in range(n):
    day, reword = map(int, input().split())
    if day > m:
        continue
    schedule[day-1].append(reword)

hq = []
sum = 0

for i in range(m):
    while schedule[i]:
        heappush(hq, -schedule[i][-1])
        del schedule[i][-1]

    if hq:
        sum -= heappop(hq)

print(sum)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値とindex(同値があった場合は一番左)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        # 1段目(最下段)の初期化
        for i in range(n2):
            self.index[i+n2] = i
        # 2段目以降の初期化
        for i in range(n2-1, -1, -1):
            # 全部左の子の値に更新
            self.index[i] = self.index[i*2]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[left]:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            else:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            i >>= 1

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = (self.init, -1)
        while l < r:
            if r & 1:
                r -= 1
                res = self.func(s[0], self.tree[r])
                # 左との一致を優先する
                if res == s[0]:
                    pass
                else:
                    s = (self.tree[r], self.index[r])
            if l & 1:
                res = self.func(self.tree[l], s[0])
                # 左との一致を優先する
                if res == self.tree[l]:
                    s = (self.tree[l], self.index[l])
                else:
                    pass
                l += 1
            l >>= 1
            r >>= 1
        return s

N, M = MAP()
# 日数別に報酬の値を格納
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

# indexに日数、値に報酬の値を入れるセグ木
sti = SegTreeIndex(10**5+1, max, -INF)
for i in range(10**5+1):
    # 報酬の値をソート
    days[i].sort()
    if len(days[i]):
        # その日数での最大値でセグ木を更新
        sti.update(i, days[i][-1])

ans = 0
# 制約の厳しい後半から確認していく
for i in range(M-1, -1, -1):
    # 現在日iで間に合う範囲にある報酬の最大値とindexを取得
    val, idx = sti.query(0, M-i+1)
    if val == -INF:
        continue
    ans += val
    # 日数別のリストから今回分を削除
    days[idx].pop(-1)
    # それに合わせてセグ木も更新
    if len(days[idx]):
        sti.update(idx, days[idx][-1])
    else:
        sti.update(idx, -INF)
print(ans)

Submission status: Accepted

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

tab = [[] for _ in range(10 ** 5)]
for Ai, Bi in AB:
    tab[Ai - 1].append(Bi)

import heapq
import bisect

# from end
ans = 0
q = []
for d_left in range(1, M + 1):
    for item in tab[d_left - 1]:
        heapq.heappush(q, -item) # pos -> neg
    if len(q) > 0: 
        ans_tmp = -(heapq.heappop(q)) # neg -> pos
        ans += ans_tmp

print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())

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

sal=0
poss=[]
for i in range(1,M+1):
  for j in ab[i-1]:
    heapq.heappush(poss,-j)
  if len(poss)>0:
    sal+=-heapq.heappop(poss)
    
print(sal)

Submission status: Accepted

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

def solve():
    N, M = map(int, input().split())
    jobs = [[] for _ in range(M)]
    for i in range(N):
        a, b = map(int, input().split())
        if a - 1 < M:
            jobs[a-1].append(-b)
    
    ans = 0
    hq = []
    for i in range(M):
        for job in jobs[i]:
            heapq.heappush(hq, job)
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import heapq

N,M=map(int,input().split())
l=[[0] for _ in range(M)]
ans=[]
count=0

for _ in range(N):
    A,B=map(int,input().split())
    if A>M:
        continue
    else:
        l[A-1].append(B*(-1))

for lis in l:
    for item in lis:
        heapq.heappush(ans,item)
    count-=heapq.heappop(ans)

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
def main():
  N, M = list(map(int, input().split()))
  jobs = [[] for _ in range(M)]
  for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
      jobs[d-1].append(-r)

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

Submission status: Accepted

Solution code:
import heapq
def main():
  N, M = list(map(int, input().split()))
  jobs = [[] for _ in range(M)]
  for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
      jobs[d-1].append(-r)

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

Submission status: Accepted

Solution code:
def main():
    import heapq
    n, m = map(int, input().split(' '))
    df = []
    for _ in range(n):
        x, y = map(int, input().split(' '))
        df.append([x, y])
    df.sort()
    h = []
    result = 0
    counter = 0
    for i in range(1, m+1):
        while counter < len(df) and df[counter][0] <= i:
            heapq.heappush(h, (-1)*df[counter][1])
            counter += 1
        if len(h) == 0:
            continue
        else:
            result -= heapq.heappop(h)
    print(result)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split(' '))
df = []
for _ in range(n):
    x, y = map(int, input().split(' '))
    df.append([x, y])
df.sort()
h = []
result = 0
counter = 0
for i in range(1, m+1):
    while counter < len(df) and df[counter][0] <= i:
        heapq.heappush(h, (-1)*df[counter][1])
        counter += 1
    if len(h) == 0:
        continue
    else:
        result -= heapq.heappop(h)
print(result)

Submission status: Accepted

Solution code:
import heapq
class Heapq :
    def __init__(self, arr, desc=False) :
        if desc :
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
    def pop(self) :
        return heapq.heappop(self.hq) * self.sign
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
    def top(self):
        return self.hq[0] * self.sign
    def size(self):
        return len(self.hq)


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

L = [[] for i in range(10**5+1)]
for a,b in AB :
    L[a].append(b)

q = Heapq([], desc=True)
ans = 0
for i in range(1,M+1) :
    for j in range(len(L[i])) :
        q.push(L[i][j])
    ans += q.pop() if q.size() > 0 else 0
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

n, m = li()
works = []
heap = []
ans = 0

for i in range(n):
    ai, bi = li()
    heappush(works, (ai, bi))

for i in range(1, m+1):
    while works:
        ai, bi = heappop(works)
        if ai > i:
            heappush(works, (ai, bi))
            break
        else:
            heappush(heap, -bi)

    if heap:
        ans += -heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(n)]
l = sorted(l, key=lambda x:x[0], reverse=True)
res = 0
q = []
for i in range(1, m+1):
    while l and l[-1][0] <= i:
        heapq.heappush(q, -1 * l.pop()[1])
    if q:
        res += -1 * heapq.heappop(q)
print(res)

Submission status: Accepted

Solution code:
from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
# 残り何日でのごとの仕事の候補をqに追加していく
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        # -1かけてqに追加
        heappush(q, -jobs.pop(-1)[1])
    if q:
        #　残り何日でごとに、-1かかってるので一番高いお金をもらえる仕事がpopされる
        ans -= heappop(q)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

part.sort()
# print(part)
idx = 0
takable = []
allmoney = 0

for i in range(m):
    if len(part) > idx:
        # print(part[idx])
        while part[idx][0] <= i+1:
            heapq.heappush(takable, part[idx][1])
            # print(takable, 0)
            idx += 1
            if len(part)-1 < idx:
                break
    if len(takable):
        pop = heapq.heappop(takable)
        # print(pop, 1)
        allmoney += pop*-1

print(allmoney)