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

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

count = 0
current = []

for day in range(1, M + 1):
    if day in AB:
        current.extend(AB[day])
        current.sort(reverse=True)

    #print("day{}:{}".format(day, current))
    if len(current) != 0:
        count += current.pop(0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n,m=map(int,input().split())
b=[[] for i in range(m)]
for i in range(n):
    x,y=map(int,input().split())
    if x>m:
        continue
    b[x-1].append(y)
for i in range(m):
    b[i].sort()
#print(b)

ans=0
for i in range(m):
    tmp=0
    k=-1
    for j in range(i+1):
        if len(b[j])<=0:
            continue
        if tmp<b[j][-1]:
            k=j
            tmp=b[j][-1]
            #print(tmp)
    if k==-1:
        continue
    ans+=tmp
    b[k].pop()


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)
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
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(key=lambda x: x[1])
    ans += tmp[-1][1]
    AB_dict[tmp[-1][0]].pop()
    tmp.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = [0 for _ in range(M+1)]
for x in C:
    A,B = x[0],x[1]
    try:
        ind = hist[-A-1::-1].index(0)
        hist[M-A-ind]=1
        rev += B
    except:pass
print(rev)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
L=list(tuple(map(int,input().split())) for _ in range(N))
L.sort(key=lambda x: x[1]*10**6-x[0], reverse=True)
ans=0
for i in range(1,M+1):
    for j,[a,b] in enumerate(L):
        if a<=i:
            ans+=b
            L.pop(j)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = {i:[] for i in range(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]
#print(ab)
ans = 0
for i in range(m)[::-1]:
    rem = m - i
    if ab[rem]:
        job = ab[rem]
        ans += max(job)
        del ab[rem][job.index(max(job))]
        if rem < m:
            ab[rem+1] += ab[rem]
    #print(ans)
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()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import bisect
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      add = ab[here][1]
      point = bisect.insort_left(pool,add)
      here += 1
    else:
      break
  try:
    ans += pool.pop(-1)
  except:
    pass
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)]

AB.sort()
B = [[] for _ in range(100005)]
tmp = 0
for ab in AB:
  if ab[0] != tmp:
    B[ab[0]] = B[tmp].copy()
  B[ab[0]].append(ab[1])
  tmp = ab[0]

for i in range(1, M + 1):
  if len(B[i]) == 0:
    B[i] = B[i - 1].copy()

ans = 0
for i in range(1, M + 1):
  if len(B[i]) > 0:
    m = max(B[i])
    ans += m
    for j in range(i, M + 1):
      if len(B[j]) > 0:
        B[j].remove(m)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

