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 = []
for _ in range(n):
    a, b = map(int, input().split())
    AB.append((a,b))

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

heap = []
heapq.heapify(heap)

for i in range(1,m+1):
    while idx < len(AB):
        if AB[idx][0] == i:
            heapq.heappush(heap, AB[idx][1]*-1)
            idx += 1
        else:
            break
    if len(heap) >= 1:
        ans += heapq.heappop(heap) * -1
    elif idx == len(AB) -1:
        break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(AB, key=lambda x: x[0])  # sort by days

import heapq
que = []
heapq.heapify(que)

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

Submission status: Accepted

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

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

heap = []
ind = 0
ans = 0
for i in range(1, m+1):
    while ind<len(ab):
        if ab[ind][0]==i:
            heapq.heappush(heap, -ab[ind][1])
            ind += 1
        else:
            break
    if len(heap)>0:
        ans += heapq.heappop(heap)
    elif ind==len(ab)-1:
        break
print(-ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
import heapq

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
ab = []
for i in range(n):
    a,b = inm()
    ab.append((a,b))
ab.sort(reverse=True)
h = []
sm = 0
for d in range(m-1,-1,-1):
    while len(ab)>0 and ab[-1][0]<=m-d:
        ab2 = ab.pop()
        heapq.heappush(h, -ab2[1])
    if len(h)>0:
        sm -= heapq.heappop(h)
print(sm)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def solve():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        if a > M:
            continue
        A.append((a, b))
    A.sort(reverse=True)
    
    q = []
    count = 0
    for i in range(1, M+1):
        while A and A[-1][0] <= i:
            a, b = A.pop()
            heappush(q, -b)
        if q:
            c = -heappop(q)
            count += c
    
    return count

print(solve())

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(cands[0])
total = 0
for i in range(m):
    if len(cands[0]) > 0:
        total -= heapq.heappop(cands[0])
    if i < m - 1:
        for c in cands[i + 1]:
            heapq.heappush(cands[0], c)

print(total)

Submission status: Accepted

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

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

ans = 0
q = []

for i in range(1, M+1):
    for j in d[i]:
        heappush(q, -j)
    if q:
        ans += (-heappop(q))

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
def main():
    N, M = map(int, input().split())
    work = defaultdict(list)
    for _ in range(N):
        A, B = map(int, input().split())
        work[M-A].append(B)
    
    ans = 0
    num_list = []
    heapq.heapify(num_list)
    for i in range(M-1,-1,-1):
        if work[i]:
            for j in work[i]:
                heapq.heappush(num_list,-j)
        if num_list:
            ans -= heapq.heappop(num_list)

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る←だめでした

# 解説AC
# 後ろから問題を見ていくと良いかも？
# 前から貪欲ではなぜ行けないのか？→残り日付が遠い中で最大の報酬 よりも 残り日付が近い中で最大の報酬を選んだほうが最適になる可能性があるから
# では後ろから貪欲は？→残り日付が近いなかで最大の報酬はその時点で最適な選択肢となることが確定できる。→OK
# だけどi日後までの候補に絞ってソートし直すと O(MNlogN)の計算量になる
# →priority queueで高速化
# つまり i 日後を考えるときに、それが可能となる候補をqueに追加 (最大logNがM回必要)
# その中で最大の報酬をもたらすものをpop (最大logNがM回必要)
# 日付のソートでNlogNかかる。
# この問題の計算量はO((M+N)logN)である


from heapq import heapify, heappop, heappush, heappushpop
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


N, M = read_ints()
AB = read_tuple(N)
AB.sort()

q = PriorityQueue([])
l = 0  # ABのindex
ans = 0

for i in range(1, M + 1):
    for j in range(l, N):
        a, b = AB[j]
        if j == N - 1:
            l = N
        if a > i:  # i日以内に支払われない # こういう書き方はbugの原因になるから控えよう
            l = j
            break
        q.push(-b)  # pythonでは最小ヒープのため
    if q:  # qが空のときはしょうがないのでskip
        ans -= q.pop()

# # 前処理しておくと実装が楽という例
# from collections import defaultdict
# ilimb = defaultdict(lambda: [])
# for a, b in AB:
#     ilimb[a].append(b)

# for i in range(1, M + 1):
#     for b in ilimb[i]:
#         q.push(-b)  # pythonでは最小ヒープのため
#     if q:  # qが空のときはしょうがないのでskip
#         ans -= q.pop()

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る←だめでした

# 解説AC
# 後ろから問題を見ていくと良いかも？
# 前から貪欲ではなぜ行けないのか？→残り日付が遠い中で最大の報酬 よりも 残り日付が近い中で最大の報酬を選んだほうが最適になる可能性があるから
# では後ろから貪欲は？→残り日付が近いなかで最大の報酬はその時点で最適な選択肢となることが確定できる。→OK
# だけどi日後までの候補に絞ってソートし直すと O(MNlogN)の計算量になる
# →priority queueで高速化
# つまり i 日後を考えるときに、それが可能となる候補をqueに追加 (最大logNがM回必要)
# その中で最大の報酬をもたらすものをpop (最大logNがM回必要)
# 日付のソートでNlogNかかる。
# この問題の計算量はO((M+N)logN)である


from heapq import heapify, heappop, heappush, heappushpop
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

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


N, M = read_ints()
AB = read_tuple(N)

# AB.sort()
from collections import defaultdict
ilimb = defaultdict(lambda: [])
for a, b in AB:
    ilimb[a].append(b)

q = PriorityQueue([])
l = 0  # ABのindex
ans = 0

# for i in range(1, M + 1):
#     for j in range(l, N):
#         a, b = AB[j]
#         if a > i:  # i日以内に支払われない
#             l = j  # ココらへんに実装のバグがありそう
#             break
#         q.push(-b)  # pythonでは最小ヒープのため
#     if q:  # qが空のときはしょうがないのでskip
#         ans -= q.pop()

for i in range(1, M + 1):
    for b in ilimb[i]:
        q.push(-b)  # pythonでは最小ヒープのため
    if q:  # qが空のときはしょうがないのでskip
        ans -= q.pop()

print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A].append(-B)
# print(dic, sorted(dic.keys()))

