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/env python3
import sys, heapq
sys.setrecursionlimit(300000)


def solve(N: int, m: int, A: "List[int]", B: "List[int]"):
    p = []
    for i in range(N):
        p.append([A[i], B[i]])
    p.sort(key = lambda x: (x[0], - x[1]))
    #print(p)
    ret = 0
    tmp = 1
    idx = 0
    q = []
    while tmp <= m:
        while idx < len(p) and p[idx][0] <= tmp:
            heapq.heappush(q, -p[idx][1])
            idx += 1
        #print(q)
        if len(q) > 0:
            head = heapq.heappop(q)
            ret += -head
        tmp += 1
    print(ret)
    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:
from heapq import *
n,m=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(n)])+[[m+1,2]]
b,c,d=[],0,0
for i in range(1,m+1):
    while a[c][0]==i:
        heappush(b,-a[c][1])
        c+=1
    else:
        if len(b)!=0:
            d+=-heappop(b)
print(d)

Submission status: Accepted

Solution code:
class Plan(object):
    def __init__(self, m):
        self.plans = [-1] * (m + 1)
        self.size = m

    def reserve(self, a, b):
        a = self.find_empty(a)
        if a == -1:
            return
        self.plans[a] = [b, a+1]

    def find_empty(self, a):
        if a > self.size:
            return -1
        if self.plans[a] == -1:
            return a
        next_day = self.find_empty(self.plans[a][1])
        if next_day == -1:
            return -1
        self.plans[a][1] = next_day
        return next_day


def main():
    n, m = map(int, input().split())
    w = [list(map(int, input().split())) for _ in range(n)]
    wsorted = sorted(w, key=lambda x: x[1], reverse=True)
    plan = Plan(m)
    for work in wsorted:
        plan.reserve(*work)

    print(sum([p[0] for p in plan.plans if p != -1]))


main()

Submission status: Accepted

Solution code:
import heapq

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

baito.sort()
m = [0]*(M+1)
kouho = []
num = 0
x = 0
for day in range(M + 1):
	while True:
		if x >= N or baito[x][0] > day:
			break
		else:
			heapq.heappush(kouho, -baito[x][1])
			x+=1
	if len(kouho) > 0:
		num -= heapq.heappop(kouho)

print(num)

Submission status: Accepted

Solution code:
import heapq as hp
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], -x[1]))
j = 0
ans = 0
que = []
for i, (a, b) in enumerate(AB):
    if j + a <= M:
        hp.heappush(que, b)
        j += 1
        ans += b
    else:
        if len(que) > 0 and que[0] < b:
            v = hp.heappushpop(que, b)
            ans -= v
            ans += b

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

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

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

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


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    # 後ろから貪欲
    AB = list(zip(A, B))
    AB.sort()
    A, B = zip(*AB)
    DP = [0]
    h = MaxHeap([])
    left = 0
    for i in range(1, M+1):
        while left < N and A[left] <= i:
            h.push(B[left])
            left += 1
        if len(h) > 0:
            # print("h", h)
            b = h.pop()
            # print(b, DP[-1]+b)
            DP.append(DP[-1]+b)
        else:
            DP.append(DP[-1])
    print(DP[-1])
    # print(DP)
    # print(h)
    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:
import heapq

N, M = map(int, input().split())
D = {}
for n in range(N):
    a, b = map(int, input().split())
    D.setdefault(a, []).append(b)

hq = []
res = 0
for n in range(1, M + 1):
    if n in D.keys():
        AD = D[n]
        for l in AD:
            heapq.heappush(hq, -l)
    if hq:
        res -= heapq.heappop(hq)

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

ans = 0
min_A = min(works.keys())
if min_A < M:
    a = min_A
    bag = []
    heapq.heapify(bag)
    while a <= M:
        d = M - a
        for w in works[a]:
            heapq.heappush(bag, -w)
        if len(bag) >= 1:
            ans -= heapq.heappop(bag)
        a += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


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

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


ans = 0
jobs_h = list()
for i in range(1, m + 1):
    for job in jobs[i]:
        heapq.heappush(jobs_h, job)

    if len(jobs_h) != 0:
        # b -> -b -> b
        value = heapq.heappop(jobs_h)
        ans -= value

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

pq = []
j = 0
ans = 0
for i in range(1, M + 1):
    while albeit[j][0] == i:
        heapq.heappush(pq, -albeit[j][1])
        if j < N - 1:
            j += 1
        else:
            break
    if pq:
        ans += -heapq.heappop(pq)

print(ans)

Submission status: Accepted

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

P = {}
for a, b in AB:
    if a <= M:
        if not a in P.keys():
            P[a] = [b]
        else:
            P[a].append(b)