# なんこか入力
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=lambda x: x[0])
x = sorted(x, key=lambda x: -x[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 = list(map(int, input().split()))
ABs = [0] * N

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

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

rewards = [0] * (M + 1)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 10 21:26:22 2019
ABC137D
@author: maezawa
"""

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:
        i = 0
        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 = [int(x) for x in input().split()]

A = [[] for i in range(M)]

for i in range(N):
	t1, t2 = [int(x) for x in input().split()]
	if t1-1 <= M-1:
		A[t1-1].append(t2)


ans = 0
for i in range(M):
	t = 0
	idx = -1
	for j in range(i+1):
		if A[j] != []:
			if max(A[j]) >= t:
				idx = j
				t = max(A[j])
	if idx!=-1:
		ans += t
		A[idx].remove(t)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
X = []
for _ in range(n):
    a, b = map(int, input().split())
    if m-a>=0:
        X += [(-b, m-a)]

X = sorted(X)
ans = [0]*m

for ax, bx in X:
    if ans[bx]==0:
        ans[bx] = -ax
    elif ans[bx]>0:
        if 0 in ans[:bx]:
            ind = max([i for i, x in enumerate(ans[:bx]) if x == 0])
            ans[ind] = -ax

print(sum(ans))

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] = deque(sorted(C[i])[::-1])

answer = 0
tmp = deque()

for i in range(1, M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = 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
        else:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

Submission status: Time Limit Exceeded

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

# なんこか入力
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=lambda x: x[0])
x = sorted(x, key=lambda x: -x[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())
jds = [
  tuple(map(int, input().split()))
  for _ in range(n)
]
jds.sort(key=lambda x: x[1], reverse=True)

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

print(sum(jobs))

Submission status: Time Limit Exceeded

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

    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
    target_works = sorted_works[:index]
    best_work = max(enumerate(target_works), key=lambda x: x[1].b)
    sum += best_work[1].b
    del sorted_works[best_work[0]]

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = [0 for _ in range(M+1)]
for x in C:
    A,B = x[0],x[1]
    if 0 in hist[-A-1::-1]:
        ind = hist[-A-1::-1].index(0)
        hist[M-A-ind]=1
        rev += B
print(rev)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
arbs = sorted(
    [tuple(int(v) for v in input().split()) for _ in range(n)],
    key=lambda t: t[1], reverse=True)
cands = [[] for _ in range(m)]
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        cands[t].append(arb)
rest = []
total_reward = 0
for d, cand in enumerate(reversed(cands)):
    if len(cand) == 0:
        cand = rest
    else:
        cand = cand + rest
    if len(cand) == 0:
        continue
    valid_max_index = 0
    cand = sorted([c for c in cand if c[0] <= d + 1], key=lambda t: t[1], reverse=True)
    rest = cand[1:]
    if len(cand) > 0:
        c = cand[0]
        if c[0] <= d + 1:
            total_reward += c[1]

print(total_reward)

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

c = []

ab.sort()

answer = 0
j = 0
for i in range(1,m+1):
    max = 0
    while j < n:
        if ab[j][0] <= i:
            c.append(ab[j])
            j += 1
        else:
            break
    c.sort(reverse = True,key=lambda x:x[1])
    if len(c) != 0:
        answer += c[0][1]
        del c[0]

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def merge(a_list, b_list):
    res = []

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

    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])
for i in range(len(score_list)):
    score_list[i].sort(reverse=True)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(u) for u in input().split(" ")]
s = [tuple([int(u) for u in input().split(" ")]) for u in range(n)]
w = 0
for mi in range(1, m+1):
    try:
        c = [u for u in s if u[0] <= mi]
        v = max(c, key=lambda x: x[1])
        s.remove(v)
        w += v[1]
    except ValueError:
        pass
print(w)

Submission status: Time Limit Exceeded

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

a_b_list = []


for i in range(N):
    a, b = list(map(int, input().split()))
    a_b_list.append((a, b))


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

total_value = 0
memo_list = []
memo_index = len(sort_a_b_list) + 1000
for day in range(M, 0, -1):
    max_value = 0
    length = len(sort_a_b_list)
    j = 0
    while j <= length - 1:
        a_b = sort_a_b_list[j]
        if a_b[0] <= day:
            if max_value < a_b[1]:
                max_value = a_b[1]
                memo_index = j
        j += 1

    memo_list.append(memo_index)
    sort_a_b_list = [value for index, value in enumerate(sort_a_b_list) if index not in memo_list]
    memo_list = []
    total_value += max_value

print(total_value)

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
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(key=lambda x: x[1])
    ans += tmp[-1][1]
    AB_dict[tmp[-1][0]].remove(tmp[-1])
    tmp.remove(tmp[-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
n, m = map(int, input().split())

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

ans = 0
for i in range(m):
    i = i+1
    if min(a_list) <= i:
        # ind = a_list.index(max(b_list[list(map(lambda x : x < i+1,b_list))]))
        max_num = max( map(lambda y: y[0] * (y[1] <=i) ,zip(b_list,a_list)))
        # ind = a_list.index(max(b_list * list(map(lambda x : x <= i,a_list))))
        ind = b_list.index(max_num)
        ans = ans + b_list[ind]
        a_list[ind] = m + 1

print(ans)

# print( list(map(lambda x : x < 3,[1,2,3,4])))
# list(map(lambda x : x < i+1,b_list))

# print( [1,2,3,4] * [True,False,True,False])
# print(1 * False)

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:
        bisect.insort_left(ABs[A], B)

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 time

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

    L = []
    c = 0
    E = 0
    F = 1
    for i in range(M):
        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:
from bisect import bisect_left
import sys
input = sys.stdin.readline

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.pop(a)
    ret += b
    if not s :
        break
print(ret)

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()
    ans = 0
    # tmpL = []
    for i in range(1,M+1):

        maxv = 0
        maxi = -1

        for j in range(1,i+1):

            if len(DV[j])>=1 and maxv < DV[j][-1]:

                maxv = DV[j][-1]
                maxi = j
        ans += maxv
        if maxi != -1:
            DV[maxi].pop()
        

        # tmpL += l
        # tmpL.sort()
        # ans += tmpL.pop()
    print(ans)
        
        



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

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 main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

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

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

    res = 0
    q = []

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

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = 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:
N, M = map(int, input().split(' '))

reward = [0] * M

for i in range(N):
    a, b = map(int, input().split(' '))
    for j in reversed(range(max(0, M-a+1))):
        if reward[j] < b:
            b, reward[j] = reward[j], b

print(sum(reward))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
from collections import deque
sys.setrecursionlimit(100000000)

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  query = sorted(query,reverse = False)
  query2 = []
  for i in range(n):
    query2 += [query[i][0]]

  ans = 0
  judge = deque([])
  for i in range(m):
    left = bisect.bisect_left(query2,i+1)
    right = bisect.bisect_right(query2,i+1)

    judge += query[left:right]
    judge = deque(sorted(judge,reverse = True,key=lambda x: x[1]))
    if len(judge) != 0:
     a,b = judge.popleft()
     ans += b
  print(ans)
  
    
    
    
solve()

Submission status: Time Limit Exceeded

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

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

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

dic = {}
for i in range(M + 1):
    dic[i] = -1

for AB in ABs:
    day, reward = AB
    if day <= M:
        r = dic[day]
        if r == -1:
            dic[day] = reward
        else:
            for i in range(day, M + 1):
                r = dic[i]
                if r == -1:
                    dic[i] = reward
                    break
result = 0
for i in range(M + 1):
    v = dic[i]
    if v != -1:
        result += v
print(result)

Submission status: Time Limit Exceeded

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

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:
n,m=map(int,input().split())
li=[]

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

li.sort()

ans=0
for i in range(1,m+1):
    tmp=-1
    tmp_n=-1
    for j in range(len(li)):
        if li[j][0]<=i:
            if tmp<li[j][1]:
                tmp=li[j][1]
                tmp_n=j
        else:
            break
            
    if tmp!=-1:
    #    print(tmp)
        ans+=tmp
        del li[tmp_n]
    
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
for i in range(1, m+1):
    for n, a in enumerate(A):
        if a[1] <= i:
            ans += a[0]
            A.pop(n)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

class WorkList:
    def __init__(self):
        self.payList = [[] for _ in range(10001)]
        self.payList_sorted = []

    def add(self, a, b):
        if a <= M:
            self.payList[10001 - b].append(a)

    def sort_task(self):
        self.payList_sorted = [deque(sorted(l)) for l in self.payList]

    def get_task(self, deadline):
        for i, q in enumerate(self.payList_sorted):
            if len(q) > 0 and q[0] <= deadline:
                q.popleft()
                return 10001 - i
        return 0


w = WorkList()
for _ in range(N):
    A, B = map(int, input().split())
    w.add(A, B)

w.sort_task()

ans = 0

for d in range(M + 1):
    ans += w.get_task(d)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,*ab=map(int,open(0).read().split())
ab = [[x,y] for x,y in zip(ab[::2],ab[1::2])]
p_list=[0]*m
ab.sort(reverse=True,key=lambda x:x[1])
for d,p in ab:
    if 0 in set(p_list[d-1:]):
        p_list[p_list.index(0,d-1)] = p
print(sum(p_list))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
job_list = {}
for i in range(N):
	day, pay = map(int, input().split())
	if((day-1) in job_list):
		job_list[day-1].append(pay)
	else:
		job_list[day-1] = [pay]

now_date = 0
money = 0
now_job_list = []
sorted = False
for i in range(M):
	if(i in job_list):
		now_job_list.extend(job_list[i])
		sorted = False
	if(len(now_job_list) > 0):
		if(not sorted):
			now_job_list.sort()
			sorted = True
		money += now_job_list.pop()
print(money)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

for i in range(1, m + 1):
    cm = -1
    cmi = -1
    for j in range(len(xys)):
        if xys[j][0] <= i and xys[j][1] > cm:
            cm = xys[j][1]
            cmi = j
    if cmi >= 0:
        ans += cm
        xys.pop(cmi)

print(ans)

Submission status: Time Limit Exceeded

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

A = [[] for i in range(M)]

for i in range(N):
	t1, t2 = [int(x) for x in input().split()]
	if t1-1 <= M-1:
		A[t1-1].append(t2)


ans = 0
for i in range(M):
	t = 0
	idx = -1
	for j in range(i+1):
		if A[j] != []:
			if max(A[j]) >= t:
				idx = j
				t = max(A[j])
	if idx!=-1:
		ans += t
		A[idx].remove(t)


print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(M):
    work = -1
    income = 0
    for cand in range(len(li)):
        if li[cand][0] <= i + 1 and li[cand][1] > income:
            work = cand
            income = li[cand][1]
    if income != 0:
        ans += income
        li.pop(work)
print(ans)