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:
from heapq import heappush, heappop

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

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

#print(AB)
queue = []
ans = 0
for i in range(M) :
    for j in range(len(AB[i])) :
        heappush(queue, -AB[i][j])

    if len(queue) != 0 :
        ans += -heappop(queue)

print(ans)


'''
ans = 0
#print(AB)
for i in range(1, M + 1) :
    maxIncome = 0
    anker = -1
    for k in ABkeys :
        #print(AB[j][0])
        if k <= i :
            if heappop(AB[k]) > maxIncome :
                maxIncome = AB[j][0]
                anker = k
                #print('A', j, maxIncome)
                continue
        else :
            break
    ans += maxIncome
    if len(AB) == 0 :
        break
    if anker != -1:
        AB[anker].pop(0)
        if len(AB[anker]) == 0 :
            AB.remove


print(ans)
'''
'''
N, M = map(int, input().split())
AB = []
for i in range(N) :
    AB.append(list(map(int, input().split())))

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

ans = 0
#print(AB)
for i in range(1, M + 1) :
    maxIncome = 0
    anker = -1
    for j in range(len(AB)) :
        #print(AB[j][0])
        if AB[j][0] <= i :
            if AB[j][1] > maxIncome :
                maxIncome = AB[j][1]
                anker = j
                #print('A', j, maxIncome)
                continue
        else :
            break
    ans += maxIncome
    if len(AB) == 0 :
        break
    if anker != -1:
        AB.pop(anker)

print(ans)
'''

Submission status: Accepted

Solution code:
import heapq
N,M = [ int(x) for x in input().split()]

AB = [ list(map(int, input().split())) for _ in range(N)]
AB.sort()
result = 0
# sort したABを押し上げるindex
i = 0
memo = []
# 制約のきついM-1日後(余裕日数1日)から数える
for x in range(M-1, -1, -1):
    allaw = M - x
    while i < N:
        ab = AB[i]
        limit, reward = ab
        if limit > allaw:
            # AB は sort してあるので、制約を超えたらそれ以上は見ない
            break
        else:
            # 日数制約を満たした仕事は全て heapq に入れられる
            heapq.heappush(memo, -reward)
            i += 1
    if memo:
        # heapq の特性により自動的に最小のもの（-を掛けているので最大のもの）から取り出される
        result += -heapq.heappop(memo)
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

dct=defaultdict(list)

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

hq=[]
val=0

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

print(-val)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
A = []
for i in range(1, M + 1):
    while AB:
        if AB[-1][0] <= i:
            cand = - AB.pop(-1)[1]
            heapq.heappush(A, cand)
        else:
            break
    
    if A:
        ans += - heapq.heappop(A)
    
print(ans)

Submission status: Accepted

Solution code:
import math, heapq
from operator import itemgetter
from collections import defaultdict
INF = float("inf")
MOD = int(1e9 + 7)

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

    AB = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        AB[a].append(b)

    v, que = 0, []
    for m in range(1, M + 1):
        if m in AB:
            for b in AB[m]:
                heapq.heappush(que, -b)
        if que:
            v += -heapq.heappop(que)
    print(v)

main()

Submission status: Accepted

Solution code:
import heapq
import collections

n, m = map(int, input().split())
work = collections.defaultdict(list)
hp = [[] for _ in range(m+1)]
ignore = []
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    work[x].append(-y)
candidate = []
for x in range(1, m+1):
    if work[x]:
        for e in work[x]:
            heapq.heappush(candidate, e)
    if candidate:
        ans += heapq.heappop(candidate)
print(abs(ans))

Submission status: Accepted

