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: Time Limit Exceeded

Solution code:
def acinput():
    return list(map(int, input().split(" ")))

def search(do,M,b):
    #print("m",M,b)
    for i in reversed(range(M-b+1)):
        if do[i]==0:
            return i
    
    return -1

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[1])
#print(ab)
now=0
res=0
do=[0]*(M+1)
while True:
    try:
        sab=ab.pop()
    except:
        break
    #print("sab",sab)
    #print(do)

    idx=search(do,M,sab[0])
    #print(idx)
    if idx>=0:
        do[idx]+=sab[1]
        res+=do[idx]


print(res)

Submission status: Time Limit Exceeded

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

count_lis = [[0 for _ in range(M)] for _ in range(N)]
x = M - ab[0][0]
if x >= 0:
  for i in range(x+1):
    count_lis[0][i] = ab[0][1]

for i in range(1, N):
  if ab[i][0] <= M:
    count_lis[i][0] = max(count_lis[i-1][0], ab[i][1])
  for j in range(1, M):
    if M - ab[i][0] >= j:
      count_lis[i][j] = max(count_lis[i-1][j-1] + ab[i][1], count_lis[i-1][j])
    else:
      count_lis[i][j] = count_lis[i-1][j]
print(max(count_lis[N-1]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,M = map(int,input().split())

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

l.sort(key=lambda x:x[0])
l.sort(key=lambda x:x[1], reverse=True)

d = defaultdict(int)
ind = 0
ans = 0

for i in range(N):
    A,B = l[i]
    if A+ind<=M:
        day = M-A
        while d[day]!=0:
            day-=1
        d[day]=1
        ans+=B
    while d[ind]!=0:
        ind+=1
    if ind>=M:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
A = []
for i in range(n):
   a,b = map(int, input().split())
   A.append((b, a))
A=sorted(A, reverse=True)
ans = 0
w = [0]*m
for a in A:
    for i in range(a[1]-1, m):
        if w[i]==0:
            w[i]=a[0]
            break
        i += 1
        
print(sum(w))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

dy = 0
ans = 0
total_dy = 0
cnt = 0
while total_dy <= M:
    tmp_max = max(B)
    idxs = [i for i, x in enumerate(B) if x == max(B)]
    if len(idxs) > 1:
        for i in idxs:
            if cnt == 0:
                tmp_max_idx = i
                cnt += 1
            elif cnt > 0 and A[tmp_max_idx] < A[i]:
                tmp_max_idx = i
    else:
        tmp_max_idx = B.index(max(B))

    cnt = 0
    if A[tmp_max_idx]+dy <= M:
        ans += tmp_max
        total_dy = A[tmp_max_idx] + dy
        dy += 1

    A.pop(tmp_max_idx)
    B.pop(tmp_max_idx)
    tmp_max_idx = 0
    if A == [] or B ==[]:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())


# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(0))
x = sorted(x,key=itemgetter(1), reverse=True)

#x = sorted(z, key=lambda z: -z[1])
y = [0]*m
#print(x)


for i in range(n):
    for j in range(x[i][0]-1,m):
        if y[j] == 0:
            y[j] = x[i][1]
            break
#    print(y)

answer=0
for i in range(m):
    answer += y[i]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def merge(a_list, b_list):
    res = deque()

    while len(a_list) > 0 and len(b_list) > 0:
        if a_list[0] > b_list[0]:
            res.append(a_list.popleft())
        else:
            res.append(b_list.popleft())


    if len(a_list) > 0:
        res.extend(a_list)
    if len(b_list) > 0:
        res.extend(b_list)

    return res


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

score_list = [[] for i in range(M+1)]


for ab in ab_list:
    if ab[0] <= M:
        score_list[ab[0]].append(ab[1])

scores = [deque() for i in range(M+1)]
for i in range(len(score_list)):
    scores[i] = deque(sorted(score_list[i], reverse=True))
ans = 0
for i in range(0, M+1):
    if len(scores[i]) == 0:
        continue
    ans += scores[i].popleft()
    if i < M and len(scores[i]) > 0:
        scores[i+1] = merge(scores[i], scores[i+1])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

import bisect

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

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

Submission status: Time Limit Exceeded

Solution code:
import logging

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


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(N):
        if i >= M:
            break
        
        if sorted_A_B[i][1] + i <= M and sorted_A_B[i][0] != -1:
            total += sorted_A_B[i][0]
            sorted_A_B[i][0] = -1

        else:
            for k in range(i, N):
                if sorted_A_B[k][1] + i <= M and sorted_A_B[k][0] != -1:
                    total += sorted_A_B[k][0]
                    sorted_A_B[k][0] = -1


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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = {}
for i in range(N):
    a, b = map(int, input().split())
    if a in AB.keys():
        AB[a].append(b)
    else:
        AB[a] = [b]
dp = [0] * (M+1)
for i in range(1, M+1):
    tmp = 0
    km = -1
    tm = -1
    for k in range(i+1):
        if k not in AB.keys():
            continue
        for t in range(len(AB[k])):
            if tmp < AB[k][t]:
                tmp = AB[k][t]
                km = k
                tm = t
    if km >= 0:
        dp[i] = dp[i-1] + tmp
        AB[km][tm] = 0
    else:
        dp[i] = dp[i-1]

print(dp[len(dp)-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
arbs = [tuple(int(v) for v in input().split()) for _ in range(n)]
cands = [[] for _ in range(m)]
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        cands[t].append(arb[1])
rest = []
total_reward = 0
for d, cand in enumerate(reversed(cands)):
    cand = cand + rest
    if len(cand) == 0:
        continue
    valid_max_new_index = -1
    max_rw = 0
    new_cand = []
    for i, rw in enumerate(cand):
        if max_rw <= rw:
            max_rw = rw
            valid_max_new_index = len(new_cand)
        new_cand.append(rw)
    if valid_max_new_index >= 0:
        rw = new_cand.pop(valid_max_new_index)
        rest = new_cand
        total_reward += rw
    else:
        rest = []

print(total_reward)

Submission status: Time Limit Exceeded

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

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


# 日数でソート
ind_sorted = sorted(range(N), key = lambda x:A[x])

tmp_a = 0
tmp_b_ls = [0]
money = 0
for i in range(N):
    if A[ind_sorted[i]] > M:
        break
    if tmp_a != A[ind_sorted[i]]:
        d = A[ind_sorted[i]]-tmp_a
        tmp_b_ls = sorted(tmp_b_ls)[::-1]
        tmp_money = sum(tmp_b_ls[:d])
        tmp_b_ls = tmp_b_ls[d:]
        money += tmp_money
        tmp_a = A[ind_sorted[i]]
    tmp_b_ls.append(B[ind_sorted[i]])

d = M+1-tmp_a
tmp_money = sum(sorted(tmp_b_ls)[::-1][:d])
money += tmp_money

print(money)

Submission status: Time Limit Exceeded

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], x[0]), reverse=True)

