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: Runtime Error

Solution code:
# coding: utf-8
import sys
# import bisect
# import math
# import numpy as np

# from fractions import gcd
# import itertools

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def make_divisors(n):
    # divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            # divisors.append(i)
            return i
            # if i != n // i:
            #     divisors.append(n//i)


def n_to_10(X, n):
    if int(X / n):
        return n_to_10(int(X / n), n) + str(X % n)
    return str(X % n)


def main():
    ip = IP()
    id = Idea()
    """この下から書いてね"""
    n, m = ip.IL()
    ab = ip.SILS(n)
    id.S(ab, 1, 0)
    id.S(ab, 1, 1)
    hantei = [False for _ in range(m)]
    # print(hantei)
    # print(ab)
    ans = 0
    day = 1
    for x in ab:
        try:
            if not all(hantei[:x[0]]) and not all(hantei[x[0]-1:]):
                # print(x)
                # print(hantei)
                ans += x[1]
                day += 1
                memo = np.where(np.array(hantei[x[0]-1:]) == False)
                # print(hantei[x[0]-1:])
                # print("memo", memo)
                # print(memo[0][-1])
                hantei[memo[0][-1] + x[0] - 1] = True

        except IndexError:
            pass
        # if day == m:
            # break
    # print(hantei)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
import heapq

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
ans = 0
A = []

L = sorted(L, key=lambda x: x[1],reverse=True)
L = sorted(L, key=lambda x: x[0],reverse=True)

cnt = 0

for i in range(N) :
    if i >= 1 and L[i][0] != L[i-1][0] :
        cnt = 0
    
    if (M-L[i][0]+1)-cnt <= 0 :
        continue
    if i < M :
        heapq.heappush(A,L[i][1])
        cnt += 1
    else :
        minv = heapq.heappop(A)
        if minv >= L[i][1] :
            heapq.heappush(A, minv)
        else :
            heapq.heappush(A,L[i][1])
            cnt += 1

print(sum(A))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        # return sorted(a+b)[-m:]
        m = min(m, len(a) + len(b))
        res = [0] * m
        if len(a) == 0:
            return b
        if len(b) == 0:
            return a
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while True:
                        j -= 1
                        if j < 0:
                            break
                        res[j] = b[ib]
                        ib -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while True:
                        if j < 0:
                            break
                        res[j] = a[ia]
                        ia -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = merge(q, current, M - i)
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

w = [[0] for _ in range(10000)]

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

money = 0
l = []
for i in range(m):
  l += w[i]
  if len(l) == 0:
    continue
  
  x = max(l)
  l.remove(x)
  money += x

print(money)

Submission status: Runtime Error

Solution code:
import heapq

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

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

ls = sorted(ls,key=lambda x:(x[0],-x[1]))

ans = 0
a = []
j = 0
for i in range(m-1,-1,-1):
  while j<len(ls) and ls[j][0] == m-i:
    heapq.heappush(a,ls[j][1]*(-1))
    j += 1
  g = -1*heapq.heappop(a)
  ans += g

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x: (-x[1],x[0]))
r=0
on=[-1]*M
def put(i):
    r=0
    if i<0:
        return -1
    if on[i]<0:
        if i==0:
            if on[i]==-1:
                on[i]=-2
            else:
                r=-1
        elif on[i-1]==-1:
            on[i]=i-1
        else:
            on[i]=on[i-1]
    else:
        r=put(on[i])
    return r
for a,b in AB:
    x=put(M-a)
    if x!=-1:
        r+=b
print(r)

Submission status: Runtime Error

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

dp = [0 for _ in range(100000)]

