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:
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)
crr = AB[0][0]
AB_dict = {}
AB_dict[crr] = []
for ab in AB:
    if ab[0] != crr:
        crr = ab[0]
        AB_dict[crr] = [ab]
    else:
        AB_dict[crr].append(ab)
perr(AB_dict)

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

ans = 0
for i in range(1, M+1):
    # 残りi日
    tmp = []
    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(key=lambda x: x[1])
    ans += tmp[-1][1]
    AB_dict[tmp[-1][0]].remove(tmp[-1])
print(ans)

Submission status: Time Limit Exceeded

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

d = dict()
key_all = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    if a not in key_all:
        d[a] = [b]
        key_all.append(a)
    else:
        d[a].append(b)

key_all.sort()

ans = 0
l = []
import bisect

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                bisect.insort(l, v)

            key_all.pop(0)

    # print(l)

    if l != []:
        ans += l.pop()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect



def main():
    num, max_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x:(-x[1]))
    # for


    visit = [0 for i in range(max_num + 1)]

    ans = 0
    # print(data)
    for i in range(num):
        day, value = data[i]
        ind_lim = day
        try:
            ind_insert = visit[ind_lim:].index(0)
            visit[ind_insert + ind_lim] = 1
            ans += value
        except:
            pass
        # print(visit)

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
num, day = [int(x) for x in input().split()]

worklist = [[] for i in range(day+4)]

wd = {}

for i in range(num):
  d, m = [int(x) for x in input().split()]
  if d <= day:
    worklist[d-1].append(m)
  if d-1 in wd.keys():
    wd[d-1].append(m)
  else:
    wd[d-1] = [m]

ans = 0

canworklist = []

workday = wd.keys()

for i in range(day):
  if i in workday:
    canworklist += wd[i]
    canworklist.sort(reverse=True)
  if canworklist:
    ans += canworklist.pop(0)
  
print(ans)

#print(wd)

Submission status: Time Limit Exceeded

Solution code:
N,limit = [int(x) for x in input().split()]
dvs = [[int(x) for x in input().split()] for _ in range(N)]
dvs = sorted(dvs, key = lambda x: (x[0], -x[1]))
res = []
for i in range(1,limit+1):
    a = [0,0]
    idx = -1
    for j,dv in enumerate(dvs):
        if not dv or dv[0]>i:
            break
        if dv[0]<=i:
            if a[1]<dv[1]:
                a = [dv[0],dv[1]]
                idx = j
    res.append(a)
    if idx>=0 and dv:
        del dvs[idx]
ans = 0
for k,v in res:
    ans +=v
print(ans)

Submission status: Time Limit Exceeded

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

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

for l in d.values():
    l.sort()


ans = 0
for i in range(1,M+1):
    mx_a = None
    mx_b = 0
    for j in range(1, i+1):
        if j in d and d[j]:
            mx_b = max(mx_b, d[j][-1])
            mx_a = j
    if mx_a is not None:
        ans += mx_b
        d[mx_a].pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    jobs_time = collections.defaultdict(list)
    for a,b in zip(A,B):
        jobs_time[b].append(a)

    jobs_time = sorted(jobs_time.items(),reverse=True)
    job_list = [0] * M

    for k,v in jobs_time: 
        v.sort()
        st = -1
        for vv in v:
            if vv <= M:
                for i in range(max(st,vv-1),len(job_list)):
                    if job_list[i] < k:
                        job_list[i] = k
                        st = min(i+1,len(job_list))
                        break
            else:
                break

        if all(j>0 for j in job_list):
            break

    print(sum(job_list))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
s = dict()
for i in range(0,n):
    a = list(map(int,input().split()))
    if not a[0] in s:
        s[a[0]] = list([a[1]])
    else:
        s[a[0]].append(a[1])

w = list()
ans = 0
for i in range(1,m+1):
    if i in s:
        w.extend(s[i])
        w.sort()
    if w != []:
        ans += w[-1]
        del w[-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)
for i in range(M + 1):
    ABs[i].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N, M = [int(x) for x in input().split()]
AB = []
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    AB.append((A, B))

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

ans = 0
used = set()
for m in range(M, -1, -1):
    for i in range(N):
        a, b = AB[i]
        if a + m <= M and i not in used:
            ans += b
            used.add(i)
            # print("m:{}, a:{},b{}".format(m, a, b))
            break

print(ans)

Submission status: Time Limit Exceeded

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

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

money = 0

# for A, B in sorted_AB_list:
#  print(A, B)

