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 pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

from heapq import heappush, heappop

import __pypy__


def main():
    n, m = map(int, input().split())
    a, b = [0] * n, [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    order = sorted(range(n), key=lambda x: a[x])

    heap = []

    cnt = 0
    i, j = 0, 1
    while i < n and j <= m:
        while i < n and a[order[i]] <= j:
            heappush(heap, -b[order[i]])
            i += 1
        if heap:
            cnt -= heappop(heap)
        j += 1

    while j <= m:
        if heap:
            cnt -= heappop(heap)
        j += 1

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

B.sort()
j=0

import heapq
H=[]
ANS=0


for day in range(1,M+1):
    while j<N and B[j][0]<=day:
        heapq.heappush(H,-B[j][1])
        j+=1

    if H:
        ANS+=-heapq.heappop(H)


print(ANS)

Submission status: Accepted

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

N, M = map(int, input().split())
d = defaultdict(list)

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

h = []
res = 0
for a in range(1, M + 1):
    for b in d[a]:
        heappush(h, -b)
    if len(h) > 0:
        c = heappop(h)
        res -= c

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.readline

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

vmax = pow(10, 5)

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

ans = 0
h = []
for i in range(1, m + 1):
    for j in jobs[i]:
        heappush(h, j)
    if h:
        v = heappop(h)
        v *= -1
        ans += v
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info)
q = []
i = 0
j = 0
day = 1
ans = 0
for i in range(m):
    while True:
        if j >= n:
            break
        if info[j][0] == i+1:
            heapq.heappush(q, -info[j][1])
            j += 1
        else:
            break
    if q:
        ans += -heapq.heappop(q)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappop, heappush

n, m = li()
works = [[] for _ in range(m+1)]
for _ in range(n):
    ai, bi = li()
    if m-ai >= 0:
        works[m-ai].append(bi)

pque = []
ans = 0
for mi in range(m, -1, -1):
    if works[mi]:
        for wi in works[mi]:
            heappush(pque, -wi)

    if pque:
        ans += -heappop(pque)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)
#ab.sort()

#print(ab)
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)



print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'

n,m=MI()
w=[[] for _ in range(10**5+3)]
for i in range(n):
    a,b=MI()
    w[a].append(-b)

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

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=itemgetter(0))
q = []
idx = 0
ans = 0
for i in range(1, M+1):
    while idx < N:
        a, b = AB[idx]
        if a <= i:
            heapq.heappush(q, -b)
            idx += 1
        else:
            break
    if len(q)>0:
        b = heapq.heappop(q)
        ans -= b
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
ab = []
for i in range(n):
    ab.append(na())

ab.sort(key=itemgetter(0))

pq = []
import  heapq

ans = 0
p = 0
for i in range(m+1):
    while p < n and ab[p][0] <= i:
        heapq.heappush(pq, -ab[p][1])
        p += 1

    if len(pq) == 0:
        continue

    ans -= heapq.heappop(pq)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor
from heapq import heappop, heappush

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N, M = inpl()
T = sorted([inpl() for _ in range(N)], key=itemgetter(0), reverse=True)
Q = []
ans = 0

for i in range(1, M+1):
    while len(T) and (T[-1][0] == i):
        heappush(Q, -T.pop()[1])
    if len(Q):
        ans += -heappop(Q)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush as hp, heappop as hpp
N, M = map(int, input().split())
W = [[] for _ in range(M+1)]
for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    if a > M:
        continue
    W[a].append(b)

Q = []
ans = 0
for j in range(M+1):
    for b in W[j]:
       hp(Q, -b)
    if Q:
        ans -= hpp(Q)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

n, m = list(map(int, input().split()))
works = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > m:
        continue
    works.append((a, b))

works.sort(reverse=True)

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

Submission status: Runtime Error

Solution code:
import heapq

n,m=map(int,input().split())
mm=10*5+1
c=[[0] for i in range(mm)]

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

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  h+=list(map(lambda x:-x, c[d]))+[0]
  heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)

Submission status: Runtime Error

Solution code:
import heapq

n,m=map(int,input().split())
mm=10*5+1
c=[[0] for i in range(mm)]

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

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  h+=list(map(lambda x:-x, c[d]))
  heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split( ))
arr = {}
for _ in range(n):
  a, b = map(int, input().split( ))
  if a > m:
    continue
  if a in arr:
    arr[a].append(b)
  else:
    arr[a] = [b]
#arr_sorted = sorted(arr.items(), key=lambda x:x[0])
#print(arr_sorted)
ans = 0
am = []
mam = -1
for i in range(1, m+1):
  if i in arr:
    am.extend(arr[i])
  ans += max(am)
  am.remove(max(am))
print(ans)

Submission status: Runtime Error

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

jobs = [[] for i in range(10**4+1)]

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

job_schedules = [0 for _ in range(m+1)]
today = m
for i in range(len(jobs)-1, -1, -1):
    jobs[i].sort()
    for j in jobs[i]:
        day = min(today, m - j)
        while job_schedules[day] and day >= 0:
            day -= 1
        if day < 0:
            break
        job_schedules[day] = i

