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())
import numpy as np
from bisect import bisect_right

AB=[]
A=[]
for i in range(N):
    a,b=map(int, input().split())
    AB.append([a,b])
    A.append(a)
AB=(sorted(AB))
B=[]
for t in AB:
    a,b=t
    B.append(b)
A=sorted(A)
#print(A)
#print(bisect_left(A, 3))
ans=0
for i in range(M-1,-1,-1):
    idx=bisect_right(A,M-i)
    b=np.array(B[:idx])
    #print(b)
    if b.shape[0]!=0:
        just=np.argmax(b)
        ans+=B[just]
        A.pop(just)
        B.pop(just)

print(ans)

Submission status: Time Limit Exceeded

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

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB[-1][0],AB[-1][1]
    AB=AB[:-1]
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

Submission status: Time Limit Exceeded

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

AB.sort()
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[0][0]<=latest:
    a,b=AB[0][0],AB[0][1]
    AB=AB[1:]
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

Submission status: Time Limit Exceeded

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

AB.sort()
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[0][0]<=latest:
    a,b=AB.pop(0)
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    while A and A[0]<=latest:
    #for _ in range(br(A,latest)):
      A=A[1:]
      #index=br(works,B[0])
      #works=works[:index]+B[0]+works[index:]
      heapq.heappush(works,-B[0])
      B=B[1:]
  if not works:
    continue
  #ans+=works.pop(-1)
  ans-=heapq.heappop(works)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      #index=br(works,B[0])
      #works=works[:index]+B[0]+works[index:]
      heapq.heappush(works,-B[0])
      B=B[1:]
  if not works:
    continue
  #ans+=works.pop(-1)
  ans-=heapq.heappop(works)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      index=br(works,B[0])
      works=works[:index]+[B[0]]+works[index:]
      B=B[1:]
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      works.insert(br(works,B[0]),B[0])
      B=B[1:]
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A.pop(0)
      works.insert(br(works,B[0]),B[0])
      B.pop(0)
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  for _ in range(br(A,latest)):
    A.pop(0)
    works.insert(br(works,B[0]),B[0])
    B.pop(0)
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  for _ in range(br(A,latest)):
    A.pop(0)
    works.insert(br(works,B[0]),B[0])
    B.pop(0)
  if len(works)==0:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
ans=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        val.append(q[1])
    val.sort()
    if len(val):
        ans+=val.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
ans=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        val.append(q[1])
    val.sort()
    if len(val)>0:
        ans+=val.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
z,*q=[0]*99*M
v=[[]for _ in q]
for a,b in t:v[a-1]+=b,
for i in v[:M]:
 for j in i:heappush(q,-j)
 z-=heappop(q)