Solution code:
class Work:
    count=0
    def __init__(self,payday,money):
        Work.count+=1
        self.count=Work.count
        self.payday=payday
        self.money=money
 #moneyが大きい方、同じなら早くもらえる方、それも同じなら最初に書いてある方が強い方
    def __ft__(self,other):
        if self.money>other.money:
            return True
        if self.money==other.money:
            if self.payday<other.payday:
                return True
            if self.payday==other.payday:
                if self.count<other.count:
                    return True
        return False

    def __gt__(self,other):
        if self.money<other.money:
            return True
        if self.money==other.money:
            if self.payday>other.payday:
                return True
            if self.payday==other.payday:
                if self.count>other.count:
                    return True
        return False

#バイトの数、いつまでに稼ぐのか 
n,limit=[int(i) for i in input().split()]

#バイトのリストを作り、クラスを入れる O(n)
baitolist=[]
for i in range(n):
    payday,money=[int(i) for i in input().split()]
    work=Work(payday,money)
    baitolist.append(work)

#日数でランク付け　O(n)
summoney=0    
rank=[[] for i in range(limit+1)]
for baito in baitolist:
    if baito.payday<=limit:
        rank[baito.payday].append(baito)

        
import heapq
accessible=[]
count=1


for i in range(limit):
    for baito in rank[count]:
        heapq.heappush(accessible,baito)
    if accessible!=[]:
        dowork=heapq.heappop(accessible)
        summoney+=dowork.money
    count+=1
    
    
print(summoney)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int, input().split())
job = {}
for i in range(n):
    a,b = map(int, input().split())
    if a not in job.keys():
        job[a] = [(-b,a)]
    else:
        job[a].append((-b,a))
 
hq = []
 
max_income = 0
for i in range(1,m+1):
    if i in job.keys():
        for j in job[i]:
            heapq.heappush(hq,(j))
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i
 
print(max_income)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
n,m = map(int, input().split())
job_list = {}
for i in range(n):
    a,b = map(int, input().split())
    if a in job_list:
        job_list[a].append((-b,a))
    else:
        job_list[a] = [(-b,a)]
# job_list.sort(key=lambda x:x[0])
# print(job_list)

hq = []
max_income = 0
# j = 0
for i in range(1,m+1):
    if i in job_list:
        for j in job_list[i]:
            heapq.heappush(hq, j)
    # while j < n and job_list[j][0] <= i:
        # heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        # j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
n,m = map(int, input().split())
job_list = []
for i in range(n):
    a,b = map(int, input().split())
    job_list.append((a,b))
job_list.sort(key=lambda x:x[0])
# print(job_list)

hq = []
max_income = 0
j = 0
for i in range(1,m+1):
    while j < n and job_list[j][0] <= i:
        heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int, input().split())
job_list = []
for i in range(n):
    a,b = map(int, input().split())
    job_list.append((a,b))
job_list.sort(key=lambda x:x[0])
# print(job_list)

hq = []
max_income = 0
j = 0
for i in range(1,m+1):
    while j < n and job_list[j][0] <= i:
        heapq.heappush(hq, (-job_list[j][1],job_list[j][0]))
        j += 1
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, heapq


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    hq = []
    ans, j = 0, 0
    X = sorted(zip(A, B), key=lambda x: x[0])
    for i in range(1,M+1):
        while (j<N) and (X[j][0] <=i):
            heapq.heappush(hq,-X[j][1])
            j+=1
        if hq:
            ans-=heapq.heappop(hq)
    print(ans)
    return


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

import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3

from heapq import heappush, heappop

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      s += (-sum([heappop(top) for _ in range(a-k) if len(top) != 0]))
      k = a
    heappush(top, -b)

  s += (-sum([heappop(top) for _ in range(m-k+1) if len(top) != 0]))
  print(s)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import heapq
n,m = [int(i) for i in input().split()]
a = [[int(k) for k in input().split()] for _ in range(n)]
# for i in range(len(a)):
#     a[i].append(a[i][1]/a[i][0])
a.sort(key=lambda x: (x[0], x[1]))