jobs = [0 for _ in range(m)]
i_min = 0
for jd in jds:
  if i_min == m:
    break
  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]:
          i_min += 1
          if i_min == m:
            break
        else:
          break
      break
    else:
      i -= 1

print(sum(jobs))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()
jobs = list(map(lambda s:list(map(int,s.split(" "))), sys.stdin.readlines()))

jobs.sort(key=lambda job: job[0])
jobs.sort(key=lambda job: job[1], reverse=True)

# 昇順にソート済みのarrから、n以上の最小の要素を探索して返します。
# 存在しない場合は、Noneを返します。
def bin_gte(arr, n):
    l = 0
    r = len(arr) - 1
    c = (l+r)//2
    while l < r:
        c = (l+r)//2
        if arr[c] >= n:
            r = c
        else :
            l = c+1
    c = max(0, (l+r)//2)
    if arr[c] >= n:
        return (c, arr[c])
    else:
        return (None, None)


mark = [True] * (m+1)

lll = [ i for i in range(m+1)]

ans = 0
for job in jobs:
    nouki = job[0]
    if nouki <= m:

        # nouki以上の最小値をさがす
        i, x = bin_gte(lll, nouki)

        if i == None:
            continue
        
        ans += job[1]

        lll.pop(i)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
cost = defaultdict(list)
for i in range(N):
    A, B = map(int, input().split())
    cost[A].append(B)
    
now = []
ans = 0
for i in range(1, M+1):
    now += cost[i]
    if len(now) != 0:
        max_n = max(now)
        now.remove(max_n)
        ans += max_n
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from sys import stdin

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * N]

    ab = defaultdict(list)
    for a, b in AB:
        ab[a].append(b)

    ans = 0
    reward = []
    for i in range(1, M + 1):
        if ab[i]:
            reward += ab[i]
            reward.sort()
        if reward:
            ans += reward[-1]
            reward.pop()
    print(ans)