ans = 0
heap = []

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

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(n)]

import heapq

heap = []
heapq.heapify(heap)

lst1.sort()
ans = 0
now = 0
for i in range(1,m+1):
    while True:
        if now < len(lst1) and lst1[now][0] == i:
            heapq.heappush(heap,-lst1[now][1])
            now += 1
        else:
            break
    if len(heap) != 0:
        ans -= heapq.heappop(heap) #最小値を負で取り出す

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
AB = []

for i in range(N):
  a, b = map(int, input().split())
  AB.append((a,b))

AB.sort()
index = 0
result = 0
queue = []

for limit in range(1, M+1):
  while index < N and AB[index][0] <= limit:
    a, b = AB[index]
    heappush(queue, -b)
    index += 1

  if queue:
    result += -heappop(queue)

print(result)

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

queue = []
day, i, ans = 0, 0, 0
while day <= m:
    while i < n and AB[i][0] <= day:
        heapq.heappush(queue, -AB[i][1])
        i += 1
    if len(queue):
        ans += -heapq.heappop(queue)
    day += 1
print(ans)

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(list) 
for i in range(N):
    a,b = map(int, input().split())
    d[a].append(b)

import heapq
q = []
ans = 0
for i in range(1,M+1): #1~MまでOK
    ls = d[i]
    for l in ls:
        heapq.heappush(q,-l)
    if len(q)==0:continue
    a = heapq.heappop(q)
    # print(i,ls,-a)
    ans += a
print(-ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(-b)
    except:
        pass
ans = 0
a = []
heapq.heapify(a)
for i in range(M):
    for x in w[i]:
        heapq.heappush(a, x)
    try:
        ans += -heapq.heappop(a)
    except:
        pass
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n) ], reverse=True)
que = []
ans = 0
for i in range(1, m+1):
  while ab and ab[-1][0] <= i:
    t = ab.pop()
    heapq.heappush(que, -t[1])
  if que:
    ans -= heapq.heappop(que)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque

