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
from numpy import array, where

# 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 = []
                for x in hantei[x[0]-1:]:
                    if not x:
                        memo.append(x)
    
                # memo = where(array(hantei[x[0]-1:]) == False)
                # print(hantei[x[0]-1:])
                # print("memo", memo)
                # print(memo[0][-1])
                hantei[memo[-1] + x[0] - 1] = True
        except IndexError:
            pass
        # if day == m:
            # break
    # print(hantei)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
# import bisect
# import math
# from numpy import array, where

# 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:
        if not all(hantei[:x[0]]) and not all(hantei[x[0]-1:]):
            # print(x)
            # print(hantei)
            ans += x[1]
            day += 1
            memo = []
            for x in hantei[x[0]-1:]:
                if not x:
                    memo.append(x)
                    
            # memo = where(array(hantei[x[0]-1:]) == False)
            # print(hantei[x[0]-1:])
            # print("memo", memo)
            # print(memo[0][-1])
            hantei[memo[-1] + x[0] - 1] = True
        # if day == m:
            # break
    # print(hantei)
    print(ans)


main()

Submission status: Runtime Error

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

from operator import itemgetter
AB.sort(key = itemgetter(1),reverse = True)
AB.sort(key = itemgetter(0),reverse = True)


memo = {}
import sys
sys.setrecursionlimit(10**5 + 1)
def dp(i,j):
        if (i,j) in memo:
                return memo[(i,j)]
        elif i == M or j == N:
                return 0
        a,b = AB[j]
        if i <= M - a:
                return max(dp(i+1,j+1) + b, dp(i,j+1))
        return dp(i,j+1)
print(dp(0,0))

Submission status: Runtime Error

Solution code:
def replace (b,cur,l):
    for z in range(cur,-1,-1):
        if (l[z]==0):
            l[z]=b
            return l
        elif (b>l[z]):
            k=l[z]
            l[z]=b
            l=replace(k,z-1,l)
            return l
    return l

n,m=map(int,input().split())
ab=[]
for i in range(n):
    ab.append([int(x) for x in input().split()])
scores=([0]*m)
for i in range(n):
    scores=replace(ab[i][1],m-ab[i][0],scores)
print(sum(scores))

Submission status: Runtime Error

Solution code:
wanidonMacbook:~ yc$ cd Dropbox/code/atcoder/abc
wanidonMacbook:abc yc$ ls
124     126     127     128     132     133     134     135     136     a.py    b.py    c.py    d.py
wanidonMacbook:abc yc$ mkdir 137
wanidonMacbook:abc yc$ cd ../
wanidonMacbook:atcoder yc$ ls
__pycache__     agc             hoge            modint.py       testModInt.py
abc             gcd.py          hoge.py         templete.py
wanidonMacbook:atcoder yc$ cp templete.py abc/137/a.py
wanidonMacbook:atcoder yc$ cd abc/137/a.py 
bash: cd: abc/137/a.py: Not a directory
wanidonMacbook:atcoder yc$ cd abc/137/
wanidonMacbook:137 yc$ ls
a.py
wanidonMacbook:137 yc$ cp a.py b.py
wanidonMacbook:137 yc$ cp a.py v.py
wanidonMacbook:137 yc$ cp a.py c.py
wanidonMacbook:137 yc$ cp a.py d.py
wanidonMacbook:137 yc$ code c.py 
wanidonMacbook:137 yc$ python3 d.py 
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraintTraceback (most recent call last):
  File "c.py", line 32, in <module>
    main()
  File "c.py", line 13, in main
    d = defaultdict(0)
