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:
n, m = map(int, input().split())
a = []
b = []
 
for i in range(n):
    tmp0, tmp1 = map(int, input().split())
    a.append(tmp0)
    b.append(tmp1)
    
import numpy as np
x = np.array(a)
y = np.array(b)
order = np.argsort(-y)
x_sorted = list(x[order])
y_sorted = list(y[order])
 
used = [0 for _ in range(n)]
 
res = 0
for day in range(m, 0, -1):
    thres = m - day + 1
    for i in range(len(x_sorted)):
        if x_sorted[i] <= thres:
            used[i] = 1
            res += y_sorted[i]
            x_sorted.pop(i)
            y_sorted.pop(i)
            break
print(res)

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(m):
  dic[i+1] = i+1
ans = 0
mset = set([i+1 in range(m)])
for a, b in ab:
  if a <= m:
    while(True):
      if a in dic:
        if dic[a] == a:
          ans += b
          if a in mset:
            mset.remove(a)
          dic[a] += 1
          break
        else:
          a = dic[a]
      else:
        break
  if len(mset) == 0:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect



 
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
 
ab.sort()
ab.append([1000000,0])
 
t = 0
x = []
ans = 0

bi = bisect.bisect_left
xi = x.insert
xp = x.pop

for i in range(1,m+1):
    while True:
        if ab[t][0] > i:
            break
        index = bi(x, ab[t][1])
        xi(index, ab[t][1])
        t += 1
    
    if len(x) != 0:
        ans += xp(len(x) - 1)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = []
for _ in range(n):
   a,b = map(int, input().split())
   A.append((b, a))
A.sort()
w = [0]*m
for a in reversed(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:
import sys
input = sys.stdin.readline

def main():
    n,m = map(int,input().split())
    money = [[] for _ in range(10**5)]
    dp = [0] * m

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

    max1 = []
    for i in range(m):
        max1 += money[i]
        if max1:
            dp[i] = max1.pop(max1.index(max(max1)))
        if i >= 1:
            dp[i] += dp[i-1]

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
ans=0
for i in range(n):
  x,y=map(int,input().split())
  a.append(x)
  b.append(y)
for j in range(m):
  c=[i for i, x in enumerate(a) if x<=j+1]
  d=[b[x] for x in c]
  if(d != []):
    e=max(d)
    ans+=e
    f=d.index(e)
    g=c[f]
    del a[g]
    del b[g]
print(ans)

Submission status: Time Limit Exceeded

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

reward = [0] * M

D2J = {}

for i in range(N):
    a, b = map(int, input().split(' '))
    d = max(0, M-a+1)
    if d not in D2J:
        D2J[d] = []
    D2J[d].append(b)

ans = 0
candidate = []
for j in reversed(range(1, M+1)):
    if j in D2J:
        candidate += D2J[j]
    if not candidate:
        continue
    r = max(candidate)
    i = candidate.index(r)
    candidate[i] = 0
    ans += r
print(ans)

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:tuple(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)


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 = lll[:i] + lll[i+1:]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0][0]
    su = [x[0]]
    for i in range(len(x)-1):
        if aa != x[i+1][0]:
            a.append(su)
            aa = x[i+1][0]
            su = [x[i+1]]
        else:
            su.append(x[i+1])
    a.append(su)
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

def binary_search_recursion(a,b):

    arry = a
    target = b
    arry_len = len(arry) 

    def recursion(left=0,right=arry_len-1):

        if left > right:
            return print("not found")

        mid = (left+right) // 2
        if arry[mid] > target:
            return recursion(left,mid-1)
        elif arry[mid] < target:
            return recursion(mid+1,right)
        else:
            return print("found: " + str(mid+1) + " 番目にありました")

    recursion()

n,m = l()

a = []

for i in range(n):
    z,x = l()
    a.append([z,x])

a.sort(key = lambda x:(x[0],-x[1]))
kkk = s(a)
co = 0
p = 0
al = []
for i in range(m):
    k = i + 1
    if p <= len(kkk)-1:
        if k >= kkk[p][0][0]:
            for ppp in kkk[p]:
                al.append(ppp[1])
            p += 1
    al.sort(reverse = True)
    if len(al) != 0:
        an = al.pop(0)
        co += an 
print(co)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
dic = {}
for _ in range(N):
    a,b = map(int,input().split())
    if a > M:
        pass
    else:
        if a in dic.keys():
            dic[a].append(b)
        else:
            dic[a] = [b]
lis = [[]] * M
for p in dic.keys():
    lis[M-p] = dic[p]