def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split()))[::-1] for _ in range(N)]
    logging.info("Hello!")

    sorted_A_B = sorted(A_B, reverse=True)
    logging.info(sorted_A_B)


    total = 0
    for i in range(M):
        if sorted_A_B[i][1] + i <= M:
            total += sorted_A_B[i][0]


    print(total)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	ab = []
	cnt = {}
	for i in range(N):
		a,b = inputMap()
		ab.append((a,b))

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

	ans = 0
	#print(aa)
	for i in range(M,0,-1):
		#print(i)
		for j, val in enumerate(aa):
			a,b = val
			#print("{} {}".format(a,i))
			if i >= a:
				cnt[a] -= 1
				ans += b
				aa.pop(j)
				#print(aa)
				break
			else:
				aa.pop(j)

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in sorted(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    for i in range(m):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            bs[i] = bs[i][1:]
            subtotal = total_money(bs, m-1)
            if tmp+subtotal > mx:
                mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Runtime Error

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

w = [[0] for _ in range(10000)]

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

money = 0
l = []
for i in range(m):
  l += w[i]
  x = max(l)
  l.remove(x)
  money += x

print(money)

Submission status: Runtime Error

Solution code:
def update(i, x):
    i += 1
    while i < n + 1:
        bit[i] += x
        i += i & -i

def get_sum(i):
    i += 1
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

n, m = map(int, input().split())
bit = [0] * (m + 2)
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x:(-x[1],-x[0]))
cnt = 0
ans = 0
for a,b in ab:
    if a <= m:
        a = m - a
        if get_sum(a) < a + 1:
            update(a, 1)
            cnt += 1
            ans += b
    if cnt==m:break
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
s = [sorted(input()) for i in range(N)]

s_int = []
a_ord = ord('a')
for _s in s:
    v = list(map(lambda x: ord(x)-a_ord, _s))
    v = sum([v[i]*26**i for i in range(len(v))])
    s_int.append(v)

s_int = sorted(s_int)

cnt = 0
old = -1
for i in s_int:
    _cnt = 1
    if old == i:
        _cnt += 1
    else:
        cnt += _cnt * (_cnt+1)
        _cnt = 1
        old = i

print(cnt)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split(' '))))
ab = list(filter(lambda x: x[0] <= m, ab))
ab = sorted(ab, key=lambda x: (-x[1], -x[0]))

ans = 0
while m > 0:
    ab = list(filter(lambda x: x[0] <= m, ab))
    if ab[0][0] <= m:
        ans += ab[0][1]
        ab.pop(0)
    else:
        break
    m -= 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
N,M = map(int,input().split(' '))
AB = [[] for i in [0]*(M+1)]
for i in [0]*N:
	a,b = map(int,input().split(' '))
	if a <= M:
		AB[a].append(b)

an = 0
ans = 0
cand = deque([])
for i in range(1,M+1):
	for b in AB[i]:
		bisect.insort(cand,b)
	if cand:
		ans += cand.pop()
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
ans = 0
A = []

L = sorted(L, key=lambda x: x[1],reverse=True)
L = sorted(L, key=lambda x: x[0],reverse=True)

minv = float("inf")
cnt = 0

for i in range(N) :
    if i >= 1 and L[i][0] != L[i-1][0] :
        cnt = 0
    
    if (M-L[i][0]+1)-cnt <= 0 :
        continue
    if i < M :
        heapq.heappush(A,L[i][1])
        cnt += 1
    else :
        minv = heapq.heappop(A)
        heapq.heappush(A,max(L[i][1], minv))
        cnt += 1

print(sum(A))

Submission status: Runtime Error

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

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in range(m):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    for i in range(m):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            bs[i] = bs[i][1:]
            subtotal = total_money(bs, m-1)
            if tmp+subtotal > mx:
                mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

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

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
job_list = [[int(x) for x in input().split()] for i in range(N)]
job_list = sorted(job_list,key=itemgetter(1))
ans = 0
for i in range(N):
  k = len(job_list)
  for j in range(k):
    if j == len(job_list):
      break
    if i+job_list[len(job_list)-1-j][0] <= M:
      ans += job_list[len(job_list)-1-j][1]
      job_list.pop()
      break
    job_list.pop()
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(N)
used_list = [False] * N

reward = 0
for b, a in ab_list:
	index = M - a
#	print("i", index, a)
	prev_index = None
	while index >= 0:
		if not used_list[index]:
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1
		
#	print(index)
	if index >= 0:
		used_list[index] = True
		reward += b

print(reward)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
job_list = [[int(x) for x in input().split()] for i in range(N)]
job_list = sorted(job_list,key=itemgetter(1))
ans = 0
for i in range(N):
  k = len(job_list)
  for j in range(k):
    if j == len(job_list):
      break
    if i+job_list[len(job_list)-1-j][0] <= M:
      ans += job_list[N-1-i][1]
      job_list.pop()
      break
    job_list.pop()
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(res, depth, path, A, B, time, M):
    res.append(path)
    for i in range(depth, len(A)):
        if time + A[i] <= M:
            dfs(res, i+1, path + [B[i]], A, B, time + A[i], M)