# 最終日から逆算
for i in range(M): # 残り日数
  remain_days = i+1
  
  for A, B in sorted_AB_list:
    if A <= remain_days:
      money += B
      sorted_AB_list.remove((A, B))
      break
      
print(money)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from bisect import insort
from copy import copy

n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    sub = d[i]
    if len(sub) > 0:
        for j in range(len(sub)):
            insort(resList, sub[j])
    if len(resList) > 0:
        res += resList[-1]
        resList.pop()

print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
n, m = map(int, input().split())
works = [[] for _ in range(10**5+1)]
for i in range(n):
    a, b = map(int, input().split())
    works[a].append(b)
reward = 0
now_works = [0 for _ in range(10**4+1)]
max_kingaku = 0
for i in range(m+1):
    for kingaku in works[i]:
        now_works[kingaku] += 1
        if kingaku > max_kingaku:
            max_kingaku = kingaku
    if max_kingaku == 0:
        continue
    reward += max_kingaku
    now_works[max_kingaku] -= 1
    if now_works[max_kingaku] == 0:
        for j in reversed(range(1, max_kingaku)):
            if now_works[j] > 0:
                max_kingaku = j
                break
        else:
            max_kingaku = 0
print(reward)

Submission status: Time Limit Exceeded

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

import sys

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        cur+= ref
        cur.sort()
    #
    if not cur: continue
    tot+= cur.pop()
#
print( tot )

Submission status: Time Limit Exceeded

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

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

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

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s = s[:a] + s[a+1:]
    ret += b
    if not s :
        break
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]
 
answer = 0
tmp = deque()
 
for i in range(M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = deque(C[i])
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        elif len(right) != 0:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, key=lambda x: x[1], reverse=True)

    free_day = set(list(range(m + 1)))
    answer = 0
    for i in range(n):
        a = ab[i][0]
        b = ab[i][1]
        work_days = {day for day in free_day if m-day >= a}
        if len(work_days) != 0:
            free_day.remove(max(work_days))
            answer += b
    print(answer)

Submission status: Time Limit Exceeded

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 = max([i for i, j in enumerate(a_list_2[:k + 1]) if max(a_list_2[:k + 1]) == j])
        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: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
ab.sort(key = lambda x:x[1] ,reverse = True)
# print(ab)
f = [True]*m
ans=0
for i in range(n):
    # print(f)
    if ab[i][0]>m:
        continue
    else:
        k=m-ab[i][0]
        while f[k]==False:
            k-=1
            if k<0:
                break
        if k<0:
            continue
        f[k]=False
        ans+=ab[i][1]
print(ans)

Submission status: Time Limit Exceeded

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]*M
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: 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=[]
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]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = [0 for _ in range(n)]
B = [0 for _ in range(n)]

d = {}

for i in range(n):
    a,b = map(int,input().split())
    A[i] = a
    B[i] = b
    if(a in d):d[a].append(b)
    else:d[a] = [b]
al = np.array(sorted(list(set(A))))

c = 0
for i in range(0,m)[::-1]:
    rem_day = m - i
    tmp = al[al <= rem_day]
    ma = -1
    idx = -1
    idx2 = -1
    for j in tmp[::-1]:
        if(len(d[j])==0):continue
        if(max(d[j]) > ma):
            ma = max(d[j])
            idx = j
            idx2 = d[j].index(ma)
    if(idx != -1 and idx2 != -1):c += d[idx].pop(idx2)


print(c)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
ba = []
for _ in range(n):
    a, b = map(int, input().split())
    ba.append([b, a])
