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())
work = [[] for _ in range(10**5 + 1)]
for i in range(n):
    a, b = map(int, input().split())
    work[a].append(b)

total = 0
candidates = []
for d in range(1, m+1):
    for w in work[d]:
        heapq.heappush(candidates, -w)
    if len(candidates) > 0:
        total += -heapq.heappop(candidates)
print(total)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m = map(int,input().split())
lst = [[int(i) for i in input().split()] for _ in range(n)]
PQ = []
idx = 0
ans = 0
lst.sort(key = lambda x:x[0])
for i in range(1,m+1):
    while idx < n and lst[idx][0] <= i:
        heappush(PQ,-(lst[idx][1]))
        idx += 1
    if PQ: ans -= heappop(PQ)
print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[LI() for _ in range(n)]
  l.sort(reverse=True)

  q=[]
  i=1
  ans=0
  while True:
    while True:
      if len(l)>0:
        if l[-1][0]<=i:
          a,b=l.pop()
          heapq.heappush(q,-b)
        else:
          break
      else:
        break
    if len(q)>0:
      c=heapq.heappop(q)
      ans-=c
    i+=1

    if i>m:
      break

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()


from collections import deque

ab = deque(ab)
from heapq import heappush, heappop, heapify
hq = []
# heappush(hq,(1,33))
# heappush(hq,(5,43))
#
# for i in range(len(hq)):
#     print(heappop(hq))

jobs = []
#m-1日後に何をするかから考える
ret = 0
for mi in range(1,m+1):
    while len(ab)>0 and ab[0][0]<=mi:
        a,b = ab.popleft()
        heappush(jobs,[-b,a])
    if len(jobs)>0:
        ret+=heappop(jobs)[0]
print(-ret)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
# tasks[i][j]
# i: 開始日
# j: 価値
tasks = [[] for _ in range(M)]
for _ in range(N):
    A,B = map(int, input().split())
    if A <= M:
        tasks[M - A].append(B)

from heapq import *

que = []
for day in range(M):
    for task in tasks[day]:
        if len(que) < day + 1:
            heappush(que, task)
        elif len(que) == day + 1:
            heappushpop(que, task)

print(sum(que))

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
jobs = [[] for _ in range(M+1)]
for _ in range(N):
    a, b = lr()
    if a > M:
        continue
    jobs[a].append(b)

answer = 0
candidate = []
for i in range(1, M+1):
    for job in jobs[i]:
        heappush(candidate, -job)
    if candidate:
        answer += heappop(candidate)

answer *= -1
print(answer)
# 31

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split(" "))
work_que = []
can_work = []
ans = 0
for i in range(N):
    a, b = map(int, input().split(" "))
    heapq.heappush(work_que, (a, -b))

for i in range(M, -1, -1):
    while len(work_que) > 0 and work_que[0][0] + i <= M:
        top_work = heapq.heappop(work_que)
        heapq.heappush(can_work, top_work[1])
    
    if len(can_work) > 0:
        ans += -heapq.heappop(can_work)
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(-ret)


def solve(N, M, A):
    A = deque(sorted(A, key=lambda x: x[0], reverse=False))

    jobs = []
    heapq.heapify(jobs)

    ret = 0
    for day in range(M):
        nokori = day + 1

        dn = 0
        #print(nokori)
        #print(A)
        for job in A:
            if job[0] == nokori:
                heapq.heappush(jobs, -job[1])
                dn += 1
            else:
                break
        for i in range(dn):
            A.popleft()

        #print(jobs)
        if jobs:
            #print(jobs)
            ret += heapq.heappop(jobs)

        #print(nokori)
        #print(jobs)
        #print(A)

    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
from heapq import heapify, heappop, heappush

def main():
    N, M = input_nums()
    jobs = {}
    for i in range(1, 10**5+1):
        jobs[i] = [0]
    for i in range(N):
        A, B = input_nums()
        jobs[A].append(B)
    res = 0
    hq = [0]
    heapify(hq)
    for i in range(1, M+1):
        for c in jobs[i]:
            heappush(hq, -c)
        if not hq:
            continue
        res -= heappop(hq)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

db.sort(reverse=True)

# ヒープキュー（最小値・最大値の取得）
import heapq
a=[]
heapq.heapify(a)