N, M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])
d=deque(AB)
h=[]
ans=0
for i in range(M+1):
    while d and d[0][0]<=i:
        heapq.heappush(h, -d.popleft()[1])
    if h:
        ans-=heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            heapq.heappush(candidates, -b)
        else:
            s = j
            break
    else:
        s = j + 1
    if len(candidates) > 0:
        # print(candidates)
        ans += -1 * heapq.heappop(candidates)

print(ans)
"""
4 3 2

3 2 3 1
2 3 1


"""

Submission status: Accepted

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

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

AB.sort()

h = []
index = 0
answer = 0
for i in range(1, M + 1):
  while index < N:
    a, b = AB[index]
    if a == i:
      heappush(h, -b)
      index += 1
    else:
      break
  if h:
    answer += - heappop(h)
    
print(answer)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

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

hq = []
j = 0
ans = 0

for i in range(m):
  while j<n and ab[j][0] <= i+1:
    heappush(hq,-ab[j][1])
    j+=1
  if len(hq)>0:
    ans += -heappop(hq)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    N, M = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        l.append((a,b))
    l.sort(key=lambda x: x[0])
    t = []
    i = 0
    r = 0
    for d in range(1, M+1):
        while i < len(l):
            a, b = l[i]
            if a <= d:
                heapq.heappush(t, -b)
            else:
                break
            i += 1
        if not t:
            continue
        r -= heapq.heappop(t)
    return r
print(main())

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort()
    AB.reverse()
    M += 1
    w = [False] * M
    q = []
    r = 0
    for i in range(1, M):
        while AB and AB[-1][0] <= i:
            heapq.heappush(q, -AB.pop()[1])
        if q:
            r += heapq.heappop(q)
    return -r

print(main())

Submission status: Accepted

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

ans = 0

v = []
q.heapify(v)

ab.sort()
i = 0
for j in range(m):
  while True:
    if i >= n:
      break
    a, b = ab[i]
    if a > j + 1:
      break
    q.heappush(v, -b)
    i += 1
  if v:
    ans -= q.heappop(v)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
from collections import deque

N, M=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:(x[0], x[1]))
for i in range(N):
  AB[i][1]=-AB[i][1]
d=deque(AB)
ans=0
h=[]
for i in range(M+1):
  if not d and not h:
    break
  while d and d[0][0]<=i:
    heapq.heappush(h, d.popleft()[1])
  if h:
    ans-=heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
#maspyさんの

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
from heapq import heappush, heappushpop
 
N,M = map(int,input().split())
tasks = [[] for _ in range(M+1)] # 価値、締切
for _ in range(N):
    a,b = map(int,input().split())
    if a <= M:
        tasks[M-a].append(b)
 
q = []
for day in range(M+1):
    for v in tasks[day]:
        if len(q) < day+1:
            heappush(q,v)
        else:
            heappushpop(q,v)
 
answer = sum(q)
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32
import heapq

# refer to https://atcoder.jp/contests/abc137/submissions/6814694

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    from collections import defaultdict
    d = defaultdict(list)

    for i in range(N):
        d[A[i]].append(-B[i])

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

    # i日以下で追加できるものを追加していく
    # 　⇒「editorialの後ろから見ていく」になる
    for i in range(1, M+1):
        # ちょうどi日で実施できるものの候補をすべてpushする
        if d[i]:
            for v in d[i]:
                heapq.heappush(h, v)
        
        # でもその日に実行できるバイトは一つだけなので、一つを取り出す。
        # こうするとi+1...のときに、参照されなかったものも候補になる
        if h:
            res += heapq.heappop(h)
        
        # print(i, h, res)

    print(-res)

    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:
# 優先度つきキューをやるらしい
# どうすんのと思ったら毎回条件があうまで探索してpushしてpopすんのか

import heapq

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