ba.sort(reverse=True)
days = [x for x in range(m)]
ans = 0
for x in ba:
    a = x[1]
    b = x[0]
    lim = m - a
    d = bisect_right(days, lim)
    if d > 0:
        ans += b
        days = days[:d-1] + days[d:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
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: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = deque()

for i in range(M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = deque(C[i])
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        elif len(right) != 0:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn==M-ab[0]-i:
                break
            if D[M-ab[0]-i]==0:
                D[M-ab[0]-i]+=1
                pay+=ab[1]
                flag=False
                break
            else:
                i+=D[M-ab[0]-i]

        if flag:
            mn=M-ab[0]
            
print(pay)

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    rewards = sorted([x for x in baito if x[0] + i <= M and x[2] == 0], key=lambda x: (-x[1], -x[0]))
    if rewards:
        max_reward = rewards[0]
        max_reward[2] = 1
        if i == 0:
            dp[i] = max_reward[1]
        else:
            dp[i] = dp[i-1] + max_reward[1]
    else:
        if i == 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]

print(dp[M-1])

Submission status: Time Limit Exceeded

Solution code:
# ABC137d
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

dp = dict()


def hataraku(sigoto, day):
    if (day == 0 or sigoto >= len(a)):
        return 0
    if (dp.get((sigoto, day)) != None):
        return dp[(sigoto, day)]
    if (day >= a[sigoto][0]):
        # print(str(sigoto)+"とる")
        t = max(a[sigoto][1] + hataraku(sigoto + 1, day - 1),
                hataraku(sigoto + 1, day))
        # print(t)
        dp[(sigoto, day)] = t
        return t
    # print(str(sigoto)+"とらない")
    t = hataraku(sigoto + 1, day)
    dp[(sigoto, day)] = t
    return t


print(hataraku(0, m))

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
s = dict()
for i in range(0,n):
    a = list(map(int,input().split()))
    if not a[0] in s:
        s[a[0]] = list([a[1]])
    else:
        s[a[0]].append(a[1])

w = list()
ans = 0
for i in range(1,m+1):
    if i in s:
        w.extend(s[i])
    if w != []:
        ans += max(w)
        del w[w.index(max(w))]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M=map(int,input().split())
A,B=[],[]
hi_re=collections.defaultdict(list)
for i in range(N):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
    hi_re[a].append(b)

dp=[0]*(M+1)
res=list()

for i in range(1,M+1):
    res.extend(hi_re[i])
#    print(res)
    if len(res) != 0:
        m = max(res)
        dp[i]=dp[i-1]+m
        res.remove(m)
    else:
        dp[i]=dp[i-1]

print(dp[M])

Submission status: Time Limit Exceeded

Solution code:
N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
    
days_limit = M

jobs = AB[:]
jobs  =sorted(jobs, key=lambda x: x[1], reverse=True)
#print(jobs)

plan = [0] * (days_limit+1)

for d, r in jobs:
    while not d > days_limit:
        if plan[d] == 0:
            plan[d] = r
            break
        else:
            d += 1
#print(plan)
print(sum(plan))

Submission status: Time Limit Exceeded

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

not_done = [True for _ in range(M)]

for A, B in pairs:
    for i in range(M-A, -1, -1):
        if not_done[i]:
            out += B
            #print(A, B)
            not_done[i] = False
            break

print(out)

Submission status: Time Limit Exceeded

Solution code:

n, m = list(map(int, input().split()))
ab = []
for _ in range(n):
    ai, bi = list(map(int, input().split()))
    ab.append([ai,bi])
    
ab.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)

day = [0]*(m+1)
cnt = 0
for abi in ab:
    if abi[0] <= m:
        if day[m-abi[0]] == 0:
            day[m-abi[0]] = 1
            cnt += abi[1]
        else:
            i = 1
            while m-abi[0]-i>=0:
                if day[m-abi[0]-i] == 0:
                    day[m-abi[0]-i] = 1
                    cnt += abi[1]
                    break
                i += 1
print(cnt)

Submission status: Time Limit Exceeded

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

ab.sort()

answer = 0
j = 0
for i in range(1,m+1):
    max = 0
    while j < n:
        if ab[j][0] <= i:
            j += 1
        else:
            break
    if j != 0:
        for k in range(j):
            if max < ab[k][1]:
                max = ab[k][1]
                max_index = k
        answer += max
        del ab[max_index]
        j -= 1
        n -= 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
# ABC137d
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def hataraku(sigoto, day):
    if (day == 0 or sigoto >= len(a)):
        return 0
    if (day >= a[sigoto][0]):
        # print(str(sigoto)+"とる")
        t = max(a[sigoto][1] + hataraku(sigoto + 1, day - 1),
                hataraku(sigoto + 1, day))
        # print(t)
        return t
    # print(str(sigoto)+"とらない")
    t = hataraku(sigoto + 1, day)
    return t


print(hataraku(0, m))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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])