input = lambda: stdin.readline()
main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ba = []
m1 = m + 2
check = set()
for _ in range(n):
    a,b = map(int,input().split())
    ba.append([b,a])
ba.sort(reverse=True)
cnt = 0
for BA in ba:
    a1 = BA[1]#a
    b1 = BA[0]#b
    if a1 >= m1:
        continue
    mb = m1
    m1 = a1
    for i in range(m - a1 + 1):
        if a1 + i not in check:
            check.add(a1 + i)
            cnt += b1
            m1 = mb
            break
print(cnt)

Submission status: Time Limit Exceeded

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

l = [list(map(int, input().split())) for i in range(n)]
l.sort()
l.sort(key = lambda x:x[1], reverse = True)

ll = [0 for i in range(m)]

for i in range(m):
    for j in range(len(l)):
        if l[j][0] <= i+1:
            ll[i] = l[j][1]
            del l[j]
            break

print(sum(ll))

Submission status: Time Limit Exceeded

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

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

ab_list = sorted(ab_list, key=lambda x: -x[1])
a_list = sorted(a_list)

c = 0
for i in range(1, m+1):
    if a_list[0] > i:
        continue

    for j, (a, b) in enumerate(ab_list):
        if a <= i:
            c += b
            ab_list.pop(j)
            a_list.pop(0)
            break

print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

def cmp(x, y):
    if x[1] != y[1]:
        return x[1] - y[1]
    return y[0] - x[0]

N, M = map(int, raw_input().split())
l = list()

for i in range(N):
    a, b = map(int, raw_input().split())
    l.append((a,b))

l.sort(cmp=cmp, reverse=True)
#print l
sum = 0
for i in range(1, M+1):
    #print i, l
    subl = [x for x in l if x[0] <= i]
    if subl:
        sum += subl[0][1]
        l.remove(subl[0])

print sum

Submission status: Time Limit Exceeded

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 = []
#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)
        cnt = cnt + C[0]
        #C.remove(max(C))
        del C[0]
    if len(C) > M + 1 - i:
        C = C[:M+1-i]
print(cnt)

Submission status: Time Limit Exceeded

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**6 + 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:
                memo[(i,j)] =  max(dp(i+1,j+1) + b, dp(i,j+1))
                return memo[(i,j)]
        memo[(i,j)] =  dp(i,j+1)
        return memo[(i,j)]
print(dp(0,0))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(100000)

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


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 ia < 0:
            res[j] = b[ib]
            ib -= 1
            continue
        if ib < 0:
            res[j] = a[ia]
            ia -= 1
            continue
        if a[ia] > b[ib]:
            res[j] = a[ia]
            ia -= 1
            # if ia < 0:
            #     return b[:m - j] + res[j:]
                # 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:
            #     return a[:m - j] + res[j:]
                # while True:
                #     if j < 0:
                #         break
                #     res[j] = a[ia]
                #     ia -= 1
                # return res
    return res


# print(merge([1], [1, 2, 3], 3))
# print(merge([1], [1, 2, 3], 1))
# print(merge([1], [1, 2, 3], 5))


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 = []

    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: Time Limit Exceeded

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

baito = []
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    baito.append([a, b])

jobs = sorted(baito, key=lambda x: x[0])
day = [j[0] for j in jobs]
pay = [j[1] for j in jobs]

kane = 0
for i in range(1, m+1):
    pos = bisect.bisect_right(day, i)
    if pos == 0:
        continue
    ind = pay.index(max(pay[:pos]))
    kane += pay.pop(ind)
    day.pop(ind)