TypeError: first argument must be callable or None
wanidonMacbook:137 yc$ acornistnt
bash: acornistnt: command not found
wanidonMacbook:137 yc$ peanutbomb
bash: peanutbomb: command not found
wanidonMacbook:137 yc$ constraint
bash: constraint: command not found
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
defaultdict(<function main.<locals>.<lambda> at 0x100b01d90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraintacornistnt
peanutbomb

constraint
defaultdict(<function main.<locals>.<lambda> at 0x10c7fdd90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraintacornistnt
peanutbomb

constraint
defaultdict(<function main.<locals>.<lambda> at 0x102e1cd90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraintacornistnt
peanutbomb

constraint
defaultdict(<function main.<locals>.<lambda> at 0x10392ad90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraintaaa= acornistnt
aaa= peanutbomb

aaa= constraint
defaultdict(<function main.<locals>.<lambda> at 0x100bebd90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
aaa= acornistnt 


aaa= peanutbomb 



aaa= constraint 

defaultdict(<function main.<locals>.<lambda> at 0x10bd4fd90>, {1563547937388403509070898085: 2, 20694617904755669861703772485: 1})
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constrainta
c
o
r
n
i
s
t
n
t
p
e
a
n
u
t
b
o
m
b

c
o
n
s
t
r
a
i
n
t
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint0
2
14
17
13
8
18
19
13
19
15
4
0
13
20
19
1
14
12
1

2
14
13
18
19
17
0
8
13
19
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint0 1
2 676
14 64509974703297150976
17 1133827315385150725554176
13 2481152873203736576
8 208827064576
18 29479510200013918864408576
19 766467265200361890474622976
13 2481152873203736576
19 766467265200361890474622976
15 1677259342285725925376
4 456976
0 1
13 2481152873203736576
20 19928148895209409152340197376
19 766467265200361890474622976
1 26
14 64509974703297150976
12 95428956661682176
1 26

2 676
14 64509974703297150976
13 2481152873203736576
18 29479510200013918864408576
19 766467265200361890474622976
17 1133827315385150725554176
0 1
8 208827064576
13 2481152873203736576
19 766467265200361890474622976
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
0
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
dict_items([])
0
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
dict_items([(1563547937388403509070898085, 2), (20694617904755669861703772485, 1)])
Traceback (most recent call last):
  File "c.py", line 38, in <module>
    main()
  File "c.py", line 24, in main
    if n >= 2:
TypeError: '>=' not supported between instances of 'tuple' and 'int'
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
dict_values([2, 1])
Traceback (most recent call last):
  File "c.py", line 38, in <module>
    main()
  File "c.py", line 25, in main
    asn += n-1
UnboundLocalError: local variable 'asn' referenced before assignment
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
dict_values([2, 1])
1
wanidonMacbook:137 yc$ python3 c.py 
2
oneplustwo
ninemodsix
dict_values([1, 1])
0
wanidonMacbook:137 yc$ python3 c.py 
5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa
dict_values([3, 2])
3
wanidonMacbook:137 yc$ code ../../modint.py 
wanidonMacbook:137 yc$ code ../../modint.py 
5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaawanidonMacbook:137 yc$ 5
bash: 5: command not found
wanidonMacbook:137 yc$ abaaaaaaaa
bash: abaaaaaaaa: command not found
wanidonMacbook:137 yc$ oneplustwo
bash: oneplustwo: command not found
wanidonMacbook:137 yc$ aaaaaaaaba
bash: aaaaaaaaba: command not found
wanidonMacbook:137 yc$ twoplusone
bash: twoplusone: command not found
wanidonMacbook:137 yc$ aaaabaaaaa
bash: aaaabaaaaa: command not found
wanidonMacbook:137 yc$ python3 c.py 
5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa
dict_values([3, 2])
4
wanidonMacbook:137 yc$ python3 c.py 
2
oneplustwo
ninemodsix
dict_values([1, 1])
0
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
dict_values([2, 1])
1
wanidonMacbook:137 yc$ python3 c.py 
3
acornistnt
peanutbomb
constraint
1
wanidonMacbook:137 yc$ code b.py 
wanidonMacbook:137 yc$ python3 b.py 
3 7
5
6
7
8
9
wanidonMacbook:137 yc$ python3 b.py 
4 0
-3
-2
-1
0
1
2
3
wanidonMacbook:137 yc$ python3 b.py 
1 100
100
wanidonMacbook:137 yc$ code a.py 
wanidonMacbook:137 yc$ python3 a.py 
-13 3
-10
wanidonMacbook:137 yc$ python3 a.py 
13 3
39
wanidonMacbook:137 yc$ code d.py 
wanidonMacbook:137 yc$ python3 a.py 
3 4
4 3
4 1
2 212
wanidonMacbook:137 yc$ 4 3
bash: 4: command not found
wanidonMacbook:137 yc$ 4 1
bash: 4: command not found
wanidonMacbook:137 yc$ python3 a.py 
^CTraceback (most recent call last):
  File "a.py", line 20, in <module>
    main()
  File "a.py", line 11, in main
    A,B = LMIIS()
  File "a.py", line 5, in <lambda>
    LMIIS = lambda : list(map(int,input().split()))
KeyboardInterrupt
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0, 0, 2, 0, 3]
wanidonMacbook:137 yc$ python3 d.py 
  File "d.py", line 19
    DV[A].append(B)
                  ^
IndentationError: unindent does not match any outer indentation level
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[[], [], [2], [], [1, 3]]
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
Traceback (most recent call last):
  File "d.py", line 36, in <module>
    main()
  File "d.py", line 27, in main
    ans += l.pop(0)
IndexError: pop from empty list
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2[[0], [0], [0], [0], [0]]

0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2[[0], [0], [0], [0], [0]]

[[0], [0], [0, 2], [0], [0, 3, 1]]
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2[[0], [0], [0], [0], [0]]

[[0], [0], [0, 2], [0], [0, 1, 3]]
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2[[0], [0], [0], [0], [0]]

[[0], [0], [0, 2], [0], [0, 1, 3]]
5
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3[[0], [0], [0], [0]]

[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
7
wanidonMacbook:137 yc$ python3 d.py 
1 1
2 1[[0], [0]]

[[0], [0]]
0
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3[[0], [0], [0], [0]]

[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
7
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3[[0], [0], [0], [0]]

[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
[0]
[0, 0, 2, 3, 4]
[0, 0, 2, 3, 4, 0, 1, 3]
[0, 0, 2, 3, 4, 0, 1, 3, 0]
7
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3[[0], [0], [0], [0]]

[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
[0]
[0, 0, 2, 3, 4]
[0, 0, 2, 3, 4, 0, 1, 3]
[0, 0, 2, 3, 4, 0, 1, 3, 0]
7
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3

[[0], [0], [0], [0]]
[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
[0]
[0, 0, 2, 3, 4]
[0, 0, 0, 1, 2, 3, 3, 4]
[0, 0, 0, 0, 1, 2, 3, 3, 4]
7
wanidonMacbook:137 yc$ 
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3[[0], [0], [0], [0]]

[[0], [0, 2, 3, 4], [0, 1, 3], [0]]
[0]
[0, 2, 3, 4]
[0, 0, 1, 2, 3, 3]
[0, 0, 0, 1, 2, 3]
10
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3
10
wanidonMacbook:137 yc$ python3 d.py 
1 1
2 1
0
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3
10
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
5
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
Traceback (most recent call last):
  File "d.py", line 49, in <module>
    main()
  File "d.py", line 31, in main
    if maxv > DV[j][-1]:
IndexError: list index out of range
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[]
Traceback (most recent call last):
  File "d.py", line 50, in <module>
    main()
  File "d.py", line 32, in main
    if maxv > DV[j][-1]:
IndexError: list index out of range
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[]
Traceback (most recent call last):
  File "d.py", line 50, in <module>
    main()
  File "d.py", line 32, in main
    if len(DV)>=1 and maxv > DV[j][-1]:
IndexError: list index out of range
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[]
[0]
Traceback (most recent call last):
  File "d.py", line 50, in <module>
    main()
  File "d.py", line 36, in main
    DV[maxi].pop()
IndexError: pop from empty list
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[0]
[0]
[0]
[0]
[0, 2]
[0]
[0]
[0, 2]
[0]
-4
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[0]
[0]
[0]
[0]
[0, 2]
[0]
[0]
[0, 2]
[0]
-4
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[0]
[0]
[0]
[0]
[0, 2]
[0]
[0]
[0, 2]
[0]
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[0]
[0, 2]
[0]
[0, 2]
[0]
[0]
[0, 2]
[0]
[0, 1, 3]
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
[0]
[0]
[0, 2]
[0]
[0, 2]
[0]
[0]
[0, 2]
[0]
[0, 1, 3]
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
0
2
0
2
0
0
2
0
3
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
0
2
0
2
0
0
2
0
3
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
0
0
2
a
0
0
0
0
0
0
3
a
5
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3
10
wanidonMacbook:137 yc$ python3 d.py 
1 1
2 1
0
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
Traceback (most recent call last):
  File "d.py", line 38, in <module>
    main()
  File "d.py", line 27, in main
    tmpL += D[i][:M-i+1]
NameError: name 'D' is not defined
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
2
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
3
wanidonMacbook:137 yc$ python3 d.py 
3 4
4 3
4 1
2 2
5
wanidonMacbook:137 yc$ python3 d.py 
5 3
1 2
1 3
1 4
2 1
2 3
10
wanidonMacbook:137 yc$ python3 d.py 
1 1
2 1
0
wanidonMacbook:137 yc$

Submission status: Runtime Error

Solution code:
# coding: utf-8
n, m = map(int, input().split())
lst = list(list(map(int, input().split())) for i in range(n))
dp = [0] * 100010
lst.sort(key=lambda x: x[1], reverse=True)
for i in range(n):
    x = lst[i][0]
    dp[i + x] = max(dp[i + x], dp[i] + lst[i][1])

print(sum(dp[0: m+1]))

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = len(a_list_2) - reversed(a_list_2).index(max(a_list_2[:k + 1])) - 1
        if l < len(a_list_2):
            if a_list_1[l] <= m - i:
                ans += a_list_2[l]
                del a_list_1[l], a_list_2[l]
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)

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 time

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A
    
if __name__ == '__main__':
    N, M = InputToInt()
    A = []
    for i in range(N):
        A.append(InputToInt())
    A.sort(key=lambda x: x[0])

    L = []
    c = 0
    E = 0
    F = 1
    for i in range(M):
        if A[c][0] > M:
            break
        while F and A[c][0] <= i+1:
            L.append(A[c][1])
            c += 1
            if c == N:
                F = 0
                break
        if len(L) > 0:
            E += max(L)
            L.remove(max(L))

print(E)

Submission status: Runtime Error

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

ab = []

for i in range(n):
  aa, bb = map(int, input().split())
  ab.append((aa,bb))

ab.sort(reverse=True)

dp = [ [ -1 for _ in  range(m + 1) ] for _ in range(n + 1)]

def rec_dp(i, day):
  if dp[i][day] != -1:
    return dp[i][day]

  if i == n:
    res = 0
  elif day == 0 or ab[i][0] > day:
    res = rec_dp(i + 1, day)
  else:
    res = max(rec_dp(i + 1, day - 1) + ab[i][1], rec_dp(i + 1, day))

  dp[i][day] = res
  return res


print(rec_dp(0, m))

Submission status: Runtime Error

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

A = [None] * N
B = [None] * N

for n in range(N):
    a, b = map(int, input().split())
    A[n] = a * (-1)
    B[n] = b

zipped  = zip(A, B)
zipped  = sorted(zipped, key=lambda x: [x[0], x[1]], reverse=True)
A, B = map(list, zip(*zipped))

R   = [0] * (min(A)*(-1)+2)
now = 0

for i in range(N):
    a   = abs(A[i])
    b   = B[i]
    now = max(now, a)
    if R[now] < b:
        R[now] = b
        now    = min(now+1, M)

print(sum(R[:M+1]))

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = len(a_list_2) - reversed(a_list_2).index(max(a_list_2[:k + 1])) - 1
        if a_list_1[l] <= m - i:
            ans += a_list_2[l]
            del a_list_1[l], a_list_2[l]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
#最大日数は M + M-1 + M-2 + .. + 1
#最大選択数 は M個
Y = [[] for i in range(100001)]
for i in range(N):
    A, B = map(int,input().split())
    Y[A].append(B)

cnt = 0
C = [0]*10000
#import itertools
#C = list(itertools.chain.from_iterable(Y[1:M+1]))
#print(C)
#C.sort()
#print(sum(C[:M]))
for i in range(1,M+1):
    #if len(Y[i]) > 0:
    #C.extend(Y[i])
    C += Y[i]
    #if len(C) > 0:
    #C.sort(reverse=True)
    a = max(C)
    cnt = cnt + a
    C.remove(a)
    #del C[0]

print(cnt)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
# AB_s = [list(map(int,input().split())) for _ in range(N)]
dicts = {i:[] for i in range(1,M+1)}
for _ in range(N):
    A,B = map(int,input().split())
    dicts[A].append(B)
answer = 0
wages = []
for i in range(1,M+1):
    wages.extend(dicts[i])
    if wages:
        wages.sort()
        answer += wages.pop()
print(answer)
# AB_s = sorted(AB_s, key=lambda x:-x[0])
# print(AB_s)

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] * M

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

print(reward)