current = 0
ans = 0
queue = []
for i in range(1,m+1):
    while current < len(a) and a[current][0] <= i:
        heapq.heappush(queue,-a[current][1])
        current += 1
    if len(queue) >= 1:
        temp = heapq.heappop(queue)
        ans += -temp

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
# 解説動画でもあったが、制約が大きいものから当てはめていくのがよいみたなのでソート
# M日後までにもらえる報酬の最大化なので、日数が短い順でソート 
AB.sort()

import heapq
# heapqを作成 
h=[]
ans=0
j=0
for i in range(1,M+1):
    while j<N: # N件のアルバイトがあるので、すべてを検証するまでループ 
        # i日後に補修がもらえないなら break AB[j][0]は各アルバイトの日数
        if AB[j][0]>i:
            break
        else:
            # i日後にもらえるアルバイトは、heapq h にいれる 
            # -をかけてあるのは、後で使うheappopは、heapqの最小値から取り出すので
            # マイナスをかけることで報酬の高い順にとりだすため
            heapq.heappush(h,-AB[j][1])
            j+=1
    # i日後に報酬をもらえるアルバイトの中で報酬の最大値を加算
    if h!=[]:
        # pushの時にマイナスをかけているので最大値からとりだせる
        # heappushでマイナスをかけているので、
        # 取り出したときに再度マイナスをかけている
        k=-heapq.heappop(h)
        ans+=k
print(ans)

Submission status: Accepted

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

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 hq:
        ans-=heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
 
def main():
    n, m = map(int,input().split())
    
    jobs = []
    for i in range(n):
        day, value = map(int,input().split())
        jobs.append((day, value))

    jobs.sort()
    
    cur, res = 0, 0
    done = []
    h = []
    for i in range(1, m+1):
        while cur < n and jobs[cur][0] <= i:
            heappush(h, -jobs[cur][1])
            cur += 1
        if not h:
            continue
        res -= heappop(h)
 
    print(res)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    #print(q)
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
D = []
for i in range(N):
    a, b = map(int, input().split())
    D.append((a, b))
D = sorted(D)
ans = 0
j = 0
que = []
for i in range(1, M + 1):
    while j < N and D[j][0] <= i:
        heappush(que, -D[j][1])
        j += 1
    if que:
        ans += -heappop(que)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ABdct = {}
    for _ in range(N):
        A, B = [int(x) for x in stdin.readline().rstrip().split()]
        if A in ABdct:
            ABdct[A].append(B)
        else:
            ABdct[A] = [B]
    ans = 0
    candidate = []
    for i in range(1, M + 1):
        if i in ABdct:
            for b in ABdct[i]:
                heapq.heappush(candidate, -b)
        if not candidate:
            continue
        b = heapq.heappop(candidate)
        b = -b
        ans += b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from heapq import heappush, heappop

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

# A日後、報酬B
# 日付ごとに報酬をリスト化
workList = {}
for i in range(n):
    a, b = map(int, input().split())
    if a not in workList:
        workList[a] = [b]
    else:
        workList[a].append(b)

hq = []
sum = 0
for i in range(1, m + 1):
    # 日付が短い順にheapに追加
    # 最大値を取り出すため正負は逆に
    if i in workList:
        for w in workList[i]:
            heappush(hq, -w)

    # 最大値を取り出し、正負を戻して加算
    if len(hq) > 0:
        val = heappop(hq)
        sum += -val

print(sum)

Submission status: Accepted

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

from heapq import heappush, heappop

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

# A日後、報酬B
workList = {}
for i in range(n):
    a, b = map(int, input().split())
    if a not in workList:
        workList[a] = [-b]
    else:
        workList[a].append(-b)
# print(workList)

hq = []
sum = 0
for i in range(1, m + 1):
    if i in workList:
        for w in workList[i]:
            heappush(hq, w)

    val = None
    if len(hq) > 0:
        val = heappop(hq)
    if val is not None:
        sum += -val

print(sum)

Submission status: Accepted