print(z)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*;(N,M),*t=[map(int,s.split())for s in open(0)];q=[0]*99*M;v=[[]for _ in q]
for a,b in t:v[a-1]+=b,
print(sum(exec("for j in i:heappush(q,-j)")or-heappop(q)for i in v[:M]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
import heapq


def solve():
    n, m = MI()

    AB = []
    for i in range(n):
        a, b = MI()
        AB.append((a, b))

    AB = sorted(AB, key=lambda x: x[0])
    # print(AB)

    q = [AB[0][1]]
    pre = AB[0][0]
    memo = {}
    for i in range(1, n):
        a, b = AB[i]
        if a == pre:
            q.append(b)
        else:
            memo[pre] = deque(sorted(q))
            q = [b]
            pre = a
    memo[pre] = deque(sorted(q))

    # print(memo)

    ans = 0
    for i in range(1, m+1):
        q = memo.get(i, deque([]))

        # print(i, hp)
        if len(q) > 0:
            ans += q.pop()

        q.extend(memo.get(i + 1, []))

        memo[i+1] = deque(sorted(q)[-m-i:])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
import heapq


def solve():
    n, m = MI()

    AB = []
    for i in range(n):
        a, b = MI()
        AB.append((a, b))

    AB = sorted(AB, key=lambda x: x[0])
    # print(AB)

    hp = [-AB[0][1]]
    heapq.heapify(hp)
    pre = AB[0][0]
    memo = {}
    for i in range(1, n):
        a, b = AB[i]
        if a == pre:
            heapq.heappush(hp, -b)
        else:
            memo[pre] = hp
            hp = [-b]
            heapq.heapify(hp)
            pre = a
    memo[pre] = hp

    # print(memo)

    ans = 0
    # for i in sorted(memo.keys()):
    for i in range(1, m+1):
        hp = memo.get(i, [])
        # print(i, hp)
        if len(hp) > 0:
            ans += - heapq.heappop(hp)

        hp_next = memo.get(i + 1, []) + hp
        heapq.heapify(hp_next)
        memo[i+1] = hp_next
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    job = [[] for _ in range(1 + max(ab))]
    for i, j in zip(*[iter(ab)] * 2):
        job[i].append(j)

    ans = 0
    t = []
    for i in range(1, m + 1):
        t += job[i]
        if len(t) == 0:
            continue
        else:
            m = max(t)
            t.remove(m)
            ans += m

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
Bl=[[] for i in range(10**5+5)]

for i in range(N):
    A,B=nm()
    Bl[A].append(B)

now=Bl[0]
ans=0
for i in range(1,M+2):
    if(now!=[]):
        max_val=max(now)
        ans+=max_val
        now.remove(max_val)
    now=now+Bl[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
n,m = map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            bisect.insort(pys,j)
    if pys:
        sum+=pys.pop()

print(sum)

Submission status: Time Limit Exceeded

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

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
sum = 0
for i in range(m):
    tmp = lis[i]
    if tmp:
        for j in tmp:
            bisect.insort(pys,j)
    if pys:
        sum+=pys.pop(-1)

print(sum)

Submission status: Time Limit Exceeded

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

lis = [[]for i in range(m)]

for i in range(n):
    if ab[i][0]<=m:
        lis[ab[i][0]-1].append(ab[i][1])

pys = []
sum = 0
for i in range(m):
    tmp = lis[i]
    for j in tmp:
        bisect.insort(pys,j)
    if pys:
        sum+=pys.pop(-1)

print(sum)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    d[a-1].append(-b)
cnt = 0
a = []
for i in range(m):
    a += d[i]
    heapq.heapify(a)
    if a:
        cnt += -heapq.heappop(a)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    d[a].append(b)
for i in range(m):
    d[i+1] = sorted(d[i+1])
cnt = 0
for i in range(m, 0, -1):
    max_n = 0
    index = 0
    for j in range(i, 0, -1):
        if d[j] and max_n < d[j][-1]:
            index = j
            max_n = d[j][-1]
    if d[index]:
        cnt += d[index].pop()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
N, M = list(map(int, input().split()))
A = [0]*N
B = [0]*N
# 日数別にもらえる額を管理
# money = defaultdict(list)
keys = list(range(1, 1+10**5))
# print(keys)
values = [[] for i in range(1, 1+10**5)]
job = dict(zip(keys, values))
for i in range(N):
    a, b = map(int, input().split())
    job[a].append(b)
    # A[i], B[i] = a, b
# A日後にB円もらえる、M日後に報酬最大化
ans = 0
can_work = []
for delay in range(1, 1+M):
    can_work.extend(job[delay])
    # print('delay', delay)
    # print(job)
    if (len(can_work) != 0):
        max_money = max(can_work)
        ans += max_money
        can_work.remove(max_money)

    # for i in range(delay):
    #     print(delay-i)
    #     if len(jpb[delay-i]) != 0:
    #         print('found')
    #         max_money = max(jpb[delay-i])
    #         ans += max_money
    #         jpb[delay-i].remove(max_money)
    #         jpb[delay-i]
    #         break
    #     print('===========')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-*-coding:utf-8-*-

import sys
import heapq

def pickup_job(tmp_jobs):
    tmp_jobs = sorted(tmp_jobs,key=lambda x:x[1],reverse=True)
    worked_job=heapq.heappop(tmp_jobs)
    return worked_job

def main():
    N,M = map(int, input().split())
    job_datas = [list(map(int,input().split())) for _ in range(N)]
    job_datas=sorted(job_datas)
    day_counter=M
    tmp_jobs=[]
    ans=0
    while day_counter >= 0:
        for job_data in job_datas:
            if (M-day_counter)>=job_data[0]:
                tmp_jobs.append(job_data)
            else:
                break
        if len(tmp_jobs)!=0:
            worked_job=pickup_job(tmp_jobs)
            ans+=worked_job[1]
            job_datas.remove(worked_job)
            tmp_jobs=[]
        day_counter-=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

value = [[] for _ in range(10 ** 5 + 1)]

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

for v in value:
    heapq.heapify(v)


ans = 0
for i in range(1, M + 1):
    my_max = 0
    for j, k in enumerate(range(i), 1):
        if len(value[j]) > 0:
            tmp = -1 * heapq.heappop(value[j])
            if my_max < tmp:
                my_max = tmp
            else:
                heapq.heappush(value[j], tmp * -1)
    ans += my_max

print(ans)

Submission status: Time Limit Exceeded

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

for i in range( N ):
  a, b = map( int, input().split() )
  if a - 1 < M:
    if L[ a - 1 ] == []:
      L[ a - 1 ] = [ b ]
    else:
      L[ a - 1 ].append( b )
      
ret = 0
C = []
for i in range( M ):
  C = sorted( L[i] + C )
  if C != []:
    ret += C.pop( -1 )

print( ret )

Submission status: Time Limit Exceeded

Solution code:
n,m=(int(i) for i in input().split())
r=0
s=[[] for i in range(m+1)]
for i in range(n):
  a,b=(int(i) for i in input().split())
  if a<=m:
    s[a].append([a,b])
for i in range(m):  
  s[i+1].sort(key=lambda x:x[1])
c=[]
for i in range(m):
  if len(s[i+1])!=0:
    c.append(s[i+1].pop())
  if len(c)!=0:
    c.sort(key=lambda x:x[1])
    k=c.pop()
    r+=k[1]
    if len(s[k[0]])!=0:
      c.append(s[k[0]].pop())
print(r)

Submission status: Time Limit Exceeded

Solution code:
import heapq

dic = {}
n, m = map(int, input().split())
for _ in range(n):
  a, b = map(int, input().split())
  if dic.get(a) is not None:
    dic[a].append(-b)
  else:
    dic[a] = [-b,]

ans = 0
bite = []
for i in range(1, m+1):
  if dic.get(i) is not None:
    bite = bite + dic[i]
  if len(bite) > 0:
    heapq.heapify(bite)
    ans += heapq.heappop(bite)
print(ans*-1)

Submission status: Time Limit Exceeded

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

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

AB.sort(key=lambda x: x[0])
ans = 0

for i in range(1,M+1):
  tmp = 0
  de = -1
  for j in range(N):
    
    if AB[j][0] > i:
      break
    
    if AB[j][1] > tmp:
      de = j
      tmp = AB[j][1]
    
  ans += tmp
  if de != -1:
    AB[de][1] = 0

print(ans)

Submission status: Time Limit Exceeded

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

import heapq
N,M = (int(x) for x in input().split())
jobs = []
taken = [0] * (M+1)
jappend = jobs.append
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jappend((B*(-1),A))
heapq.heapify(jobs)
for i in range(len(jobs)):
    temp = heapq.heappop(jobs)
    if taken[(M-temp[1]+1)//2:M-temp[1]+1].count(0) > 0:
        searching = M - temp[1]
    else:
        if temp[1] == M:
            searching = 0
        elif taken[0:(M-temp[1]+1)//2].count(0) > 0:
            searching = ((M-temp[1]+1)//2) - 1
        else:
            continue
    for i in range(searching+1):
        if taken[searching-i] == 0:
            taken[searching-i] = temp[0]
            break
print(sum(taken)*(-1))

Submission status: Time Limit Exceeded

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

import heapq
N,M = (int(x) for x in input().split())
jobs = []
taken = [0] * M
jappend = jobs.append
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jappend((B*(-1),A))
heapq.heapify(jobs)
for i in range(len(jobs)):
    temp = heapq.heappop(jobs)
    for i in range(M-temp[1]+1):
        if taken[M-temp[1]-i] == 0:
            taken[M-temp[1]-i] = temp[0]
            break
print(sum(taken)*(-1))

Submission status: Time Limit Exceeded

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

import heapq
N,M = (int(x) for x in input().split())
jobs = []
taken = [0] * M
jappend = jobs.append
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jappend((B*(-1),A))
heapq.heapify(jobs)
while jobs:
    temp = heapq.heappop(jobs)
    for i in range(M-temp[1]+1):
        if taken[M-temp[1]-i] == 0:
            taken[M-temp[1]-i] = temp[0]
            break
print(sum(taken)*(-1))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(N)]
pairs.sort(key = itemgetter(1), reverse = True)

A_max = M + 1
schedule = [0] * (M+1)
for A, B in pairs:
    if A_max == 1:
        break
    elif A < A_max:
        for i in range(A, A_max):
            if schedule[i] == 0:
                schedule[i] = B
                break
        else:
            A_max = A
    
print(sum(schedule))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(N)]
pairs.sort(key = itemgetter(1), reverse = True)

A_max = M + 1
schedule = [0] * (M+1)
for A, B in pairs:
    if A_max == 1:
        break
    elif A < A_max:
        for i in range(A, A_max):
            if schedule[i] == 0:
                schedule[i] = B
                break
        else:
            A_max = A
    


print(sum(schedule))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

pairs.sort(key = itemgetter(1), reverse = True)
schedule = [0] * (M+1)
for A, B in pairs:
    for i in range(A, M+1):
        if schedule[i] == 0:
            schedule[i] = B
            break

print(sum(schedule))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x:x[0])
day = 0
pay = 0
q = []
for i in range(1, M+1):
  for j in range(len(ab)):
    if ab[0][0] <= i:
      a, b = ab.pop(0)
      heapq.heappush(q, (-b, a))
    else:
      break
  if len(q) > 0:
    pay += - heapq.heappop(q)[0]

print(pay)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))
sal=0
for i in range(1,m+1):
    workL=[x for x in L if x[0]<=i]
    if len(workL)>0:
        workL=sorted(workL,key=lambda x:x[1],reverse=True)
        sal += workL[0][1]
        L.remove(workL[0])
print(sal)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))
sal=0
for i in range(1,m+1):
    workL=[x for x in L if x[0]<=i]
    ma=0
    for j in range(1,len(workL)):
        if workL[ma][1]<workL[j][1]:
            ma=j
    if len(workL)>0:
        sal += workL[ma][1]
        L.remove(workL[ma])