B = sorted(P.items(), key=lambda x:x[0], reverse=True)
Q = []
for k, v in B:
    v.sort(reverse=True)
    A = v[:M-k+1]
    for a in A:
        heapq.heappush(Q, a)
    maxp = max(len(Q)-M+k-1, 0)
    for _ in range(maxp):
        heapq.heappop(Q)

print(sum(Q))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
# def slv(N, M, AB):
#     @lru_cache(maxsize=None)
#     def f(done, day):
#         print(day)
#         if day == M:
#             b = 0
#             for i, d in enumerate(done):
#                 if d == '0':
#                     continue
#                 b += AB[i][1]
#             return b
        
#         ans = 0
#         d_ = [d for d in done]
#         for i, d in enumerate(done):
#             if d == 1 or M - day < AB[i][0]:
#                 continue
#             d_[i] = '1'
#             ans = max(ans, f(''.join(d_), day+1))
#             d_[i] = '0'
#         ans = max(ans, f(''.join(d_), day+1))
#         return ans
#     return f('0'*N, 0)


@mt
def slv(N, M, AB):
    ans = 0
    cand = []
    AB.sort(key=lambda x: x[0], reverse=True)
    for i in range(1, M+1):
        while AB and AB[-1][0] <= i:
            a, b = AB.pop()
            heapq.heappush(cand, -b)
        if cand:
            ans -= heapq.heappop(cand)
    return ans 

def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))

    # N = 10**5
    # M = 10**5
    # AB = [[random.randint(1, 10**5), random.randint(1, 10**4)] for _ in range(N)]
    # print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
import heapq
sys.setrecursionlimit(10000000)

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 = sorted(AB)
    ans = 0
    idx = 0
    priority_queue = []
    for i in range(1, M + 1):
        # print(i)
        while True:
            if idx < N and AB[idx][0] <= i:
                heapq.heappush(priority_queue, - AB[idx][1])
                idx += 1
            else:
                break
        if len(priority_queue) == 0:
            continue
        else:
            max_element = - heapq.heappop(priority_queue)
            ans += max_element
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
can_work = []
i = 0
for m in range(M + 1):
    while (i < N) and (Work[i][0]) <= m:
        heapq.heappush(can_work, -Work[i][1])
        i += 1
    if can_work:
        ans += -heapq.heappop(can_work)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
import heapq
A=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,-b])
A.sort(key=lambda x:(x[0],x[1]))
B=[]
heapq.heapify(B)
ans=0
c=0
for i in reversed(range(m)):
  while c<n:
    a,b=A[c]
    if i+a<=m:
      heapq.heappush(B,[b,a])
      c+=1
    else:
      break
  if len(B)==0:
    continue
  else:
    bb,aa=heapq.heappop(B)
    ans+=bb
print(-ans)

Submission status: Accepted

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



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

pq=[]
ans=0
for i in range(M):
    for b in tasks[i]:
        heapq.heappush(pq,-b)
    if len(pq)!=0:
        temp=heapq.heappop(pq)
        ans-=temp

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, M = list(map(int, input().split()))
M_max = 10**5+1
B = [[] for _ in range(M_max)]
for _ in range(N):
    a,b = list(map(int, input().split()))
    B[a].append(b)

for a in range(M_max):
    B[a] = sorted(B[a])

queue = []
ans = []
for m in range(1,M+1):
    if B[m]:
        b = B[m].pop(-1)
        idx = bisect_left(queue, (b, m))
        queue.insert(idx, (b, m))

    if queue:
        b, a = queue.pop(-1)
        ans.append(b)
        if B[a]:
            b_ = B[a].pop(-1)
            idx = bisect_left(queue, (b_, a))
            queue.insert(idx, (b_, a))

    #print(queue)                                                                                                                                                                                                  
    #print(ans)                                                                                                                                                                                                    
    #print()                                                                                                                                                                                                       

print(sum(ans))

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    a,b=map(int,input().split())
    d=defaultdict(list)
    for i in range(a):
        c,e=map(int,input().split())
        d[c].append(-e)
    for k,v in d.items():
        v=sorted(v)
    ans=[]
    anss=0
    for i in range(1,b+1):
        if i in d.keys():
            for j in d[i]:
                heappush(ans,j)
        if ans:
            anss+=heappop(ans)
    print(-anss)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

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

AB.sort(key=lambda x:-x[1])

skip_pointer = [i for i in range(M)]
total = 0

def update_skip(s):
    if s < 0:
        return -1
    else:
        if s == skip_pointer[s]:
            skip_pointer[s] -= 1
            return s
        else:
            t = update_skip(skip_pointer[s])
            skip_pointer[s] = t - 1
            return t