ans = 0
pnt = 0
day = m-1
while(day>=0):
    if(pnt < len(db)):
        while(db[pnt][0] == day):
            heapq.heappush(a,db[pnt][1])
            pnt += 1
            if(pnt == len(db)):
                break
    day -= 1

    if(len(a) > 0):
        ans -= heapq.heappop(a)

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    #cost[i]:i日後に報酬が貰える仕事の報酬
    cost = [[] for _ in range(10**5+10)]
    for _ in range(n):
        a,b = map(int, input().split())
        cost[a].append(b)

    res = 0
    hq = [0]
    heapq.heapify(hq)
    for i in range(1, m+1):
        for c in cost[i]:
            heapq.heappush(hq, -c)
        if not hq:
            continue
        res -= heapq.heappop(hq)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    #cost[i]:i日後に報酬が貰える仕事の報酬
    cost = [[] for _ in range(10**5+10)]
    for _ in range(n):
        a,b = map(int, input().split())
        cost[a].append(b)

    res = 0
    hq = [0]
    heapq.heapify(hq)
    for i in range(1, m+1):
        for c in cost[i]:
            heapq.heappush(hq, -c)
        if not hq:
            continue
        res -= heapq.heappop(hq)
    print(res)
            





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
work = [[] for _ in range(M)]
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        work[a-1].append(b)
ans = 0
q = []
heapq.heapify(q)
for i in range(M):
    for x in work[i]:
        heapq.heappush(q, -x)
    if q != []:
        ans += heapq.heappop(q)*(-1)
print (ans)

Submission status: Accepted

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

import heapq

def main():
    n, m = map(int, input().split())
    ab = []
    for i in range(n):
        a, b = map(int, input().split())
        ab.append((a, b))
    ab.sort(key=lambda x: x[0])
    doable = []
    next = 0
    res = 0
    for dt in range(m + 1):
        while next < n:
            if ab[next][0] <= dt:
                a, b = ab[next]
                heapq.heappush(doable, (-b, a))
                next += 1
            else:
                break
        if doable:
            mb, a = heapq.heappop(doable)
            b = -mb
            res += b
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq

class Reverse:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __repr__(self):
        return repr(self.val)


class PriorityQueue:

    def __init__(self, x=[], desc=False):
        if desc:
            for i in range(len(x)):
                x[i] = Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

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


def main():
    n, m = list(map(int, readline().split()))

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

    ab.sort(key=itemgetter(0))
    a = [ab[i][0] for i in range(n)]
    b = [ab[i][1] for i in range(n)]
    pq = PriorityQueue(desc=True)
    ans = 0

    idxprev = 0

    for day in range(1, m + 1):
        idxcur = bisect.bisect_right(a, day)
        if idxcur > idxprev:
            for i in range(idxprev, idxcur):
                pq.push(b[i])
                idxprev = idxcur
        if pq:
            ans += pq.pop()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

w_list = []
pq = []

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

ptr = 0
ret = 0
for i in range(m):
    while True:
        if ptr < n and w_list[ptr][0] <= i + 1:
            heapq.heappush(pq, -w_list[ptr][1])
            ptr += 1
        else:
            break
    if pq:
        ret -= heapq.heappop(pq)

print(ret)

Submission status: Accepted

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

ans=0
q=[]
heapify(q)
for i in range(1,m+1):
    for x in work[i]:
        heappush(q,-x)
    if q!=[]: ans+=heappop(q)
print(-ans)

Submission status: Accepted

Solution code:
#python3
from heapq import heappop
from heapq import heappush
def main():
    n, m = map(int, input().split())
    works = [[] for _ in range(m)]
    for _ in range(n):
        a, b = map(int, input().split())
        if a > m:
            continue
        works[m-a].append(b)
    s = 0
    h = [] 
    for i in reversed(range(m)):
        for b in works[i]:
            heappush(h, -b)
        if len(h) != 0:
            s += -heappop(h)
    print(s)
main()

Submission status: Accepted

Solution code:
import sys
import heapq

input=sys.stdin.readline

N,M=map(int,input().split())
job={i:[] for i in range(1,M+1)}
for i in range(0,N):
    a,b=map(int,input().split())
    if M>=a:
        job[a].append(b)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x:x[0])
ans=0
q=[]
heapq.heapify(q)
e=0
for i in range(1,m+1):
  while e<n and ab[e][0]==i:
    heapq.heappush(q,-ab[e][1])
    e+=1
  if len(q)>0: 
    ans-=heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
n,m=map(int,input().split())
J=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        J[a-1].append(b) #日数ごとに報酬を入れる

ans=0
Q=[]
hq.heapify(Q)
for j in J: #最終日から数えてj日目において
    for k in j:
        hq.heappush(Q,-k) #それまでにやるべき仕事を入れる
    if Q:
        ans-=hq.heappop(Q) #今やるべき仕事のなかで一番高いやつを取る
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

AB.sort()

STOCK = []
ans = 0

idx = 0
for d in range(1, M+1):
    for i in range(idx, N):
        a, b = AB[i]
        if a <= d:
            heappush(STOCK, -b)
            idx += 1
        else:
            break

    if STOCK:
        p = heappop(STOCK)
        ans -= p