print(sal)

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

dp = [0]*(m+1)
for i in range(1, m+1):
  bmax = 0
  bidx = -1
  for idx, [a, b] in enumerate(ab):
    if a > i:
      break
    if b > bmax:
      bmax = b
      bidx = idx
  dp[i] = dp[i-1] + bmax
  if bidx != -1:
    ab.pop(bidx)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
used = [0]*N
ans = [0]*(M+1)

for i in range(1,M+1):
  m = 10**9+1
  for j in range(N):
    if AB[j][0] <= i and used[j] == 0:
      ans[i] = max(ans[i], AB[j][1])
      if ans[i] == AB[j][1]:
        m = j
  if m != 10**9+1:
    used[m] = 1
  else:
    pass
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)

data.sort(key=lambda x:x[1], reverse=True)
for a,b in data:
    for i in range(M-a,-1,-1):
        if b > dp[i]:
            dp[i] = b
            break
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m = map(int,input().split())
    alb = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in alb.keys():
            alb[a] = [b]
        else:
            alb[a] += [b]
    search = []
    s = 0
    for i in range(1,m+1):
        if i in alb.keys():
            for j in range(len(alb[i])):
                search.append(alb[i][j])
        if len(search)>0:
            m = search.pop(search.index(max(search)))
            s += m
    print(s)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