for a, b in AB:
    s = M - a
    t = update_skip(s)

    if t >= 0:
        total += b

print(total)

Submission status: Accepted

Solution code:
import heapq
import sys
n, m = [int(i) for i in input().split()]
que = list()
dic = dict()
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    if dic.get(a) is None:
        dic[a] = []
    dic[a].append(b)

cnt = 0
for i in range(1, m+1):
    if dic.get(i) is not None:
        for j in dic.get(i):
            heapq.heappush(que, -j)
    if len(que) > 0:
        _max = heapq.heappop(que)
        cnt += -_max
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N, M = LI()
    import collections
    ab = collections.defaultdict(list)
    for i in range(N):
        a, b = LI()
        ab[a].append(-1*b)

    dprint(ab)
    import heapq
    sumb = 0
    tgt = []
    heapq.heapify(tgt)

    for i in range(1, M+1):
        b_list = ab[i]
        for b in b_list:
            heapq.heappush(tgt, b)

        dprint(tgt)
        if len(tgt) != 0:
            mn = heapq.heappop(tgt)
            sumb += mn
            dprint(mn, sumb)
        dprint(tgt)

    print(sumb*-1)

solve()

Submission status: Accepted

Solution code:
import heapq
n, m = [int(item) for item in input().split()]
ab = []
for i in range(n):
    a, b = [int(item) for item in input().split()]
    ab.append([-a, b])
ab.sort(reverse = True)

st = []
newday = -1 
ans = 0
itr = 0
for day in range(1, m+1):
    if itr < n:
        while day == -ab[itr][0]:
            heapq.heappush(st, -ab[itr][1])
            itr += 1
            if itr >= n:
                break
    if not st:
        continue
    ans += heapq.heappop(st)
print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(n)]
work.sort(key=lambda x: (x[0], x[1]))
work.append([10**10, 0])
# print(work)

ans = 0
idx = 0
cand = []
for day in reversed(range(m+1)):
    while work[idx][0] <= m - day and idx < n:
        a, b = work[idx]
        heappush(cand, -b)
        idx += 1

    if len(cand) > 0:
        v = heappop(cand)
        ans += -v
        # print(day, -v)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

A = {}

for i in range(N):
  a, b = map(int, input().strip().split())
  if a not in A: A[a] = []
  A[a].append(b)

total = 0
days = []
for i in range(1, M + 1):
  if i in A:
    for a in A[i]:
      heapq.heappush(days, -a)
  if len(days) > 0:
    total += - heapq.heappop(days)

print(total)

Submission status: Accepted

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

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

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

from heapq import heappush,heappop


q = []

prev = X[0][0]
ans = 0
for x in X:
    if x[0]>M:
        break
    if x[0]!=prev:
        for i in range(x[0]-prev):
            if len(q)==0:
                break
            a=-heappop(q)
            ans+=a
        prev=x[0]
    heappush(q,-x[1])

for i in range(M-prev+1):
    if len(q)==0:
        break
    a=-heappop(q)
    ans+=a
    
print(ans)

Submission status: Accepted

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

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

q = []
ret = 0
for i in range(1, M+1):
    for j in AB[i]:
        heappush(q, j)
    if q:
        ret += heappop(q)

print(-ret)

Submission status: Accepted

Solution code:
import sys 
from bisect import insort
 
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    jobs = [[] for _ in range(M)]
    
    for _ in range(N):
        A,B = map(int,input().split())
        if A<=M:
            jobs[M-A].append(B)
            
    job_candidate = []
    reward = 0
    
    for i in range(M-1,-1,-1):
        for x in jobs[i]:
            insort(job_candidate,x)
        if job_candidate:
            reward += job_candidate.pop(-1)
            
    print(reward)
            
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heappushpop, heapreplace


class HeapQueue:
    def __init__(self, reverse=False):
        self.reverse = reverse
        self.heap = []

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

    def append(self, p, v):
        heappush(self.heap, (-p if self.reverse else p, v))

    def appendpop(self, p, v):
        return heappushpop(self.heap, (-p if self.reverse else p, v))

    def popappend(self, p, v):
        return heapreplace(self.heap, (-p if self.reverse else p, v))

    def pop(self):
        return heappop(self.heap)[1]

    def front(self):
        return self.heap[0]


N, M = map(int, input().split())
AB = [[] for _ in range(100010)]
for _ in range(N):
    a, b = map(int, input().split())
    AB[a].append(b)
ans = 0
q = HeapQueue(reverse=True)
for i in range(M):
    for b in AB[i + 1]:
        q.append(b, b)
    if len(q):
        ans += q.pop()
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

alist=[]

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

alist=sorted(alist)
#print(alist)

eternal=1
now=0
hoshu=0