print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

AB.sort()

STOCK = []
ans = 0

idx = 0
for d in range(1, M+1):
    for i in range(idx, N):
        a, b = AB[i]
        if a <= d:
            heappush(STOCK, -b)

            if i == N - 1:
                idx = N
        else:
            idx = i
            break

    if STOCK:
        p = heappop(STOCK)
        p = -p
        ans += p


print(ans)

Submission status: Accepted

Solution code:
from heapq import *
n,m = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(n)]
a.sort(key=lambda x:x[0])
ans = 0
PQ = []
heapify(PQ)
idx = 0
for i in range(1,m+1):
    while idx < n and a[idx][0] <= i:
        heappush(PQ,-a[idx][1])
        idx += 1
    if PQ: ans -= heappop(PQ)
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
n,m = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(n)]
a.sort(key=lambda x:x[0])
ans = 0
PQ = []
idx = 0
for i in range(1,m+1):
    while idx < n and a[idx][0] <= i:
        heappush(PQ,-a[idx][1])
        idx += 1
    if PQ: ans -= heappop(PQ)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m, *AB = map(int, open(0).read().split())
B = [[] for _ in range(m)]
for a, b in zip(AB[::2], AB[1::2]):
    if a <= m:
        B[a-1].append(b)

ans = 0
heap = []
for b in B:
    for x in b:
        heappush(heap, -x)
    if heap:
        ans -= heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m, *AB = map(int, open(0).read().split())
AB = [(a, b) for a, b in zip(AB[::2], AB[1::2]) if a <= m]
AB_ = [[] for _ in range(m)]
for a, b in AB:
    AB_[a-1].append(b)

ans = 0
heap = []
for ab in AB_:
    for x in ab:
        heappush(heap, -x)
    if heap:
        ans -= heappop(heap)
print(ans)

Submission status: Accepted

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

def TLE():
    X.sort(key=lambda x: (-x[1], x[0]))
    days = [i for i in range(1, M+1)]
    ans = 0
    for a, b in X:
        if len(days) == 0:
            break
        if days[-1] < a:
            continue
        index = bisect.bisect_right(days, a)
        if index > 0 and days[index-1] >= a:
            days.pop(index-1)
        elif index > 0 and days[index-1] <a:
            days.pop(index) 
        elif index == 0 and days[0] >= a:
            days.pop(0)
        else:
            continue
        ans += b
    print(ans)
# TLE()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
job = sorted(AB)
reward_list = []
ans = 0
j = 0
for i in range(1, M + 1):
    while j < N and job[j][0] <= i:
        heapq.heappush(reward_list, -job[j][1])
        j += 1
    if len(reward_list) > 0:
        ans -= heapq.heappop(reward_list)
print(ans)

Submission status: Accepted

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

cd = []
heapq.heapify(cd)
cnt = 0
ans = 0
# b, a
# aの条件
for k in range(m+1):
    # a = kの仕事をheappush

    for i in range(cnt, n):
        a, b = work[i]

        if a == k:
            heapq.heappush(cd, -b)
        else:
            cnt = i
            break

        if i == n-1:
            cnt = n-1

    if not cd:
        continue
    ans -= heapq.heappop(cd)
print(ans)

Submission status: Accepted

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

cd = []
heapq.heapify(cd)
cnt = 0
ans = 0
# b, a
# aの条件
for k in range(m+1):
    # a = kの仕事をheappush

    for i in range(cnt, n):
        a, b = work[i]

        if a == k:
            heapq.heappush(cd, [-b, a])
        else:
            cnt = i
            break

        if i == n-1:
            cnt = n-1

    if not cd:
        continue
    ans -= heapq.heappop(cd)[0]
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)])

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

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = [[0] * 2] * N
for i in range(N):
	AB[i] = list(map(int, input().split()))
AB.sort()

x = []
ans, j = 0, 0
for i in range(1, M + 1):
	while j != N and AB[j][0] <= i:
		heapq.heappush(x, -AB[j][1])
		j += 1
	if len(x) != 0:
		ans -= heapq.heappop(x)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
works = [[] for _ in range(M+1)]
#Bが報酬
for _ in range(N):
    a, b = lr()
    if a <= M:
        works[a].append(b)

cand = []
answer = 0
for i in range(1, M+1):
    for work in works[i]:
        heappush(cand, -work)
    if cand:
        answer -= heappop(cand)

print(answer)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x:x[0])
AB.append([10**5+1,0])
h=[]
ans=0
for i in range(1,M+1):
  while AB[0][0]<=i:
    heapq.heappush(h,-AB.pop(0)[1])
  if len(h)>0:
    ans+=-heapq.heappop(h)
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)])