print(sum(job_schedules))

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    AB = [LI() for _ in range(N)]
    A_max = max([i[0] for i in AB])

    W = [[] for _ in range(A_max + 1)]
    for a, b in AB:
        if 0 <= M - a:
            W[M-a].append(b)
    # print(W)

    # 選択肢の少ない後ろの日付から決めていく
    ans = 0
    hq = []
    for i in range(M - 1, -1, -1):
        for j in W[i]:
            heapq.heappush(hq, -j)
        if hq:
            ans -= heapq.heappop(hq)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    AB = [LI() for _ in range(N)]
    A_max = max([i[0] for i in AB])

    W = [[] for _ in range(A_max + 1)]
    for a, b in AB:
        W[M-a].append(b)
    # print(W)

    # 選択肢の少ない後ろの日付から決めていく
    ans = 0
    hq = []
    for i in range(M - 1, -1, -1):
        for j in W[i]:
            heapq.heappush(hq, -j)
        if hq:
            ans -= heapq.heappop(hq)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import sys

icase=0
if icase==0:
    n,m=map(int,input().split())
#    ab=[[0]*2 for i in range(n)]
    ab=[]
    for i in range(n):
        ai,bi=map(int,input().split())
        if m-ai>=0:
            ab.append([m-ai,-bi])
#        ab[i][0]=m-ai
#        ab[i][1]=-bi
elif icase==1:
    n,m=3,4
    ab=[[2, -2], [0, -1], [0, -3]]    
elif icase==2:
    n,m=5,3
    ab=[[1, -3], [1, -1], [2, -4], [2, -3], [2, -2]]
elif icase==3:
    n,m=1,1
    ab=[]

from heapq import heappop,heappush
#heappush(H,l) 
#print(heappop(H)) #2

#ab.sort(reverse=True)
if len(ab)==0:
    print(0)
    sys.exit()
ab.sort()

m=len(ab)
a0=ab[0][0]
h=[]
asum=0
idx=0
for i in range(m):
    while ab[idx][0]<m-i:
        heappush(h,ab[idx][1])
#        print("i:",i,"idx:",idx,h)
        idx+=1
        if idx>=n:
            asum+=heappop(h)
#            print("1:",idx,asum,h)
            break
    if idx>=n:
        asum+=heappop(h)
#        print("2:",idx,asum,h)
        break

if idx>=n:
    asum+=heappop(h)
#    print("3:",idx,asum,h)

print(-asum)

Submission status: Runtime Error

Solution code:
import sys

icase=0
if icase==0:
    n,m=map(int,input().split())
#    ab=[[0]*2 for i in range(n)]
    ab=[]
    for i in range(n):
        ai,bi=map(int,input().split())
        if m-ai>=0:
            ab.append([m-ai,-bi])
#        ab[i][0]=m-ai
#        ab[i][1]=-bi
elif icase==1:
    n,m=3,4
    ab=[[2, -2], [0, -1], [0, -3]]    
elif icase==2:
    n,m=5,3
    ab=[[1, -3], [1, -1], [2, -4], [2, -3], [2, -2]]
elif icase==3:
    n,m=1,1
    ab=[]

from heapq import heappop,heappush
#heappush(H,l) 
#print(heappop(H)) #2

#ab.sort(reverse=True)
if len(ab)==0:
    print(0)
    sys.exit()
ab.sort()

a0=ab[0][0]
h=[]
asum=0
idx=0
for i in range(m):
    while ab[idx][0]<m-i:
        heappush(h,ab[idx][1])
#        print("i:",i,"idx:",idx,h)
        idx+=1
        if idx>=n:
            asum+=heappop(h)
#            print("1:",idx,asum,h)
            break
    if idx>=n:
        asum+=heappop(h)
#        print("2:",idx,asum,h)
        break

if idx>=n:
    asum+=heappop(h)
#    print("3:",idx,asum,h)

print(-asum)

Submission status: Runtime Error

Solution code:
icase=0
if icase==0:
    n,m=map(int,input().split())
    ab=[[0]*2 for i in range(n)]
    for i in range(n):
        ai,bi=map(int,input().split())
        ab[i][0]=m-ai
        ab[i][1]=-bi
elif icase==1:
    n,m=3,4
    ab=[[2, -2], [0, -1], [0, -3]]    
elif icase==2:
    n,m=5,3
    ab=[[1, -3], [1, -1], [2, -4], [2, -3], [2, -2]]

from heapq import heappop,heappush
#heappush(H,l) 
#print(heappop(H)) #2

#ab.sort(reverse=True)
ab.sort()
a0=ab[0][0]
h=[]
asum=0
idx=0
for i in range(m):
    while ab[idx][0]<m-i:
        heappush(h,ab[idx][1])
#        print("i:",i,"idx:",idx,h)
        idx+=1
        if idx>=n:
            asum+=heappop(h)
#            print("1:",idx,asum,h)
            break
    if idx>=n:
        asum+=heappop(h)