Solution code:
import heapq
N, M = [int(x) for x in input().split()]
AB_list = [[] for _ in range(M)]
for _ in range(N):
    A, B = list(map(int, input().split()))
    if (A > M): continue
    AB_list[A-1].append(B)
h = []
ans = 0
for i in range(M):
    for B in AB_list[i]:
        heapq.heappush(h, -B)
    # print(AB_list, h)
    if (len(h)):
        ans += -heapq.heappop(h)
print(ans)

Submission status: Accepted

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

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

L.sort(key = lambda x:(x[0]))
    
m = []
index = 0
ans = 0
for i in range(1, M + 1):
    c = 0
    for j in range(index, N):
        c += 1
        if L[j][0] <= i:
            heappush(m, -L[j][1])
        else:
            index = j
            c = 0
            break
    index += c
    
    if len(m) != 0:
        ans += heappop(m) * -1

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

#解法
rewards = 0
heap = []
for i in range(M):
    for reward in jobs[i]:
        heapq.heappush(heap, reward)
    if len(heap) >0:
        reword = heapq.heappop(heap)
        rewards += -reword

print(rewards)

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

q = []
idx = 0
ans = 0
for i in range(1, M+1):
    while idx < N:
        a, b = AB[idx]
        if a <= i:
            heapq.heappush(q, -b)
            idx += 1
        else:
            break
    if len(q) > 0:
        b = heapq.heappop(q)
        ans -= b

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict

N,M=map(int, sys.stdin.readline().split())

reward=defaultdict(lambda: []) 

hq=[]
for _ in range(N):
	a,b=map(int, sys.stdin.readline().split())
	reward[a].append(-1*b)


hq=[]
ans=0
for day in range(M-1,-1,-1):
	for r in reward[M-day]:
		heappush(hq,r)
	if hq:
		t=heappop(hq)
		ans+=t*-1

print ans

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

n, m = map(int, input().split())
dct = defaultdict(list)

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

h = []
res = 0

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

print(-res)

Submission status: Accepted

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

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

h = []
ans = 0