print(kane)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())
#  AB.sort(key=lambda x: x[0])
#  perr(AB)
AB_dict = {}
for ab in AB:
    if ab[0] not in AB_dict.keys():
        AB_dict[ab[0]] = [ab[1]]
    else:
        AB_dict[ab[0]].append(ab[1])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()

perr(AB_dict)
"""
貪欲か？
日が長くて報酬の高いものから選んでいく
そうすると
10 1
9 10
みたいなときに10 1のほうから選んでしまうからだめ
残り日数を意識
残ってる中で最も報酬の高いものから？
2 10
1 11
のパターンで、先に1をやってしまうためだめ
2 10
1 11
1 15
のパターンで、1 1をやるのが正解
"""

ans = 0
tmp = []
for i in range(1, M+1):
    # 残りi日
    if i in AB_dict.keys():
        tmp += AB_dict[i]
    #  for j in range(1, i+1):
    #      if j in AB_dict.keys():
    #          tmp += AB_dict[j]
    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue
    max_v = max(tmp)
    ans += max_v
    tmp.remove(max_v)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

for i in range(len(jobs)):
    jobs[i].sort(reverse=True)

# Day Mから考えていく
# Day i には、給料(salary)が最も大きい かつ 支払日(payday)が Day M"以前"のモノを選ぶ。
# ただし、複数ある場合は、最もpaydayが大きいモノを選ぶ。

total = 0
for i in range(M, 0, -1):   # 1 〜 M
    # print("Day", i)
    max_salary = 0
    # print("Max payday =", M - i + 1)
    for j in range(1, M - i + 1 + 1):
        if jobs[j]:
            if max_salary <= jobs[j][0]:
                max_salary = jobs[j][0]
                max_payday = j

    if max_salary:
        total += max_salary
        # print("Earn ", max_salary)
        del(jobs[max_payday][0])