idx = 0
ans = 0
heap = []
heapq.heapify(heap)
for i in range(1, m + 1):
    # i...残り日数
    while idx < n and arr[idx][0] <= i:
        heapq.heappush(heap, -arr[idx][1])
        idx += 1
    # この時点でヒープで次に取り出す値には残り日数iの時点での最大値（つーか最小値）が入っている
    if heap:
        ans = ans - heapq.heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
import heapq
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
heap = []
ans = 0
j = 0
 
for i in range(1, M+1): # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i): # 支払いがi日以内
        heapq.heappush(heap, -X[j][1]) # 候補の追加。最大の値が欲しいためマイナスに
        j += 1
    if len(heap):
        ans += - heapq.heappop(heap) # 候補があるとき、候補から最大値を取り出す
print(ans)

Submission status: Accepted

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

import heapq
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
heap = []
ans = 0
j = 0
 
for i in range(1, M+1): # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i): # 支払いがi日以内
        heapq.heappush(heap, -X[j][1]) # 候補の追加。最大の値が欲しいためマイナスに
        j += 1
    if len(heap):
        ans += - heapq.heappop(heap) # 候補があるとき、候補から最大値を取り出す
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
heap = []
ans = 0
j = 0
 
for i in range(1, M+1): # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i): # 支払いがi日以内
        heapq.heappush(heap, -X[j][1]) # 候補の追加。最大の値が欲しいためマイナスに
        j += 1
    if len(heap):
        ans += - heapq.heappop(heap) # 候補があるとき、候補から最大値を取り出す
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
heap = []
ans = 0
j = 0

for i in range(1, M+1): # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i): # 支払いがi日以内
        heapq.heappush(heap, -X[j][1]) # 候補の追加。最大の値が欲しいためマイナスに
        j += 1
    if len(heap):
        ans += - heapq.heappop(heap) # 候補があるとき、候補から最大値を取り出す
print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

nm = list(map(int, input().split()))
n, m = nm[0], nm[1]
d = {}
ab_list = list()
for i in range(n):
    ab = list(map(int, input().split()))
    rem_day, reward = ab[0], ab[1]
    if rem_day in d:
        d[rem_day].append(-reward)
    else:
        d[rem_day] = [-reward]


result = 0

candidates = list()

for rem in range(1, m + 1):
    added_candidates = d.get(rem)
    if added_candidates is not None:
        for ac in added_candidates:
            heappush(candidates, ac)

    if len(candidates) > 0:
        top = heappop(candidates)
        result += -top

print(result)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
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])
lst=[]
heapify(lst)
st=1
value=0
idx=0
#print(AB)
while st<=M:
    #print(value)
    while idx<N and AB[idx][0]==st:
        heappush(lst,-AB[idx][1])
        idx+=1
    if lst:
        value-=heappop(lst)
    st+=1
print(value)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
AB = []

for i in range(N):
  a, b = map(int, input().split())
  AB.append((a,b)) 

AB.sort()
queue = []
index = 0
ans = 0

for limit in range(1, M+1): # 残り limit日 で仕事を終わらせないといけない
  while index < N and AB[index][0] <= limit:
    a, b = AB[index]
    heappush(queue, -b)
    index += 1

  if queue:
    ans += -heappop(queue)

print(ans)

Submission status: Accepted

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

#日数ごとの集合を作る
jobs = {m: [] for m in range(1, M + 1)}
for ab in A_B:
  if ab[0] in jobs:
    jobs[ab[0]].append(ab[1])
#print(jobs)

#日数の少ない仕事からループして最適解を見つける
import heapq
q = []
ans = 0
#仕事にかかる日数のループであって経過日のループではない
for m in range(1, M + 1):
    for b in jobs[m]:
      #qには小さい順で格納される
      heapq.heappush(q, -b)
    #print(q)
    #qが空でないとき
    if len(q) > 0:
      #現時点での日数以下の仕事で一番稼げるものを取り出す
      neg_b = heapq.heappop(q)
      ans += -neg_b

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
jobs = {m:[] for m in range(1,M+1) }

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

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
jobs = {m: [] for m in range(1, M + 1)}
for _ in range(N):
    a, b = map(int, input().split())
    if a in jobs:
        jobs[a].append(b)