ans = 0
for i in range(0, M+1):
    if len(score_list[i]) == 0:
        continue
    score_list[i].sort(reverse=True)
    ans += score_list[i].pop(0)
    if i < M and len(score_list[i]) > 0:
        score_list[i+1].extend(score_list[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    ab = sorted(ab, key=lambda x: x[1], reverse=True)

    free_day = set(list(range(m + 1)))
    answer = 0
    for i in range(n):
        max_free_day = max(free_day)
        a = ab[i][0]
        b = ab[i][1]
        work_days = [day for day in free_day if m-day >= a]
        if len(work_days) != 0:
            free_day.remove(max(work_days))
            answer += b
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
def main():
    inp = input().split(' ')
    n = int(inp[0])
    m = int(inp[1])
    ms = list(range(1, m+1))
    baitos = []
    count = 0
    for i in range(n):
        inpt = input().split(' ')
        a = int(inpt[0])
        b = int(inpt[1])
        baitos.append({'a': a, 'b': b})
    baitos.sort(key=lambda x: x['b'])
    baitos.reverse()

    for baito in baitos:
        if decide_day(baito['a'], ms) is None:
            continue
        count += baito['b']
    print(count)


def decide_day(a, ms):
    if len(ms) == 0 or max(ms) < a:
        return None
    elif a in ms:
        ms.remove(a)
        return a
    else:
        return decide_day(a+1, ms)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB_list = [tuple(map(int, input().split())) for i in range(N)]
               
# print(AB_list)
# sorted_AB_list = sorted(AB_list, key=lambda x:x[0], reverse=True)
# sorted_AB_list = sorted(sorted_AB_list, key=lambda x:x[1], reverse=True)

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

# for A, B in sorted_AB_list:
#   print(A, B)

money = 0

# 最終日から逆算して考える
for i in range(M): # 残り日数
  remain_days = i+1
  
  for A, B in sorted_AB_list:
    if A <= remain_days:
      # print(A, B)
      money += B
      sorted_AB_list.remove((A, B))
      break
      
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], reverse=True)

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

print(sum(jobs))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from bisect import insort
from copy import copy

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

res = 0
resList = []
for i in range(1, m+1):
    resList.extend(d[i])
    if len(resList) > 0:
        resList.sort()
        res += resList[-1]
        resList.pop()

print(res)

Submission status: Time Limit Exceeded

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

ans=0

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

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

scadule = [0]*M
for work in reversed(BA):
    i=M-work[0]
    while i>=0:
        if scadule[i]==0:
            scadule[i]=work[1]
            break
        i-=1

ans=sum(scadule)

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

# input
n,m = [int(x) for x in stdin.readline().rstrip().split()]
r = {}
#a = []
#b = []
for i in range(n):
    tmp = [int(x) for x in stdin.readline().rstrip().split()]
    if tmp[0] not in r:
        r[tmp[0]] = []
    r[tmp[0]].append(tmp[1])
    #a.append(tmp[0])
    #b.append(tmp[1])

result = 0
for i in range(m):
    v = 0
    tmp_key = None
    tmp_i = None
    for j in range(i+1):
        l = j+1
        if l in r:
            if max(r[l]) > v:
                tmp_key = l
                tmp_i = r[l].index(max(r[l]))
                v = r[l][tmp_i]
    if tmp_key is not None:
        del r[tmp_key][tmp_i]
        if len(r[tmp_key]) == 0:
            del r[tmp_key]
        result += int(v)

print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(N)]
arr.sort()
ans = 0
tmpmax = 0
tgt = 0
for remday in range(1, M + 1):
        for idx,val in enumerate(arr):
                if val[0] > remday:
                        break
                if val[1] > tmpmax:
                        tmpmax = val[1]
                        tgt = idx
        if tmpmax > 0:
                ans += tmpmax
                tmpmax = 0
                del arr[tgt]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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[1], reverse = True)
    A.sort(key=lambda x: x[0])

    L = []
    c = 0
    E = 0
    F = 1
    for i in range(M):
        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: 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([a, b])
A = sorted(A, key = lambda x : (x[1], x[0]), reverse = True)
# print(A)
ans = 0

for i in range(M - 1, -1, -1):
    for j in range(len(A)):
        if A[j][0] <= M - i:
            ans += A[j][1]
            A.pop(j)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num, day = [int(x) for x in input().split()]

worklist = [[] for i in range(day+4)]

for i in range(num):
  d, m = [int(x) for x in input().split()]
  if d <= day:
    worklist[d-1].append(m)

ans = 0

canworklist = []

for i in range(day):
  if worklist[i]:
    canworklist += worklist[i]
    canworklist.sort(reverse=True)
    
  if canworklist:
    ans += canworklist.pop(0)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

AB = []

for i in range(N):

    A,B = map(int,input().split())

    AB.append([A,B])

AB.sort()


day = 1
i = 0
maxi = []
ans = 0

while day <= M:

    if i < N and AB[i][0] == day:

        ind = bisect.bisect_left(maxi,AB[i][1])
        maxi.insert(ind,AB[i][1])
        i += 1
        
    else:

        day += 1
        if len(maxi) > 0:
            ans += maxi.pop(-1)

print (ans)