job=[[] for _ in range(M)]
list=[]
reward=0
rewards=0
for i in range(N):
    A,B=map(int,input().split())
    if A<=M:
        job[A-1].append(B)
for j in range(M):
    list.extend(job[j])
    if len(list)>0:
        reward=max(list)
        rewards+=reward
        list.remove(reward)
    
print(rewards)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
job=[[] for _ in range(M)]
list=[]
reward=0
rewards=0
for i in range(N):
    A,B=map(int,input().split())
    if A<=M:
        job[A-1].append(B)
for j in range(M):
    if len(job[j])>=1:
        list.extend(job[j])
    if len(list)>0:
        reward=max(list)
        rewards+=reward
        list.remove(reward)
    
print(rewards)

Submission status: Time Limit Exceeded

Solution code:

N,M=map(int,input().split())
job=[[] for _ in range(M)]
list=[]
reward=0
rewards=0
for i in range(N):
    A,B=map(int,input().split())
    if A<=M:
        job[A-1].append(B)
for j in range(M):
    if len(job[j])>=1:
        for k in range(len(job[j])):
            list.append(job[j][k])
    if len(list)>0:
        reward=max(list)
        rewards+=reward
        list.remove(reward)
    
print(rewards)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
ba=[]
for i in range(n):
    a, b = map(int, input().split())
    ba.append([-b, a])