g = 0
for j in range(M):
    id = 0
    m =  0
    for w,k in enumerate(lis[j:]):
        if k != []:
            if m < max(k):
                m = max(k)
                id = w
    if m != 0:
        g += m
        lis[id+j].remove(m)
print(g)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
data = [[] for i in range(m+1)]
for i in range(n):
    tmp = []
    a, b = map(int, input().split(" "))
    if a <= m:
        data[a].append(b)

for i in range(m+1):
    data[i].sort()

money = 0
for i in range(1,m+1):
    taisyo = data[1:i+1]
    max = 0
    memo = 0
    for index in range(i):
        if not taisyo[index] == []:
            if taisyo[index][-1] > max:
                profit = taisyo[index][-1]
                max = profit
                memo = index
    if not max == 0:
        taisyo[memo].remove(profit)
        money += profit

print(money)

Submission status: Time Limit Exceeded

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

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
full=0
for work in reversed(BA):
    if work[0]>M:
        continue
    if full == M:
        break
    if (0 in scadule[work[0]-1:]):
        day = scadule[work[0]-1:].index(0)
        scadule[day+work[0]-1] = work[1]
        full+=1

ans=sum(scadule)

print(str(ans))

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])

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):

    max_idx = -1
    max_n = -1
    for j in range(i+1):
        if len(scores[j]) == 0:
          continue
        if max_n < scores[j][0]:
            max_n = scores[j][0]
            max_idx = j

    if max_idx > 0:
        ans += scores[max_idx].popleft()

print(ans)

Submission status: Time Limit Exceeded

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,reverse=True)
ans = 0
for i in range(N):
  k = len(job_list)
  for j in range(k):
    if i+job_list[j][0] <= M:
      if job_list[j] == max(job_list,key=itemgetter(1)) or (job_list[j][0]!=max(job_list,key=itemgetter(1))[0] and job_list[j][1]>=max(job_list,key=itemgetter(1))[1] and i+max(job_list,key=itemgetter(1))[0]>M):
        ans += job_list[j][1]
        job_list.remove(job_list[j])
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def max_acc(m, alist):
    max = 0
    i = -1
    id = -1
    for index, a in enumerate(alist):
        if a[0] <= m:
            if a[1] >= max:
                if a[0] >= id:
                    max = a[1]
                    i = index
                    id = a[0]
    return i

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

total = 0
for i in reversed(range(1, m +1)):
    index = max_acc(i, a)
    if index != -1:
        item = a.pop(index)
        total += item[1]
print(total)

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,(t,r) in enumerate(ws):
        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())
dp = [[0 for i in range(M+1)] for j in range(N+1)]
l = [0 for i in range(N)]
for i in range(N):
    A,B = map(int, input().split())
    l[i] = [-A, -B]
l.sort()
for n in range(1, N+1):
    for m in range(n):
        if -l[n-1][0]  + m <= M:
            dp[n][m] = max(dp[n][m], dp[n-1][m-1] - l[n-1][1])
        dp[n][m-1] = max(dp[n][m-1], dp[n-1][m-1])
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

jobs = {}

for i in range(N):
  d, r = map(int, input().split())
  
  if d not in jobs:
    jobs[d] = []  
  heapq.heappush(jobs[d], -r)
  
sum_rew = 0

for i in range(1, M + 1):
  max_reward = 0
  rew_index = 0
  for d in range(1, i + 1):
    if d not in jobs:
      continue
    
    if -jobs[d][0] > max_reward :
      max_reward = -jobs[d][0]
      rew_index = d
      
  if not max_reward:
    continue
  
  heapq.heappop(jobs[rew_index])
  if not jobs[rew_index]:
    del jobs[rew_index]
    
  sum_rew += max_reward

print(sum_rew)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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

    
job_que = []
total = 0
for j in range(1, m+1):
    job_que.extend(m_dict[j])
 
 
    if job_que:
        job_que.sort()
        total += job_que.pop()
        
    
            
print(total)

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
flag = False
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
        flag = True
      else:
        d+=1
    if not flag:
      skip_d = work[0]
      flag = False