for i in range(1,m+1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        ans += heapq.heappop(h)
print(-ans)

Submission status: Accepted

Solution code:
import heapq

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

pq = []
idx = 0
ret = 0
for day in range(maxDays + 1):
    while idx < n and a[idx][0] <= day:
        heapq.heappush(pq, -a[idx][1])
        idx += 1
    if pq:
        ret -= heapq.heappop(pq)

print(ret)

Submission status: Accepted

Solution code:
import  heapq

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

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

pq = []

for i in range(m):
    for j in memo[i]:
        heapq.heappush(pq,j)
    if len(pq):
        ans += -heapq.heappop(pq)

print(ans)

Submission status: Accepted

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

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

h = []
ans = 0

for i in range(1,m+1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        ans += heapq.heappop(h)
print(-ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

maxA = 10**5

N, M = map(int, input().split())
works = [[] for _ in range(maxA)]
for _ in range(N):
    A, B = map(int, input().split())
    works[A-1].append(-B)

PQ = []
ans = 0
for dayRest in range(1, M+1):
    for B in works[dayRest-1]:
        heappush(PQ, B)
    if not PQ: continue
    B = heappop(PQ)
    ans += -B

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict as dd
N, M = map(int, input().split())
arrs = dd(list)
for _ in range(N):
  a, b = map(int, input().split())
  arrs[a].append(-b)
q = []
ans = 0
for a in range(1, M+1):
  for b in arrs[a]:
    heappush(q, b)
  if len(q):
    ans -= heappop(q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N,M = map(int,input().split())
job = [list(map(int,input().split())) for _ in range(N)]
job.sort()
H = []
ans = 0
i = 0
for x in range(1,M + 1):
    while i < N and job[i][0] == x:
        add = [-job[i][1],job[i][0]]
        heappush(H,add)
        i += 1
    if len(H) != 0:
        salary,k = heappop(H)
        ans += -1 * salary
print(ans)

Submission status: Accepted

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

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r) #マイナスにしている
heap = []
rewards = 0
for i in range(M):
    for reward in jobs[i]:
        heapq.heappush(heap,reward)
    if len(heap) != 0:
        r = heapq.heappop(heap)
        rewards += -r
print(rewards)

Submission status: Accepted

Solution code:
import heapq

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

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
case = sorted([[int(j) for j in input().split()] for i in range(N)], key=lambda x: -x[0])

candidate_queue = []
ans = 0

for i in range(1, M + 1):
    while case:
        if case[-1][0] <= i:
            heapq.heappush(candidate_queue, -case.pop(-1)[1])
        else:
            break

    if candidate_queue:
        ans += -heapq.heappop(candidate_queue)

print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
case = sorted([[int(j) for j in input().split()] for i in range(N)], key=lambda x: -x[0])

candidate_queue = []
ans = 0

for i in range(1, M + 1):
    while case:
        if case[-1][0] <= i:
            heapq.heappush(candidate_queue, case.pop(-1)[1] * (-1))
        else:
            break

    if candidate_queue:
        ans += heapq.heappop(candidate_queue) * (-1)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N_baito,M_days = map(int,input().split())
hosyuList = [[] for _ in range(M_days)]

for _ in range(N_baito):
    days,hosyu = map(int,input().split())
    if days <= M_days:
        hosyuList[days-1].append(hosyu)

workList = []
hosyu = 0
for day in range(M_days):
    for baito in hosyuList[day]:
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)

Submission status: Accepted

Solution code:
import numpy as np
import heapq
N,M = map(int,input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]

for _ in range(N):
  a,b = map(int,input().split())
  jobs[a].append(b)
ans = 0
heap = []
for d in range(M+1):
  if jobs[d]: #空でないなら
    for _b in jobs[d]:
      heapq.heappush(heap,-_b) #heappopは最小値を返すので-をつけておく
  if heap: #空でないなら
    ans += -heapq.heappop(heap) #最小値を返してpop
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
r_jobs = list(reversed(jobs[:]))
ans = 0
q = []
cnt = 0
l = len(jobs)
for i in range(m+1):
    while cnt < l:
        if r_jobs[cnt][0] == i:
            heapq.heappush(q, -jobs.pop()[1])
            cnt += 1
        else:
            break

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

print(ans)

Submission status: Accepted

Solution code:
import os,re,sys,operator
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

setrecursionlimit(10**6)

n,m=map(int,stdin.readline().rstrip().split())
l=[[] for _ in range(m)]
h=[]
heapq.heapify(h)
for i in range(n):
    a,b=map(int,stdin.readline().rstrip().split())
    if a>m:
        continue
    l[m-a].append(b)
ans=0
for i in range(m-1,-1,-1):
    for j in l[i]:
        heapq.heappush(h,-j)
    if len(h)!=0:
        ans+=-(heapq.heappop(h))
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N,M = [int(x) for x in input().split()]

dic = {}
for m in range(1,M+1):
    dic.setdefault(m,[])
for _ in range(N):
    A,B = [int(x) for x in input().split()]
    if A <= M: dic.setdefault(A, []).append(B)

h = []
ans = 0
for m in dic.keys():
    for b in dic[m]:
        heappush(h, -b)
    if h:
        ans += -heappop(h)
print(ans)

Submission status: Accepted

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

for _ in range(N):
  A,B = map(int, input().split())
  if A <= M:
    H[A-1].append(-B)
Q=[]
r=0
for d in range(M):
  for v in H[d]:
    heapq.heappush(Q, v)
  if Q:
    r -= heapq.heappop(Q)
print(r)

Submission status: Accepted

Solution code:
import sys
import heapq

N,M = map(int,sys.stdin.readline().split())
jobList={}
for i in range(N):
  a,b = map(int,sys.stdin.readline().split())
  if a in jobList:
    jobList[a].append(b)
  else:
    jobList[a]=[b]
    
heapList=[]
heapq.heapify(heapList)
ans=0
for i in range (1,M+1):
  if i in jobList:
    for val in jobList[i]:
      heapq.heappush(heapList,val*-1)
  if len(heapList)>0:
    ans+=heapq.heappop(heapList)
print(ans*-1)

Submission status: Accepted

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

heap = []
ans = 0
for i in range(m+1):
    if jobs[i]:
        for x in jobs[i]:
            heapq.heappush(heap,-x)
    if heap:
        ans += -heapq.heappop(heap)


print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
parttime = []

for i in range(N):
	a, b = map(int, input().split())
	parttime.append((a, b))
	
parttime.sort()
index = 0
ans = 0
myheap = []

for day in range(M, -1, -1):
	for i in range(index, N):
		if (parttime[i][0] + day) <= M:
			heapq.heappush(myheap, -parttime[i][1])
			index = i + 1
		else:
			index = i
			break
			
	if myheap:
		ans -= heapq.heappop(myheap)
		
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
jobs = [[] for _ in range(M + 1)]

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

for i in range(M + 1):
	for j in jobs[i]:
		heapq.heappush(myheap, -j)
			
	if myheap:
		ans -= heapq.heappop(myheap)
		
print(ans)

Submission status: Accepted

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


n, m = map(int, input().split())
tmp = [ [] for _ in range(10 ** 5 + 1) ]
for _ in range(n):
    a, b = map(int, input().split())
    tmp[a].append(b)

h = []
ans = 0
for i in range(1, m+1):
    for bb in tmp[i]:
        heappush(h, -bb)
    if h:
        ans += -heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M = map(int,input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]
for i in range(N):
    A,B = map(int,input().split())
    jobs[A].append(B)

heap = []
ans = 0
#jobs[A]で追加しているためm+1でまわす
for i in range(M+1):
    #空出ないなら
    if jobs[i]:
        for x in jobs[i]:
            heapq.heappush(heap,-x)
    #空出ないなら
    if heap:
        ans += -heapq.heappop(heap)

print(ans)

Submission status: Accepted

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

AB = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a in AB:
        AB[a].append(b)
    else:
        AB[a] = [b]

count = 0
current = []

for day in range(1, M + 1):
    if day in AB:
    	for work in AB[day]:
            heapq.heappush(current, -work)

    #print("day{}:{}".format(day, current))
    if len(current) > 0:
        count += -heapq.heappop(current)

print(count)

Submission status: Accepted

Solution code:
import  heapq
 
N, M = map(int, input().split())
data = [[int(x) for x in input().split()] for i in range(N)]
data.sort(reverse=True, key=lambda x: (-x[0], x[1]))
 
day = M
reward = 0
 
# d日前
q = []
i = 0
for d in range(1, M + 1):
    for t in range(i, N):
        if data[t][0] > d:
            break
        i += 1
        heapq.heappush(q, -1 * data[t][1])
    if q:
        reward += heapq.heappop(q)
 
print(-1 * reward)

Submission status: Accepted

Solution code:
import heapq

#N is numbers of BAITO, M is limit of days
N,M=map(int,input().split())
 
i=0
inp ={}
while i<N:
  readTime,inCome=map(int,input().split())
  if readTime in inp:
    inp[readTime].append(-inCome)
  else:
    inp[readTime]=[-inCome]
  
  i=i+1
 
#print(inp)  
 
result=0
pool=[]
heapq.heapify(pool)
i=1
while i<=M:
  if i in inp:
    for k in inp[i]:
      heapq.heappush(pool,k)
  if len(pool)>0:
    result=result-heapq.heappop(pool)
  i=i+1
 
print(result)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
jobs = [[] for _ in range(10 ** 5 + 1)]

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

q = []
ans = 0
for i in range(m + 1):
    if jobs[i]:
        for reward in jobs[i]:
            heappush(q, -reward)
    if q:
        ans += -heappop(q)

print(ans)