heapq.heapify(ba)

ans=0

for i in range(m - 1, -1, -1):
    not_use = []
    while ba:
        l = heapq.heappop(ba)
        if l[1] + i <= m:
            ans += l[0] * -1
            break
        else:
            not_use.append(l)
    for j in not_use:
        heapq.heappush(ba, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
N,M = map(int, input().split())
AB = []
for i in range(N):
    A,B = map(int, input().split())
    if A<=M:
        AB.append((A,B))
    else:
        N-=1
AB.sort()

Q = []
ans = 0

for i in range(M):
    while AB and AB[0][0] == i+1:
        A,B = AB.pop(0)
        heappush(Q, -B)
    if Q:
        ans -= heappop(Q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

[N, M] = [int(x) for x in sys.stdin.readline().split(" ")]

ABs = {}

for i in range(N):
    [day, reward] = [int(x) for x in sys.stdin.readline().split(" ")]
    if day in ABs:
        index = 0
        for r in ABs[day]:
            if r >= reward:
                break
            else:
                index += 1

        ABs[day].insert(index, reward)
    else:
        ABs[day] = [reward]

result = 0
for day in range(M, 0, -1):
    reward_and_day = (-1, -1)
    for d in range(day, 0, -1):
        if d in ABs and ABs[d] and ABs[d][-1] > reward_and_day[0]:
            reward_and_day = (ABs[d][-1], d)
    (reward, day) = reward_and_day
    if day < 0:
        continue
    result += ABs[day].pop()

print(result)

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template

N,M = inputlist()
li = [[] for _ in range(M+1)]
for i in range(N):
    A,B = inputlist()
    B *= -1
    if A > M:
        continue
    li[A].append(B)
ans = 0
import heapq
for i in range(1,M+1):
    if i >= 2:
        li[i] += li[i-1]
    heapq.heapify(li[i])
    if len(li[i]) == 0:
        continue
    k = heapq.heappop(li[i])
    ans += k*(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
TF = [False for _ in range(N)]
kouho = []
ans = 0

# 後ろから見て優先度付きキューで取り出す
mae = 0
for i in reversed(range(M)):
    mae += 1
    kouho = []
    for n in range(N):
        if AB[n][0] <= mae and TF[n] != True:
            kouho.append([AB[n][1] * (-1), n])
    heapq.heapify(kouho)
    
    if kouho:
        b, n = heapq.heappop(kouho)
        ans += b*(-1)
        TF[n] = True
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
TF = [False for _ in range(N)]
kouho = []
ans = 0

# 後ろから見て優先度付きキューで取り出す
mae = 0
for i in reversed(range(M)):
    mae += 1
    for n in range(N):
        if AB[n][0] <= mae and TF[n] != True:
            kouho.append([n, AB[n][0], AB[n][1]])
    kouho = sorted(kouho, key=lambda x: x[2], reverse=True)
    if len(kouho) != 0:
        n, A, B = kouho[0]
        TF[n] = True
        ans += B
        kouho = []
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
from collections import deque
AB = deque(sorted([list(map(int, input().split())) for i in range(N)]))

from heapq import *
q = []
heapify(q)
ans = 0
remain_days = 1
while remain_days <= M:
    for a, b in list(AB):
        if a <= remain_days:
            heappush(q, -1 * AB.popleft()[1])
    if q:
        v = heappop(q)
        ans += -1 * v
    remain_days += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 02:06:07 2020

@author: Kanaru Sato
"""

import heapq

n,m = list(map(int, input().split()))
albeit = []
for i in range(m+1):
    albeit.append([])

for i in range(n):
    a,b = list(map(int, input().split()))
    if a <= m:
        albeit[a].append(-1*b)

##print(albeit)

for i in range(m):
    heapq.heapify(albeit[i+1])

##print(albeit)

sum = 0
for i in range(m):
    day = i+1 #day:1->m
    ##print("day=",day)
    minlist = []
    for j in range(day):
        if len(albeit[j+1]) >= 1:
            minlist.append(albeit[j+1][0])
        else:
            minlist.append(0)
    ##print(minlist)
    m = min(minlist)
    if m != 0:
        Maxalbeitindex = minlist.index(m)
        sum += -1*heapq.heappop(albeit[Maxalbeitindex+1])
    ##print(sum)

print(sum)