N, M = map(int, input().split())
A, B = [], []
res = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dfs(res, 0, [], A, B, 0, M)
if res:
  print(sum(sorted(res, key=lambda x: sum(x))[-1]))
else:
  print(0)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10*5+2)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

Submission status: Runtime Error

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

ab=sorted(ab)

def dfs(ab,cur,day):
    if cur==len(ab):
        return 0
    if day>M:
        return 0
    gain0 = dfs(ab,cur+1,day+ab[cur][0])+ab[cur][1]
    gain1 = dfs(ab,cur+1,day)
    return max(gain0,gain1)

num=0
for i in range(len(ab)):
    if ab[i][0]>M:
        num+=1
if num==len(ab):
    print(0)
else:
    print(dfs(ab,0,1))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
jds = [
  tuple(map(int, input().split()))
  for _ in range(n)
]
jds.sort(key=lambda x: x[1], reverse=True)

jobs = [0 for _ in range(m)]
i_min = 0
for jd in jds:
  a, b = jd
  i = m - a
  if i_min > i:
    continue
  while i >= 0:
    if jobs[i] == 0:
      jobs[i] = b
      while True:
        if jobs[i_min] and jobs[i_min+1]:
          i_min += 1
        else:
          break
      break
    else:
      i -= 1

print(sum(jobs))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
job_list = [[int(x) for x in input().split()] for i in range(N)]
job_list = sorted(job_list,key=itemgetter(1))
ans = 0
for i in range(N):
  for j in range(len(job_list)):
    if i+job_list[len(job_list)-1-j][0] <= M:
      ans += job_list[N-1-i][1]
      job_list.pop()
      break
    job_list.pop()
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import array
import numpy as np

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

res=0
target=array.array('i', [])
for i in range(1,m+1):
    if i in l:
        for j in l[i]:
            bisect.insort_left(target, j)

    if not target:
        val=0
    else:
        val=target.pop()
    res+=val
    #print(target, max(target))

print(res)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
D = [[] for i in range(M)]
for i in range(N):
    A,B = map(int,input().split())
    if A <= M:
        D[A-1].append(B)
count = 0
Tax = []
for i in range(M):
    for j in D[i]:
        bisect.insort_left(Tax,j)
    if not Tax:
        continue
    count += Tax.pop()
print(count)

Submission status: Runtime Error

Solution code:
from heapq import *

def update(i, x):
    i += 1
    while i < n + 1:
        bit[i] += x
        i += i & -i

def get_sum(i):
    i += 1
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

n, m = map(int, input().split())
bit = [0] * (m + 2)
hp = []
for _ in range(n):
    a, b = map(int, input().split())
    heappush(hp, [-b, a])
cnt = 0
ans = 0
while cnt < m and hp:
    b, a = heappop(hp)
    if a <= m:
        a = m - a
        if get_sum(a) < a + 1:
            update(a, 1)
            cnt += 1
            ans -= b
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
work = [0] * N
for i in range(N):
    work[i] = [0] * 2
    work[i][1], work[i][0] = map(int, input().split())
ans = 0
work_money = sorted(work)
schedule = [0]*N
for j in range(N):
    day = M-work_money[N-1-j][1]
    while day >= 0:
        if schedule[day] == 0:
            schedule[day] += 1
            ans += work_money[N - 1 - j][0]
            break
        day -= 1
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
day_pay=[[0] for _ in range(m)]
for _ in range(n):
    a,b=map(int,input().split())
    day_pay[a-1].append(b)
    day_pay[a-1].sort()

ans=0
for d in range(0, m):
    best=0
    idx=m+2
    for i in range(d+1):
        if day_pay[i][-1]>best:
            best=day_pay[i][-1]
            idx=i
    if idx<len(day_pay):
        day_pay[i].pop()
    ans+=best
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            # q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a) -1
  b = int(b)
  
  if a > m:
    continue
  arr[a].append(b)

vs = []
res = 0
for item in arr:
  vs[len(vs):len(vs)] = item
  if len(vs) == 0:
    continue
    
  vs.sort()
  maxi = vs.pop(-1)
  res += maxi
  
print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(N)
used_list = [False] * N

reward = 0
for b, a in ab_list:
	index = M - a
#	print("i", index, a)
	prev_index = None
	while True:
		if not used_list[index]:
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1
		
#	print(index)
	if index >= 0:
		used_list[index] = True
		reward += b

print(reward)