q = []
ans = 0
for m in range(1, M + 1):
    for b in jobs[m]:
        heapq.heappush(q, -b)
    if len(q) > 0:
        neg_b = heapq.heappop(q)
        ans += -neg_b

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key = lambda x: x[0])
Q = []
ans = 0
j = 0
AB.append([10**6,1])
for m in range(1,M+1):
    while AB[j][0] <= m:
        heappush(Q,-AB[j][1])
        j += 1
    if Q:
        t = -heappop(Q)
        ans += t

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
work = [0] * N
for i in range(N):
    work[i] = [0] * 2
    a, b = map(int, input().split())
    if M-a >= 0:
        work[i][0], work[i][1] = a, -1 * b
    else:
        work[i][0], work[i][1] = 10**9, -1 * b
ans = 0
work_day = sorted(work)
index = 0
heap = []
heapq.heapify(heap)
for j in range(M+1):
    if index >= N:
        if len(heap) > 0:
            ans += heapq.heappop(heap)*(-1)
        continue
    while (work_day[index][0] <= j):
        heapq.heappush(heap, work_day[index][1])
        index += 1
        if index >= N:
            break
    if len(heap) > 0:
        ans += heapq.heappop(heap)*(-1)


print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, M = MI()
    jobs = {}
    ans = 0

    for i in range(N):
        A, B = MI()
        if A not in jobs:
            jobs[A] = []
        jobs[A].append(B)

    h = []
    remaining_days = 1
    while remaining_days <= M:
        if remaining_days in jobs:
            for rewards in jobs[remaining_days]:
                heappush(h, -rewards)

        if len(h) > 0:
            rewards = heappop(h)
            ans += -rewards
        remaining_days += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify

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

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

ans = 0
num = []
heapify(num)

for j in range(1,m+1):
    for nu in lis[j]:
        heappush(num,nu)
    if len(num) > 0:
        work = heappop(num)
        ans += -work
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush,heapify
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = list(map(int,input().split()))
    if a <= M:
        AB[a].append(-b)
work = 0
AB2 = []
heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heappush(AB2,j)
    if len(AB2) > 0:
        b = heappop(AB2)
        work += -b
print(work)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = list(map(int,input().split()))
    if a <= M:
        AB[a].append(-b)
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if len(AB2) > 0:
        b = heapq.heappop(AB2)
        work += -b
print(work)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = list(map(int,input().split()))
    if a <= M:
        AB[a].append(-b)
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if len(AB2) > 0:
        b = heapq.heappop(AB2)
        work += -b
print(work)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = list(map(int,input().split()))
    if a <= M:
        AB[a].append(-b)
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)

Submission status: Accepted

Solution code:

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

T = []

for i in range(N):
  a, b = map(int, input().split())
  T.append((a, b))

T.sort()
heap = []
heapq.heapify(T)
i = 0
ans = 0

for limit in range(1, M+1):
  while (i < N) and (T[i][0] <= limit):
    cost, value = T[i]
    heapq.heappush(heap, -value)
    i += 1
  
  if heap:
    ans += -heapq.heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from operator import itemgetter

def main():
    N, M = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    AB.sort(key = itemgetter(0))
    heap = []
    ans = 0
    cnt = 0
    for i in range(1,M + 1):
        while cnt < N and AB[cnt][0] <= i:
            heapq.heappush(heap,-1*AB[cnt][1])
            cnt += 1
        if len(heap) > 0:
            ans += heapq.heappop(heap)*-1
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
hq = []
i = 0
for limit in range(1, M + 1):
    while (i < N) and (works[i][0] <= limit):
        cost, value = works[i]
        heapq.heappush(hq, -value)
        i += 1

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

AB = sorted(AB , key = lambda x : x[0])
heap = []
heapq.heapify(heap)
j = 0

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        sum += -heapq.heappop(heap)
                           
print(sum)

Submission status: Accepted

Solution code:
import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

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

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        sum += -heapq.heappop(heap)
                           
print(sum)