koholist=[]
for i in range(m):
    j=i+1
    switch=1
    while switch==1 and eternal==1:
        if alist[now][0]<=j:
            heapq.heappush(koholist, -alist[now][1])
            if now>=n-1:
                switch=0
                eternal=0
            else:
                now+=1
        else:
            switch=0
    if len(koholist)>0:
        saidai=heapq.heappop(koholist)
        #print(saidai)
        hoshu+=saidai

print(-hoshu)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import heapq

n, m = getList()

works = [[] for i in range(m+2)]

for i in range(n):
    a, b = getList()
    try:
        works[a].append(-b)
    except:
        pass

ans = 0
q = []
# print(works)
for i, day in enumerate(works[1:]):
    if i >= m:
        # print("be")
        break
    for work in day:
        heapq.heappush(q, work)
    if q:
        reward = heapq.heappop(q)
        ans += reward
    # print(q, ans)

print(-ans)

Submission status: Accepted

Solution code:
import sys
import heapq


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    tasks = list(map(tuple, zip(A, B)))
    tasks.sort()
    tasks.reverse()

    earnables = []

    ans = 0
    for i in range(M + 1):
        while len(tasks) > 0 and tasks[-1][0] <= i:
            _, pay = tasks.pop()
            heapq.heappush(earnables, -pay)
        if len(earnables) > 0:
            ans += -heapq.heappop(earnables)

    return ans


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

    ans = solve(N, M, A, B)
    if ans is not None:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


class SegmentTree:
    def __init__(self, n, f, e):
        self.n = 2**((n - 1).bit_length())
        self.f = f
        self.e = e
        self.d = [e for _ in range(2 * self.n)]

    def __setitem__(self, key, value):
        key += self.n - 1
        self.d[key] = value
        while key > 1:
            key //= 2
            self.d[key] = self.f(self.d[2 * key], self.d[2 * key + 1])

    def __getitem__(self, key):
        return self.q(key, 1, 1, self.n + 1)

    def q(self, key, i, left, right):
        return (
            self.e if left >= key.stop or right <= key.start else
            self.d[i] if key.start <= left <= right <= key.stop else
            self.f(
                self.q(key, 2 * i, left, (left + right) // 2),
                self.q(key, 2 * i + 1, (left + right) // 2, right)
            )
        )


T = SegmentTree(M, max, -1)
for i in range(M + 1):
    T[i] = i

ans = 0
for a, b in sorted(zip(A, B), key=lambda t: (-t[1], t[0])):
    x = T[1:(M-a+2)]
    if x != -1:
        ans += b
        T[x] = -1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq
N, M = map(int, input().split())
day = [[] for _ in range(100001)]
for i in range(N):
    a, b = map(int, input().split())
    day[a].append(b)


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

print(ans)

Submission status: Accepted

Solution code:

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

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

    ab.sort(key=lambda x: x[0])
    # print(ab)
    ans = 0
    j = 0
    h = []
    for i in range(1,m+1):
        while j < len(ab) and ab[j][0] <= i:
            heappush(h, (-ab[j][1]))
            j += 1

        if len(h) > 0:
            val = heappop(h)
            # print(val)
            ans -= val

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

Submission status: Accepted

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

_d = {i:[] for i in range(M+1)}
for a,b in AB:
  _d.setdefault(a, []).append(b)
  
import heapq

ans = 0
hp = []

for i in range(1, M+1):
  for b in _d[i]:
    heapq.heappush(hp, -b)
  if hp:
    ans += -heapq.heappop(hp)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
AB.sort(key=lambda x:x[0])
curpos = 0
Works = []
d = 1#d日後までの支払いが許される
ans = 0
curpos = 0

for d in range(1,M+1):#d日後までの支払いのうち一番高いやつ
    while 1:
        if curpos>=N:break
        if AB[curpos][0]<=d:
            heapq.heappush(Works,-AB[curpos][1])
            curpos += 1
        else:
            break
    if Works:
        ans -= heapq.heappop(Works)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab.sort()
#print(ab)

import heapq
h=[]
ans=0
j=0
for i in range(1,m+1):
    while j<n:
        if ab[j][0]>i:
            break
        else:
            heapq.heappush(h,-ab[j][1])
            j+=1
    #print(i,h)
    if h!=[]:
        k=-heapq.heappop(h)
        ans+=k
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
c = []

for i in range(n):
    a,b = na()
    c.append([a,b])

import heapq

c = sorted(c)
k = 0
d = 1
h = []
ans = 0
while d < m+1:
    while k < len(c) and c[k][0] <= d:
        heapq.heappush(h, -c[k][1])
        k+=1
    if len(h) > 0:
        j = heapq.heappop(h)
        ans -= j
    d += 1

print(ans)