#        print("2:",idx,asum,h)
        break

if idx>=n:
    asum+=heappop(h)
#    print("3:",idx,asum,h)

print(-asum)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 4 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 4 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        print(q)
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq

N, M = map(int, input().split())
AB = [[] for i in range(10*5+1)]

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

hq = []
heapq.heapify(hq)

ans = 0
for i in range(1, M+1):
    for a in AB[i]:
        heapq.heappush(hq, a)

    if len(hq) > 0:
        ans += abs(heapq.heappop(hq))

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
v = [[] for _ in [0] * 10**5]
q = [0, 0]
for a, b in t:
    v[a - 1] += b,
z = 0
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
v = [[] for _ in [0] * 10**5]
q = [0]
for a, b in t:
    v[a - 1] += b,
z = 0
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
v = [[] for _ in [0] * 10**5]
q = []
for a, b in t:
    v[a - 1] += b,
z = 0
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = []
for _ in range(n):
    a, b = map(int, input().split())
    d.append((b, a))
d.sort(reverse=True)

cnt = m
ans = 0
i = 0
while i < n or cnt > 0:
    if d[i][1] <= cnt:
        ans += d[i][0]
        i += 1
        cnt -= 1
    else:
        i += 1
    if i == n-1 or cnt == 0:
        break        

print(ans)

Submission status: Runtime Error

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

n,m=input2()
AB=[[] for _ in range(m)]


for i in range(n):
	a,b=input2()
	if a-1 < m: #報酬受取日がmを超える仕事は除外する
		AB[a-1].append(-b) #heapqの仕様のため，-を追加

ans=0
heap=[]
for i in range(m):
	for b in AB[i]:
		heapq.heappush(heap,b)
	#最大値をheapから取り出し
	if len(heap)>0:
		MAX=heapq.heappop(heap)
		ans+= -MAX
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq

A = sorted(A)
ans = 0
day = 1
cnt = 0
x = []

for i in range(M):
    while(cnt < N):
        if A[cnt][0] == day:
            heapq.heappush(x, -A[cnt][1])
            cnt += 1
        else:
            break
    if x:  ans -= heapq.heappop(x)
    day += 1

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m= map(int,input().split())
feeindays = [[] for _ in range(m)]
for i in range(n):
    a,b= map(int,input().split())
    feeindays[a-1]+=[b]
q=[]
heapq.heapify(q)
pay=0
for l in feeindays:
    for c in l:heapq.heappush(q,-c)
    if len(q)!=0:pay+=-1 * heapq.heappop(q)
print(pay)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  if a<=m:
    ab[m-a].append(-b)

ans=0
time=0
l=[]
for i in range(m,-1,-1):
  for b in ab[i]:
    heappush(l,b)

  if l:
    ans-=heappop(l)

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

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


ans=0
time=0
l=[]
for i in range(m,-1,-1):
  for b in ab[i]:
    heappush(l,b)

  if l:
    ans-=heappop(l)

print(ans)

Submission status: Runtime Error

Solution code:
mport sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
for i in range(1,M+1):
    i = bisect.bisect_right(A,i)
    if i == 0:
        continue
    v = max(B[:i])
    i2 = B.index(v)
    A.pop(i2)
    B.pop(i2)
    ans += v
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import numpy as np
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
for i in range(1,M+1):
    i = bisect.bisect_right(A,i)
    if i == 0:
        continue
    v = max(B[:i])
    i2 = B.index(v)
    A.pop(i2)
    B.pop(i2)
    ans += v
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列
    S.sort(key=itemgetter(1),reverse=True)
    #print(S)
    ans=0
    fil=[1 for i in range(M)]

    tot=M
    bit=BIT(M)
    bit.initialize(fil)
    for s in S:
        a,b=s
        #print(tot,tot-bit.get_sum(a-1),M+1-a)
        
        
        t=bit.get_sum(a-1)
        #print(t,tot)
        if t>=tot:
            continue

        x=bit.find_kth_element(t+1)
        
        bit.add(x,-1)
        ans+=b
        tot-=1

    print(ans)
    


        




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列
    S.sort(key=itemgetter(1),reverse=True)
    print(S)
    ans=0
    fil=[1 for i in range(M)]

    tot=M
    bit=BIT(M)
    bit.initialize(fil)
    for s in S:
        a,b=s
        #print(tot,tot-bit.get_sum(a-1),M+1-a)
        
        
        t=bit.get_sum(a-1)
        #print(t,tot)
        if t>=tot:
            continue

        x=bit.find_kth_element(t+1)
        
        bit.add(x,-1)
        ans+=b
        tot-=1

    print(ans)
    


        




if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

x = 0
res = 0

hq = []
heapq.heapify(hq)

for i in range(M):
    for j in range(x, N):
        if AB[j][0] > i+1:
            x = j
            break
        heapq.heappush(hq, AB[j][1]*-1)
    else:
        x = N
    
    print(hq)
    if hq:
        res += heapq.heappop(hq)*-1

print(res)