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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import heapq


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

heap_q = []
reword = 0
j = 0
for i in range(M):
  while j<N and ABn[j][0] <= i+1:
    heapq.heappush(heap_q,-ABn[j][1])
    j+=1
  if len(heap_q) > 0:
    reword += heapq.heappop(heap_q) * (-1)
print(reword)

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())
  if A > M:
    continue
  dct[M-A].append(-B)

h = []
ans = 0
for i in range(M-1,-1,-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:
N,M = map(int,input().split())
import heapq
from collections import defaultdict
l = []
heapq.heapify(l)
d = defaultdict(list)

for i in range(N):
    a,b = map(int,input().split())
    if a > M:
        continue
    d[a].append(b)

ans = 0
for i in range(M+1):
    for v in d[i]:
        heapq.heappush(l,-v)
    if len(l) == 0:
        continue
    ans += -heapq.heappop(l)
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 = []
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 heappush, heappop


#  https://atcoder.jp/contests/abc137/submissions/6840855 を参考にした。
q = []
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, reverse=True)

    q = []
    answer = 0
    for i in range(m-1, -1, -1):
        while ab and i + ab[-1][0] <= m:
            (a, b) = ab.pop()
            heappush(q, -b)

        if q:
            answer -= heappop(q)

    print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq

N, M = list(map(int, input().split()))
jobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue
    jobs.append((A, B))

jobs.sort(reverse=True)

q = []
ans = 0
for i in range(1, M + 1):
    while jobs and jobs[-1][0] <= i:
        A, B = jobs.pop()
        heapq.heappush(q, -B)

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

Submission status: Accepted

Solution code:
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 Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if len(self.hq) == 0:
            return None
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)

    def top(self):
        if self.desc:
            return self.hq[0].val
        else:
            return self.hq[0]

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


n, m = map(int, input().split(' '))
ab = []
for _ in range(n):
    a, b = map(int, input().split(' '))
    if a > m:
        continue
    ab.append((a, b))
ab.sort(reverse=True)

ans = 0
h = Heapq([], desc=True)
for i in range(1, m+1):
    while ab and ab[-1][0] <= i:
        a, b = ab.pop()
        h.push(b)
    if h:
        ans += h.pop()
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = list(map(int, input().split()))
days = [[] for _ in range(M + 1)]
for i in range(N):
    a, b = list(map(int, input().split()))
    if a > M: continue
    days[a].append(b)

reward = []
heapq.heapify(reward)

total = 0
for i in range(M)[::-1]:
    tasks = days[M - i]
    for task in tasks:
        heapq.heappush(reward, -1 * task)

    if len(reward) > 0:
        total += heapq.heappop(reward) * (-1)

print(total)

Submission status: Accepted

Solution code:
import heapq
def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)
 
n,m = map(int,input().split())
 
l = []
for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)
l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)
 
print(ans)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): #startline--------------------------------------------
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(N)]
    heap = []
    AB.sort(key = lambda x:x[0],reverse = True)
    ans = 0
    for i in range(1,M+1):
        while AB and AB[-1][0] <= i:
            heappush(heap,-AB.pop()[1])
        if heap:
            ans -= heappop(heap)

    print(ans)
    
if __name__ == "__main__":
    main() #endline===============================================




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Accepted

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

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

total = 0
candidates = []
heapq.heapify(candidates)

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

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)
    
    if candidates:
        total -= heapq.heappop(candidates)

print(total)

Submission status: Accepted

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

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

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

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

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

print(total)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
days = [[] for _ in range(M + 1)]
for n in range(N):
	a,b = map(int,input().split())
	if a > M:
		continue
	days[a].append(-b)

total_reward = 0
q = []
for day in range(M + 1):
	this_day = days[day]
	for reward in this_day:
		heapq.heappush(q,reward)
	if len(q):
		total_reward -= heapq.heappop(q)
print(total_reward)

Submission status: Accepted

Solution code:
import heapq

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

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

l.sort()
q = []
ans = 0
cnt = 0
for i in range(1,m+1):
    while cnt < n and l[cnt][0] == i:
        heapq.heappush(q,-l[cnt][1])
        cnt += 1
    
    if len(q) != 0:
        ans += -heapq.heappop(q)

print(ans)

Submission status: Accepted

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

ans = 0
index = 0
import heapq
hq = []
for i in range(M):
    while index < N and lst[index][0] <= i + 1:
        heapq.heappush(hq, lst[index][1])
        index += 1
    if len(hq) > 0:
        ans -= heapq.heappop(hq)
    # print ('ans, i', ans, i)
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

a_dict = defaultdict(lambda: [])
n, m = map(int, input().split())
for _ in range(n):
    a, b = map(int, input().split())
    a_dict[a].append(-b)
ans = 0
heap_list = []
for i in range(1, m + 1):
    for aa in a_dict[i]:
        heapq.heappush(heap_list, aa)
    if len(heap_list) > 0:
        ans -= heapq.heappop(heap_list)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

arbList = defaultdict(lambda: [])

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

arb = []
ans = 0

for day in range(M + 1):
    for b in arbList[day]:
        heapq.heappush(arb, b)
    if arb:
        ans += heapq.heappop(arb)

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

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