print(total)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
ABs = [0] * N

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

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

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            count += 1
        else:
            for i in range(day, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N, M= map(int, input().split())
B=[]
for i in range(N):
    B.append([None]*2)
    l=input().split()
    B[i][0]=int(l[1])
    B[i][1]=int(l[0])
B.sort(reverse=True)
h=[0]*(M+1)
a=0
for i in range(N):
    for j in range(B[i][1],M+1):
        if h[j]==0:
            h[j]=1
            a+=B[i][0]
            break
print(a)

Submission status: Time Limit Exceeded

Solution code:
# ABC 137, d
from operator import itemgetter

n, m = [int(el) for el in input().split(' ')]
X = []
for i in range(n):
    a, b =  [int(el) for el in input().split(' ')]
    X.append((a, b))

total = 0
for i in range(m):
    X = sorted(X, key = itemgetter(1, 0), reverse = True)
    for x in X:
        if x[0] + i <= m:
            total += x[1]
            X.remove(x)
            break
print(total)

Submission status: Time Limit Exceeded

Solution code:
class work(object):
    def __init__(self, nums):
        self.a = nums[0]
        self.b = nums[1]
        self.is_used = False

    def __repr__(self):
        return "({}, {})".format(self.a, self.b)

    def __lt__(self, other):
        if self.a == other.a:
            return self.b > other.b
        return self.a < other.a


(n, m) = map(int, input().split())
works = []
for _ in range(n):
    works.append(work(list(map(int, input().split()))))
sorted_works = sorted(works)

sum = 0
for i in range(1, m + 1):
    index = 0
    for j, w in enumerate(sorted_works):
        if i < w.a:
            break
        index += 1
    if 0 == index:
        continue
    max_index = 0
    max_reward = 0
    for j in range(index):
        if (not sorted_works[j].is_used) and (max_reward < sorted_works[j].b):
            max_index = j
            max_reward = sorted_works[j].b
    sum += max_reward
    sorted_works[max_index].is_used = True

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n,d = list(map(int, input().split(" ")))

ws = []
for _ in range(n):
    l,r = list(map(int, input().split(" ")))
    if l <= d:
        ws.append((l,r))

wn = len(ws)

got = 0
chosen = []
for i in range(d):
    j = d-i
    candi_k = 0
    candi_r = 0
    candi_t = 0
    for k in range(wn):
        t = ws[k][0]
        r = ws[k][1]
        if  t <= j and candi_t <= t and candi_r <= r and not k in chosen:
            candi_k = k
            candi_r = r
            candi_t = t
    chosen.append(candi_k)
    got += candi_r

print(got)

Submission status: Time Limit Exceeded

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
import sys
sys.setrecursionlimit(10**5)
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: Time Limit Exceeded

Solution code:
import numpy as np
import math
N,M = map(int,input().split())
ls = []
for n in range(N):
  ls.append(list(map(int,input().split())))
ls = np.array(ls)
idx = np.argsort(ls[:,1])[::-1]
#print (ls[idx])
days = list(range(1,M+1))
days = {k: 0 for k in days}
#print (days)
sum = 0
skip_d = -1
for work in ls[idx]:
  d = work[0]
  if d==skip_d:
    pass
  else:
    while(d<=M):
      if d in days:
        sum+=work[1]
        days.pop(d)
        d=M+1
        skip_d = -1
      else:
        d+=1
        skip_d = work[0]
print (sum)

Submission status: Time Limit Exceeded

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

lists = [[] for _ in range(10**5 + 1)]
availables = []
for A, B in ABs:
    bisect.insort(lists[A], B)
    
    ans = 0
for i in range(1, M + 1):
    for b in lists[i]:
        bisect.insort(availables, b)
    if availables:
        ans += availables.pop()

print(ans)

Submission status: Time Limit Exceeded

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

jobs = [list(map(int, input().split())) for i in range(n)]
jobs.sort(key=lambda x: (x[0], -x[1]))

reward = 0

for i in range(m):
    rewardful_jobs = [job for job in jobs if job[0] <= i + 1]
    if len(rewardful_jobs) > 0:
        rewardful_jobs.sort(key=lambda x: -x[1])
        reward += rewardful_jobs[0][1]
        jobs.remove(rewardful_jobs[0])

print(reward)

Submission status: Time Limit Exceeded

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

ans = 0
MAX = 10 ** 5 + 1
schedule = [i for i in range(M + 1)]
BA.sort(reverse=True)
x = None
for b, a in BA:
    if a < M:
        if schedule[a] == MAX:
            x = min(schedule[a+1:])
            if x == MAX:
                continue
        else:
            x = a
    elif a == M and schedule[a] != MAX:
        x = a
    else:
        continue
    schedule[x] = MAX
    ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    for l in DV:
        l.sort(reverse=True)
    ans = 0
    tmpL = []
    for i in range(1,M+1):
        tmpL += DV[i][:M-i+1]
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())
#  AB.sort(key=lambda x: x[0])
#  perr(AB)
AB_dict = {}
for ab in AB:
    if ab[0] not in AB_dict.keys():
        AB_dict[ab[0]] = [ab[1]]
    else:
        AB_dict[ab[0]].append(ab[1])
for k in AB_dict.keys():
    AB_dict[k].sort()

perr(AB_dict)
"""
貪欲か？
日が長くて報酬の高いものから選んでいく
そうすると
10 1
9 10
みたいなときに10 1のほうから選んでしまうからだめ
残り日数を意識
残ってる中で最も報酬の高いものから？
2 10
1 11
のパターンで、先に1をやってしまうためだめ
2 10
1 11
1 15
のパターンで、1 1をやるのが正解
"""

ans = 0
tmp = []
for i in range(1, M+1):
    # 残りi日
    if i in AB_dict.keys():
        tmp += AB_dict[i]
    #  for j in range(1, i+1):
    #      if j in AB_dict.keys():
    #          tmp += AB_dict[j]
    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue
    tmp.sort()
    ans += tmp[-1]
    tmp.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def merge(s1, s2):
    ls1 = len(s1)
    ls2 = len(s2)
    i1 = 0
    i2 = 0
    ans = []
    while (i1 < ls1 and i2 < ls2):
        if s1[i1] < s2[i2]:
            ans.append(s1[i1])
            i1 += 1
        else:
            ans.append(s2[i2])
            i2 += 1
    for i in range(i1, ls1):
        ans.append(s1[i])
    for i in range(i2, ls2):
        ans.append(s2[i])
    return ans


import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        bisect.insort_left(ABs[A], B)

As = 0
for i in range(M + 1):
    if i > 0:
        ABs[0] = merge(ABs[0], ABs[i])
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)