work = []
heapq.heapify(work)

idx = 0
res = 0
sz = 0
for i in range(m, -1, -1):
    dayleft = m - i
    while idx < n and ab[idx][0] <= dayleft:
        heapq.heappush(work, -ab[idx][1])
        sz += 1
        idx += 1
    if sz == 0:
        continue
    res -= heapq.heappop(work)
    sz -= 1
print(res)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
N, M = map(int, input().split())
AB = defaultdict(list)
for _ in range(N):
    a, b = map(int, input().split())
    AB[a].append(b)
# print(AB)
h = []
ans = 0
for i in range(1, M+1):
    if i in AB:
        for x in AB[i]:
            heapq.heappush(h, - x)
    if len(h) > 0:
        ans -= heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
AB = sorted(AB, reverse=True)
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
        else:
            break
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
# AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, reverse=True)
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
        else:
            break
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq


def resolve():
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(N)]
    AB.sort()
    q=[]
    sm =0
    counter =0
    for i in range(1,M+1):
        while counter <N and AB[counter][0]<=i:
            hq.heappush(q,-AB[counter][1])
            counter += 1

        if not q:
            continue
        sm -= hq.heappop(q)
    print(sm)


    

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#137_D
import heapq

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

l = []
heapq.heapify(l)

tmp = 0
ans = 0
for i in range(1, m+1):
    for j in range(tmp, n):
        a, b = ab[j]
        if i == a:
            heapq.heappush(l, -b)
        else:
            tmp = j
            break
    if len(l) > 0:
        ans += -1 * heapq.heappop(l)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
import bisect

n,m = map(int,input().split())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a, -b])
L.sort()
T = deque(L)
K = []
ans = 0
for i in range(m):
    while len(T) != 0:
        a = T.popleft()
        if a[0] == i+1:
            heapq.heappush(K, a[1])
        else:
            T.appendleft(a)
            break
    if len(K) != 0:
        t = heapq.heappop(K)
        ans += t
print(-ans)

Submission status: Accepted

Solution code:
import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

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

for day in range(1,M+1):
    for i in range(len(mission[day])):
        heapq.heappush(mission[0],mission[day][i])
    if mission[0]:
        work += heapq.heappop(mission[0])

print(-work)

Submission status: Accepted

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

def main():
    n,m=map(int,input().split())
    ab=[]
    for i in range(n):
        a,b=map(int,input().split())
        if a>m:
            continue
        ab.append((a,b))
    ab.sort(reverse=True)    
    q=[]
    ans=0
    for i in range(1,m+1):
        while ab and ab[-1][0]<=i:
            a,b=ab.pop()
            heappush(q,-b)
        if q:
            b=-heappop(q)
            ans+=b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Summer Vacation
https://atcoder.jp/contests/abc137/tasks/abc137_d

"""
import sys


from heapq import heapify, heappop, heappush

def solve(N, M, jobs):
    heapify(jobs)
    availables = []
    ans = 0
    for day in range(1, M+1):
        while jobs and jobs[0][0] <= day:
            A, B = heappop(jobs)
            heappush(availables, (-B))
        if availables:
            ans -= heappop(availables)
    return ans


def main(args):
    N, M = map(int, input().split())
    jobs = []
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append((A, B))
    ans = solve(N, M, jobs)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import heapq as hp
def o():return map(int,input().split())
n,m=o()
c=[[0] for i in range(m)]
for i in range(n):
  a,b=o()
  if a<=m:
    c[m-a]+=[-b]
d=[]
ans=0
for i in range(m-1,-1,-1):
  for j in c[i]:
    hp.heappush(d,j)
  ans-=hp.heappop(d)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
import heapq


def input():
    return sys.stdin.readline()[:-1]


def solve():

    # a = [1, 6, 8, 0, -1]
    # heapq.heapify(a)  # リストを優先度付きキューへ
    # print(a)

    # print(heapq.heappop(a))  # 最小値の取り出し
    # print(a)

    # heapq.heappush(a, -2)  # 要素の挿入
    # print(a)
    N, M = map(int, input().split())
    jobs = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        jobs[M-a].append(b)
    que = []
    heapq.heapify(que)
    total = 0
    for i in reversed(range(M)):
        for b in jobs[i]:
            heapq.heappush(que, -b)
        if que:
            total += -heapq.heappop(que)
    print(total)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq as pq
N,M = map(int,input().split())
dic = defaultdict(list)
for i in range(N):
    a,b = map(int,input().split())
    if a <= M:
        dic[a].append(b)
ls = []
ans = 0
for i in range(0,M+1):
    for j in dic[i]:
        pq.heappush(ls,-j)
    if ls:
        ans -= pq.heappop(ls)
print(ans)