print (sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.zeros(n,dtype=np.int32)
B = np.zeros(n,dtype=np.int32)
idx = np.zeros(n,dtype=np.int32)
F = np.zeros(n,dtype=np.int16)


for i in range(n):
    a,b = map(int,input().split())
    A[i] = a
    B[i] = b
    idx[i] = i
    

idx_s = np.argsort(A)
A = A[idx_s]
B = B[idx_s]

c = 0
for i in range(0,m)[::-1]:
    rem_day = m - i
    bool1 = (A <= rem_day) & (F == 0)
    A_tmp = A[bool1]
    if(len(A_tmp)==0):continue
    B_tmp = B[bool1]
    idx_tmp = idx[bool1]
    max_idx = np.argmax(B_tmp)
    F[idx_tmp[max_idx]] = 1
    c += B_tmp[max_idx]
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 copy

def get_greedy_pay(arbeits, dones, worklen):
    works = arbeits.get(worklen, [])
    done = dones.get(worklen, 0)
    if len(works) <= done:
        return -999
    else:
        return works[done]

counts, maxday = map(int, input().split())
arbeits = {}
days = set()

for i in range(counts):
    a, b = map(int, input().split())
    adays = arbeits.get(a, [])
    adays.append(b)
    adays.sort(reverse=True)
    #print("{}".format(adays))
    arbeits[a] = adays
    days.add(a)

#print("{}".format(arbeits))


rewards = [0]
plans = [{}]
for i in range(maxday):
    day = i + 1
    candlen = -1
    max_pay = -1
    for worklen in days:
        candday = day - worklen
        if candday >= 0:
            pay = get_greedy_pay(arbeits, plans[day-1], worklen)
            if max_pay < pay:
                max_pay = pay
                candlen = worklen
    if max_pay > 0:
        plan = copy.copy(plans[day-1])
        plan[candlen] = plan.get(candlen, 0) + 1
        plans.append(plan)
        reward = rewards[day - 1]
        reward = reward + max_pay
        rewards.append(reward)
    else:
        plan = copy.copy(plans[day-1])
        plans.append(plan)
        reward = rewards[day-1]
        rewards.append(reward)
    #print("{}".format(rewards))
    #print("{}".format(plans))

print("{}".format(rewards[maxday]))

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:tuple(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)


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:
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
ab = [[-1, -1] for i in range(N)]
for i in range(N):
    ab[i] = list(map(int, input().split()))

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

day_list = [False] * M
ans = 0
for i in range(N):
    a, b = ab_sorted[i]
    for j in range(a - 1, M):
        if not day_list[j]:
            day_list[j] = True
            ans += b
            break

print(ans)

Submission status: Time Limit Exceeded

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

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

A.sort(key = lambda x:-x[1])
A.sort(key = lambda x:x[0])

arr = [[0 for i in range(N)] for j in range(M)]

cnt = 0
for i in range(N):
    if i != 0:
        if A[i][0] != A[i-1][0]:
            cnt = 0
        else:
            cnt += 1
    if A[i][0]-1 < M:
        arr[A[i][0]-1][cnt] = A[i][1]


ans = arr[0][0]
del arr[0][0]
for i in range(1, M):
    res = 0
    num = 0
    for j in range(i+1):
        if res < arr[j][0]:
            res = arr[j][0]
            num = j
    del arr[num][0]
    ans += res

print(ans)
# for i in range(M):
#     print(arr[i])

Submission status: Time Limit Exceeded

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


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

def solve2(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((b,a))

    jobs_time = sorted(jobs_time,key=itemgetter(0,1),reverse=True)
    job_list = [0] * M
    job_cnt = 0
    res = 0
    for b,a in jobs_time: 
        if a <= M:
            for i in range(a-1,len(job_list)):
                if job_list[i] < b:
                    if job_list[i] == 0:
                        job_cnt += 1
                    else:
                        res -= job_list[i]
                    job_list[i] = b
                    res += b
                    break
        if job_cnt >= len(job_list):
            break

    print(res)


# 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))
    solve2(N, M, A, B)

if __name__ == '__main__':
    main()

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)] 