#ab.sort()

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

#print(ab)

tmp = 0
hq = []
ans = 0

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

Submission status: Accepted

Solution code:
import heapq

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

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

#ab.sort()

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

#print(ab)

tmp = 0
hq = []
ans = 0

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

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
n,m = map(int,input().split())
day = []
d = defaultdict(list)
for i in range(n):
    a,b = map(int,input().split())
    d[a].append(b)
task = []
cost = 0
heapq.heapify(task)
for i in range(1,m+1):
    for j in d[i]:
        heapq.heappush(task,-j)
        #print(task,j)
    if task != []:
        c = heapq.heappop(task)
        cost += (-1)*c  
print(cost)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort()
hq = []
result = 0
j = 0
for i in range(1, m + 1):
    while j < n and ab[j][0] <= i:
        heappush(hq, -ab[j][1])
        j += 1
    if hq:
        result -= heappop(hq)
print(result)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
B = [[] * M for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    B[M - a].append(b)
ans = 0
h = []
for i in range(M - 1, -1, -1):
    for b in B[i]:
        heapq.heappush(h, b * -1)
    if len(h) > 0:
        ans += heapq.heappop(h) * -1
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

q = []
heapq.heapify(q)

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

print(-ans)

Submission status: Accepted

Solution code:
import heapq
import bisect

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

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

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

# print(ab)

day = 1
# ans = []
ans = 0
pqueue = []

for i in range(n):
    if ab[i][1] > m:
        break

    if ab[i][1] <= day:
        heapq.heappush(pqueue, ab[i])
    else:
        for j in range(day, ab[i][1]):
            if len(pqueue) > 0:
                ans += heapq.heappop(pqueue)[2]
                # ans += [heapq.heappop(pqueue)[2]] // debug
                day = ab[i][1]
        heapq.heappush(pqueue, ab[i])
    # print(f"i:{i} day:{day} ans:{ans} queue:{pqueue}")

for k in range(day, m+1):
    if len(pqueue) > 0:
        ans += heapq.heappop(pqueue)[2]
        # ans += [heapq.heappop(pqueue)[2]] //debug
        # print(f"## i:{i} day:{k} ans:{ans} queue:{pqueue}")

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

kouho = []
 
ans =0
 
for i in range(1,m+1):
    if i in joblist:
        for j in joblist[i]:
            heapq.heappush(kouho,j)
    if kouho:
        ans += heapq.heappop(kouho)
 
print(-1*ans)

Submission status: Accepted

Solution code:
import heapq

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

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

q = []
heapq.heapify(q)

ans = 0
for i in reversed(range(0, M)):
  if i in jobs.keys():
    for job in jobs[i]:
      heapq.heappush(q, (-job, job))
  
  if len(q) > 0:
    ans += heapq.heappop(q)[1]

print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
a = [3, 0, 2, 6]
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)

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.sort(reverse=True)
hp = []
ret = 0
for i in range(1, M+1):
    # push
    while len(AB) > 0 and AB[len(AB)-1][0] <= i:
        heappush(hp, AB.pop()[1]*-1)
    # pop
    if len(hp) > 0:
        ret += heappop(hp)*-1

print(ret)

Submission status: Accepted

Solution code:
def main(sample_file = ''):

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)
    
    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    # for test
    if sample_file:
        sys.stdin = open(sample_file)
        
    # ----------------------------------
    # main

    N, M = R()
    AB = [R() for _ in range(N)]
    AB.sort()
    ans, index = 0, 0
    hp = []
    for left_days in range(1, M+1):
        while index < N and AB[index][0] == left_days:
            a, b = AB[index]
            heappush(hp, -b)
            index += 1
        if hp:
            ans -= heappop(hp)
    print(ans)
    # to finish code, use return instead of exit()
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

from heapq import *

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

ab.sort(reverse = True)

q = []
ans = 0
for i in range(m-1,-1,-1):
    while ab and ab[-1][0] + i <= m:
        (a,b) = ab.pop()
        heappush(q,-b)
    
    if q: ans -= heappop(q)

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)

Submission status: Accepted

Solution code:
import sys

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

import heapq

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

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            heapq.heappush(ABs[0], b)
    if len(ABs[0]) > 0:
        As -= heapq.heappop(ABs[0])
print(As)

Submission status: Accepted

Solution code:
import sys

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

import heapq

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

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            heapq.heappush(ABs[0], b)
    if len(ABs[0]) > 0:
        As += heapq.heappop(ABs[0])
print(-As)

Submission status: Accepted

Solution code:
import heapq

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

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

ans = 0
hq = []
for i in range(M):
    for d in P[i]:
        heapq.heappush(hq, d)
    if len(hq) != 0:
        ans += heapq.heappop(hq)

print(abs(ans))

Submission status: Accepted

Solution code:
import sys,heapq
input=sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AB=[list(map(int,input().strip().split())) for _ in range(N)]
AB.sort()
n=0
sumB=0
q=[]
for m in range(1,M+1):
    while n<N and AB[n][0]<=m:
        heapq.heappush(q,-AB[n][1])
        n+=1
    if len(q)!=0:
        sumB+=heapq.heappop(q)

print(-sumB)