z = sorted(x,key=itemgetter(0))
x = sorted(z,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:
n,m = map(int,input().split())
ab = {i:[] for i in range(1,m+1)}
for i in range(n):
    a,b = map(int,input().split())
    if a in ab:
        ab[a].append(b)
    else:
        ab[a] = [b]
ab = {i:sorted(ab[i],reverse=True) for i in ab}
#print(ab)
ans = 0
for i in range(m)[::-1]:
    rem = m - i
    #print("rem=",rem,"ab[rem]=",ab[rem])
    mx = 0
    fl = -1
    for j in range(1,m-i+1):
        #print("j=",j)
        if ab[j] and mx < ab[j][0]:
            mx = ab[j][0]
            fl = j
            #print("fl=",fl)
    ans += mx
    if fl > 0: del ab[fl][0]
    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(m):
  dic[i+1] = i+1
ans = 0
for a, b in ab:
  if a <= m:
    while(True):
      if a in dic:
        if dic[a] == a:
          ans += b
          dic[a] += 1
          break
        else:
          a = dic[a]
      else:
        break
print(ans)

Submission status: Time Limit Exceeded

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

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
full=0
for work in reversed(BA):
    if work[0]>M:
        continue
    try:
        day = scadule[work[0]-1:].index(0)
        scadule[day+work[0]-1] = work[1]
        full+=1
#        print(tmp_li,work,day,scadule)
    except:
        continue
    if full == M:
        break

ans=sum(scadule)

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ba = []
m1 = m + 2
check = set(i for i in range(m + 1))
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 in check:
            check.remove(a1 + i)
            cnt += b1
            m1 = mb
            break
print(cnt)

Submission status: Time Limit Exceeded

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

task.sort()

wa = [0] * (10**5+10)
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        wa[task[j][1]] += 1
        j += 1
    if sum(wa):
        ls = [i for i, e in enumerate(wa) if e != 0][-1]
        ans += ls
        wa[ls] -= 1

print(ans)

Submission status: Time Limit Exceeded

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

n,m = map(int,input().split())
money = [[] for _ in range(10**5)]
dp = [0] * m

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

max1 = []
for i in range(m):
    max1 += money[i]
    max1.sort(reverse = True)
    if max1:
        dp[i] = max1.pop(0)
    if i >= 1:
        dp[i] += dp[i-1]

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint

sys.setrecursionlimit(4100000)

B = 10


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    jobs = list(map(string_to_int, inputs))
    jobs.sort(key=lambda x: (x[0]))

    money = 0
    for day in range(1, M + 1):
        max_money = 0
        max_i = -1
        for i, j in enumerate(jobs):
            if j[0] > day:
                break
            if max_money < j[1]:
                max_money = j[1]
                max_i = i
        if max_i != -1:
            money += max_money
            jobs.pop(max_i)

    return money


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)

Submission status: Time Limit Exceeded

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

day_max = [0 for _ in range(m)]
for i in range(n):
    a,b = map(int,input().split())
    if a<= m:
        bisect.insort(ab[a-1],b)

for i in range(m):
    day_max[i] = ab[i][-1]
    if day_max[i] > 0:
        ab[i] = ab[i][0:-1]

# print(ab)
# print(day_max)

ans = 0
for day in range(m):
    gain = 0
    dayi = -1
    for i in range(day+1):
        if gain < day_max[i]:
            gain = day_max[i]
            dayi = i
    if dayi != -1:
        ans += day_max[dayi]
        day_max[dayi] = ab[dayi][-1]
        if day_max[dayi] > 0:
            ab[dayi] = ab[dayi][0:-1]
    # print(ans, day, dayi)

print(ans)

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]
    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue
    tmp.sort()
    #  max_v = max(tmp)
    #  ans += max_v
    ans += tmp.pop()
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
for d in range(0, m):
    best=max(day_pay[:d+1])
    idx=day_pay[:d+1].index(best)
    try:
        day_pay[idx]=hikae[idx].pop()
    except:
        day_pay[idx]=0
    ans+=best
print(ans)

Submission status: Time Limit Exceeded

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

AB = [0] * N
for i in range(N):
    A, B = [int(x) for x in input().split()]
    AB[i] = (A, B)

# 期間が短い報酬が高い
def key(ab):
    a, b = ab
    return -b, a
AB = sorted(((a, b) for a, b in AB if a <=M), key=key)
#print(BA)

def calc(jobs, M):
    m = 0
    for d, (a, b) in enumerate(jobs):
        if d + a <= M:
            m += b
    return m

def check(N, M, AB):
    from itertools import permutations
    return max(calc(jobs, M) for jobs in permutations(AB))

def solve(N, M, AB):
    pass

def solve(N, M, AB):
    # a = 1 -> M - a
    d = M
    i = 0
    score = 0
    scheduled = set()
    for d in range(0, M+1)[::-1]:
        for i, (a, b) in enumerate(AB):
            if i in scheduled:
                continue
            #print("d=%d"%d,(a,b),d+a,end="")
            if d + a <= M:
                score += b
                #print(" score=%d"%score)
                d -= 1
                scheduled.add(i)
                break
    return score

#print("check", check(N, M, AB))
print(solve(N, M, AB))

Submission status: Time Limit Exceeded

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

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
full=0
for work in reversed(BA):
    if work[0]>M:
        continue
    day = [i for i, x in enumerate(scadule[work[0]-1:]) if x == 0]
    if day:
        scadule[day[0]+work[0]-1] = work[1]
        full+=1
    if full == M:
        break

ans=sum(scadule)

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

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)