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:
inp = input().split()
n = int(inp[0])
m = int(inp[1])
part_list = []
for _ in range(n):
    inp = input().split()
    a = int(inp[0])
    b = int(inp[1])
    part_list.append((a, b))

part_time_list = sorted(part_list, key=lambda t: t[1]*-1)
# 給料がいいやつから入れていく．入れないやつはあきらめる


class Day:

    def __init__(self, this_index, max_index):
        self.used = False
        self.next_check_index = this_index + 1
        self.no = max_index < self.next_check_index  # true: もう調べる必要がない
        self.previous_index_list = [this_index - 1] if this_index != 0 else []
        self.max_index = max_index

    def change_next_index(self, next_inde):
        self.next_check_index = next_inde
        if self.max_index < self.next_check_index:
            self.no = True


day_list = [Day(i, m-1) for i in range(m)]  # i + 1 残りの日数．多ければ入れる
total_reward = 0
for part in part_time_list:
    # できるだけはいる
    day_index = part[0] - 1
    if day_index >= m:
        continue
    day = day_list[day_index]
    if not day.used:
        day.used = True
        total_reward += part[1]
        # 一つ前のアクセスは自分のつぎ.
        if not day.previous_index_list or len(day.previous_index_list) != 0:
            for previous_index in day.previous_index_list:
                previous_day = day_list[previous_index]
                previous_day.change_next_index(day.next_check_index)
            if not day.no:
                # 一つ次のまえに自分の前をたす
                next_day = day_list[day.next_check_index]
                next_day.previous_index_list += day.previous_index_list
            day.previous_index_list = []  # 自分を参照してくれるる奴はいない
        else:
            # 最初の要素はすることなし
            pass
    else:
        # その日は使われている.
        if day.no:
            pass
        else:
            # 次の日にバイトをいれる
            day = day_list[day.next_check_index]
            day.used = True
            total_reward += part[1]
            # 一つ前のアクセスは自分のつぎ.
            if not day.previous_index_list or len(day.previous_index_list) != 0:
                for previous_index in day.previous_index_list:
                    previous_day = day_list[previous_index]
                    previous_day.change_next_index(day.next_check_index)
                if not day.no:
                    # 一つ次のまえに自分の前をたす
                    next_day = day_list[day.next_check_index]
                    next_day.previous_index_list += day.previous_index_list
                day.previous_index_list = []  # 自分を参照してくれるる奴はいない

print(total_reward)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li = [list(map(int, input().split())) for i in range(n)]
day = [0 for i in range(m)]

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

count = 0

for i in range(n):
    x = li[i][0]-1
    for ii in range(x,m):
        if day[ii] == 0:
            day[ii] = li[i][1]
            count += li[i][1]
            break

print(count)

Submission status: Time Limit Exceeded

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

ans=0
for i in range(1,m+1):
    maxa=0
    temp=[]
    while absort:
        if absort[0][0]<=i:
            maxa=max(maxa,absort[0][1])
            temp.append(absort.pop(0))
        else:
            break
    ans+=maxa
    temp=sorted(temp,key=lambda x:(-x[1]))
    if len(temp)>0:
        del temp[0]
    temp+=absort
    absort=sorted(temp,key=lambda x:(x[0],-x[1]))


print(ans)

Submission status: Time Limit Exceeded

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


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

ab_list = sorted(ab_list, reverse=True)

monies = [0 for i in range(m + 1)]
d2c = collections.Counter()

for money, day in ab_list:
  try:
    idx = monies.index(0, day)
  except:
    continue
  monies[idx] = money
# print(monies)
print(sum(monies))

Submission status: Time Limit Exceeded

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

dayworked = set()
cnt = 0
for abi in ab:
    if abi[0] <= m:
        daycanwork = set(range(m-abi[0]+1))
        days = daycanwork - dayworked
        if len(days) == 0:
            continue
        day = max(days)
        dayworked.add(day)
        cnt += abi[1]   

print(cnt)

Submission status: Time Limit Exceeded

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

import heapq

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

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

ans = 0
l = []

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def main():
    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)

if __name__ == '__main__':
    main()

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 candi_r <= r and candi_t <= t and t <= j 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:
from bisect import bisect_right

N, M = map(int, input().split())
w = sorted([tuple(map(int, input().split())) for _ in range(N)])
days = [x[0] for x in w]
pays = [x[0] for x in sorted(w[:], key=lambda x: x[1], reverse=True)]
ans = 0
for i in range(M):
    c = bisect_right(days, M-i) - 1
    if c < 0:
        break
    e = c
    for j in range(1, M-i):
        d = bisect_right(days, M - i - j) - 1
        e = e if w[e][1] >= w[d][1] else d
    ans += w[e][1]
    del w[e]
    del days[e]

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
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 jobs.keys():
    if d > i:
      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:
N, M = map(int, input().split())
AB_list = [tuple(map(int, input().split())) for i in range(N)]

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

money = 0

for i in range(M):
  remain_days = i+1
  
  for (A, B) in sorted_AB_list:
    if A <= remain_days:
      money += B
      sorted_AB_list.remove((A, B))
      break

print(money)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
work = []
for i in range(n):
    _a, _b = list(map(int, input().split()))
    work.append({"duration": _a, "payment": _b})
work = sorted(work, key=lambda x: (-x["payment"], x["duration"]))
p = 0
for i in range(1, m + 1):
    if len(work) == 0:
        break
    for j in range(len(work)):
        w = work[j]
        if w["duration"] <= i:
            p += w["payment"]
            work.pop(j)
            break
print(p)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, M = map(int, input().split())
w = sorted([tuple(map(int, input().split())) for _ in range(N)])
days = [x[0] for x in w]
pays = [x[0] for x in sorted(w[:], key=lambda x: x[1], reverse=True)]
ans = 0
for i in range(M):
    c = bisect_right(days, M-i) - 1
    if c < 0:
        break
    e = c
    for j in range(M-i):
        d = bisect_right(days, M - i - 1) - 1
        e = e if w[e][1] >= w[d][1] else d
    ans += w[e][1]
    del w[e]
    del days[e]

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

ab1 = sorted(ab, key=lambda x: [x[0], x[1]], reverse =True)
a1 = [i[0] for i in ab1]
b1 = [i[1] for i in ab1]
c =  [0]*n
for i in range(n):
    c[i] = sum(x > b1[i] for x in b1[i:])

limit = m
ans1 = 0

for idx, time in enumerate(a1):
        if time <= limit and c[idx] < limit:
            ans1 += b1[idx]
            limit -=1
print(ans1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
work = [list(map(int, input().split())) for i in range(n)]
from operator import itemgetter
work = sorted(work,key=itemgetter(1),reverse=True)
count = 0
for i in range(1,m+1):
  for j in range(len(work)):
    if work[j][0] <= i:
      count += work[j][1]
      del work[j]
      break
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
N,M = map(int,input().split())
abc = []
for i in range(N):
    a,b = map(int,input().split())
    c = b/a
    abc.append((a,b,c))

abc.sort(key=lambda x:x[2],reverse=True)

d = defaultdict(deque)
for a,b,c in abc:
    d[a].append(b)
# print(abc)
# print(d)
ans = 0
for i in range(M-1,-1,-1):
    if not d: break
    tmpk = -1
    tmpv = -1
    dif = M - i
    for k in sorted(d.keys()):
        if k > dif: break
        if d[k][0] > tmpv:
            tmpv = d[k][0]
            tmpk = k
    if tmpk != -1:
        ans += tmpv
        d[tmpk].popleft()
        if not d[tmpk]:
            d.pop(tmpk)
print(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
    nexts = set(j for j in range(a1,m + 1))
    c = nexts & check
    if len(c) != 0:
        c =list(c)
        cc = c[0]
        check.remove(cc)
        cnt += b1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A_B = []
for i in range(N):
    a, b = map(int, input().split())
    A_B.append([a, b])
A_B = sorted(A_B, key=lambda x:x[1], reverse=True)

dayprice = [0] * (M + 1)

for a_b in A_B:
    try:
        if dayprice[a_b[0]] == 0:
            dayprice[a_b[0]] = a_b[1]
        else:
            tmp = dayprice[a_b[0] + 1:]
            ind = tmp.index(0) + a_b[0] + 1
            dayprice[ind] = a_b[1]
    except Exception as e:
        continue

print(sum(dayprice))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
PTJ = [[] for i in range(M+1)]
DP = [[[0,set()] for i in range(M+1)] for j in range(M+1)]
for i in range(N):
    A,B = map(int,input().split())
    if A <= M:  PTJ[A] += [[B,i]]
for i in range(1,M+1):  PTJ[i] = sorted(PTJ[i], key = lambda x: x[0])[::-1]

for i in range(1,M+1):
    if len(PTJ[i]) != 0:
        DP[1][i][0] = PTJ[i][0][0]
        DP[1][i][1].add(PTJ[i][0][1])

for i in range(2,M+1):
    for j in range(1,i):
        for k in range(1,M+1-(j-1)):
            key = True
            if len(PTJ[j]) == 0:                
                key = False
            else:    
                l = 0
                while PTJ[j][l][1] in DP[i-j][k][1]:
                    l += 1
                    if l >= len(PTJ[j]):                
                        key = False
                        break
            if key:    
                if DP[i][j][0] < DP[i-j][k][0] + PTJ[j][l][0]:
                    DP[i][j][0] = DP[i-j][k][0] + PTJ[j][l][0]
                    DP[i][j][1] = DP[i-j][k][1]
                    DP[i][j][1].add(PTJ[j][l][0])
            else:
                if DP[i][j][0] < DP[i-j][k][0]:
                    DP[i][j][0] = DP[i-j][k][0]
                    DP[i][j][1] = DP[i-j][k][1]

ans = max([DP[M][i][0] for i in range(M+1)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n ,m = map(int,input().split())
a = [list(map(int, input().split())) for i in range(n)]
a = sorted(a)
che = []
ans = 0
for i in range(1,m+1):
    count = 0
    for k in range(len(a)):
        k -= count
        if a[k][0] <= i:
            che.append(a.pop(k)[1])
            count += 1
        else:
            break;
    if len(che) > 0:
        ans += che.pop(che.index(max(che)))
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,limit=[int(i) for i in input().split()]
baitolist=[[int(i) for i in input().split()] for j in range(n)]
baitodict={}
for i in range(1,limit+1):
    baitodict[str(i)]=[]
for baito in baitolist:
    day=str(baito[0])
    money=baito[1]
    if int(day)<=limit:
        baitodict[day].append(money)
        baitodict[day].sort()
# print(baitodict)

sumnum=0
for i in range(1,limit+1):
    maxindex=""
    maxmoney=0
    for j in range(1,i+1):
        if baitodict[str(j)]!=[]:
            a=baitodict[str(j)][-1]
            if maxmoney<a:
                maxmoney=a
                maxindex=str(j)
    if maxindex!="":
        baitodict[maxindex].pop()
    sumnum+=maxmoney
#     print(sumnum)
print(sumnum)

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([b,a])
task.sort(reverse=True)
day = [i for i in range(1,m+1)]
salaly = 0
for k in range(n):
    for i in day:
        if task[k][1] <= i:
            day.remove(i)
            salaly += task[k][0]
            break
print(salaly)

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

ans = 0
for i in range(M):
    l2 = list(filter(lambda x:x[0]<=i+1, l))
    if l2 != []:
        m = max(l2, key = lambda x:x[1])
        ans += m[1]
        l.remove(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque

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

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

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        bisect.insort_right(paytree,wq.popleft()[1])
    if len(paytree) > 0:
        ans += paytree.pop(len(paytree) - 1)

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
    candidate.sort()
    r = candidate[-1]
    candidate = candidate[:-1]
    ans += r
print(ans)

Submission status: Time Limit Exceeded

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

job_list=[]
for i in range(1):
    # 残り日数
    nokori=M-i
    # 可能なタスクの洗い出し
    tasks_can=[(i,t) for i,t in enumerate(tasks) if t[0]<=nokori]
    # 最大効率タスク抽出
    dic={}
    for i,t in tasks_can:
        if t[0] not in dic.keys():
            dic[t[0]]=t[1]
        else:
            dic[t[0]]=max(t[1],dic[t[0]])        
    tasks_max=[]
    for x in list(dic.items()):
        tasks_max.append(x)
        
    for i,t in tasks_can:
        if t in tasks_max:
            job_list.append([i])    
    
for i in range(1,M):
    # 残り日数
    nokori=M-i
    job_list2=[]
    for job in job_list:
        # 可能なタスクの洗い出し
        tasks_can=[(i,t) for i,t in enumerate(tasks) if t[0]<=nokori and i not in job]
        # 最大効率タスク抽出
        dic={}
        for i,t in tasks_can:
            if t[0] not in dic.keys():
                dic[t[0]]=t[1]
            else:
                dic[t[0]]=max(t[1],dic[t[0]])        

        tasks_max=[]
        for x in list(dic.items()):
            tasks_max.append(x)
        for i,t in tasks_can:
            if t in tasks_max and i not in job:
                job_list2.append(job+[i])

    if len(job_list2)>0:
        job_list=job_list2
    else:
        break
        

    
score=0
for job in job_list:
    tmp=sum([x[1] for i,x in enumerate(tasks) if i in job])
    if score<tmp:
        score=tmp
print(score)

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(i) for i in input().split()]
AB = []
for n in range(N):
    AB.append([int(i) for i in input().split()])
from collections import deque
works = sorted(AB,key=lambda x:(-x[1],x[0],))
works = deque(works)
work_schedule = [0]*M
for w in range(len(works)):
    work = works.popleft()
    if work[0] > M:
        pass
    else:
        cnt = 0
        while True:
            if (work[0]-1+cnt) >= M:
                break
            elif work_schedule[work[0]-1+cnt]  == 0:
                work_schedule[work[0]-1+cnt] = work[1]
                break
            else:
                cnt+=1
print(sum(work_schedule))

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

Submission status: Time Limit Exceeded

Solution code:
num, day = [int(x) for x in input().split()]
 
worklist = [[] for i in range(day+4)]
 
wd = {}
 
for i in range(num):
  d, m = [int(x) for x in input().split()]
  if d <= day:
    worklist[d-1].append(m)
  if d-1 in wd.keys():
    wd[d-1].append(m)
  else:
    wd[d-1] = [m]
 
ans = 0
 
canworklist = []
 
workday = wd.keys()
 
for i in range(day):
  if i in workday:
    canworklist += wd[i]
  if canworklist:
    mm = max(canworklist)
    ans += mm
    canworklist.remove(mm)
  
print(ans)
 
#print(wd)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n,m = (int(num) for num in input().split())
ab = [[0,0] for _ in range(n)]
for i in range(n):
    a,b = (int(num) for num in input().split())
    ab[i][0] = a
    ab[i][1] = b
#print(ab)
ab.sort(key = lambda x: x[1], reverse=True)


days = [i+1 for i in range(m)]
leng = m
ans = 0
for item in ab:
    if leng <= 0:
        break;
    a = item[0]
    b = item[1]
    idx = bisect.bisect_left(days,a)
    if idx < leng:
        days.pop(idx)
        leng -= 1
        ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:


N,M = list(map(lambda x: int(x),input().split()))
dic = {}
maxs = [-10**6]*(M+1)
for i in range(N):
    x,y = list(map(lambda x: int(x),input().split()))
    if x > M:
      continue
    if x not in dic.keys():
        dic[x] = [y]
        maxs[x]=y
    else:
        dic[x].append(y)
        if y > maxs[x]:
            maxs[x]=y

answer=0
for i in range(1,M+1):
    #print(i)
    max_v = -10**6
    idx=-1
    for j in range(1,i+1):
        #print("j:{}".format(j))
        if max_v<maxs[j]:
            max_v = maxs[j]
            idx = j
    if idx > 0:
        answer += max_v
        dic[idx].remove(max_v)
        if len(dic[idx])>0:
            maxs[idx] = max(dic[idx])
        else:
            maxs[idx] = -10**6
    #print(maxs)
    #print(dic)
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, M = MAP()
    A = MATINT(N)
    A.sort()
    sumv = 0
    mm = 1
    A += [[10**6, 10**6]]
    aa = 0
    count = 0
    tmp = []
    for mm in range(1, M+1):
        while A[aa][0] <= mm:
            tmp.append(A[aa][1])
            aa += 1
        if tmp:
            maxv = max(tmp)
            count += maxv
            tmp.remove(maxv)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

today = 0

after = []
money = []

for i in range(n):
    a, b = map(int, input().split())
    after.append(a)
    money.append(b)

sum_money = 0
for day in range(m, -1, -1):
    # print('day',day)
    # print('after', after)
    candidates = [[i, money[i]] for i, x in enumerate(after) if x <= (m - day)]
    # print(candidates)
    if candidates:
        maxi = [-1, 0]
        for cand in candidates:
            if maxi[1] < cand[1]:
                maxi = cand
        # print('maxi', maxi)
        del after[maxi[0]]
        del money[maxi[0]]
        sum_money += maxi[1]

print(sum_money)

Submission status: Time Limit Exceeded

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

import bisect
import heapq

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

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


ans = 0
l = []

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    # print(l)

    if l != []:
        ans += heapq.heappop(l) * -1

    # print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    mix_list = [[a, b] for a, b in zip(A, B)]
    mix_list = sorted(mix_list, key = lambda x: x[0])
    A = [a for a, b in mix_list]
    B = [b for a, b in mix_list]
    #print(A, B)
    dp = [[0 for i in range(N)] for j in range(M)]
    for i in range(M):
        if A[0] <= (i+1):
            dp[i][0] = B[0]
    for j in range(1, N):
        if A[j] <= 1:
            dp[0][j] = max(B[j], dp[i][j-1])
    for i in range(1, M):
        for j in range(1, N):
            if A[j] <= (i+1):
                dp[i][j] = max(B[j]+dp[i-1][j-1], dp[i][j-1])
            else:
                dp[i][j] = dp[i][j-1]
    #print(dp)
    print(dp[M-1][N-1])
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        wa.append(task[j][1])
        j += 1
    if wa:
        ls = max(wa)
        ans += ls
        wa.remove(ls)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

l.sort(cmp=cmp, reverse=True)
#print l
sum = 0
for i in range(1, M+1):
    #print i, l
    for j in l:
        if j[0] > i:
            continue
        else:
            sum += j[1]
            l.remove(j)
            break

print sum

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n)]
abab = sorted(sorted(abab, key=itemgetter(0), reverse=True), key=itemgetter(1), reverse=True)

gyara = [0 for _ in range(m+1)]

for a, b in abab :
    for i in range(a, m+1) :
        if gyara[i] == 0 :
            gyara[i] = b
            break

print(sum(gyara))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect
import heapq
N,M = [int(x) for x in input().split()]
work = {}
for _ in range(N):
    a,b = [int(x) for x in input().split()]
    if(a in work):
        work[a].append(-b)
    else:
        work[a] = [-b]

#%%
cand = []
cnt = 0
for i in range(1,M+1):
    if(i in work):
        cand += work[i]
    heapq.heapify(cand)
    if(len(cand)==0):
        continue
    x = heapq.heappop(cand)
    cnt += -x

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
work = []
for i in range(n):
    _a, _b = list(map(int, input().split()))
    work.append({"duration": _a, "payment": _b})
work = sorted(work, key=lambda x: (-x["payment"], -x["duration"]))
p = 0
for i in range(1, m + 1):
    if len(work) == 0:
        break
    for j in range(len(work)):
        w = work[j]
        if w["duration"] <= i:
            p += w["payment"]
            work.pop(j)
            break
print(p)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
N,M = map(int,input().split())
abc = []
for i in range(N):
    a,b = map(int,input().split())
    c = b/a
    abc.append((a,b,c))

abc.sort(key=lambda x:x[2],reverse=True)

d = defaultdict(deque)
for a,b,c in abc:
    d[a].append(b)
# print(abc)
# print(d)
now = 1
ans = 0
days = [True] * M
for i in range(M-1,-1,-1):
    tmpk = -1
    tmpv = -1
    dif = M - i
    for k in sorted(d.keys()):
        if k > dif: break
        if d[k][0] > tmpv:
            tmpv = d[k][0]
            tmpk = k
    if tmpk != -1:
        ans += tmpv
        d[tmpk].popleft()
        if not d[tmpk]:
            d.pop(tmpk)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import copy
import math
from collections import Counter
from operator import itemgetter
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))

    return get_counter(first_word) == get_counter(second_word)
input = sys.stdin.readline
N ,M = map(int,input().split())
e = [[int(i) for i in input().split()] for i in range(N)]
e=sorted(e, key=itemgetter(0))
task_list=[]
chker = 0
ans = 0
for i in range(M):
    day = i+1
    if chker != N:
        while day == e[chker][0] or day > e[chker][0]:
            task_list.append(e[chker][1])

            chker += 1
            if chker == N:
                break
    task_list.sort()
    if task_list != []:
        ans += task_list[-1]
        task_list = task_list[:len(task_list)-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
#最大日数は M + M-1 + M-2 + .. + 1
#最大選択数 は M個
Y = [[] for i in range(100001)]
#Y1 = {}
for i in range(N):
    A, B = map(int,input().split())
    Y[A].append(B)
    # if A in Y1.keys():
    #     Y1[A].append(B)
    # else:
    #     Y1[A] = [B]

cnt = 0
C = []
#import itertools
#C = list(itertools.chain.from_iterable(Y[1:M+1]))
#print(C)
#C.sort()
#print(sum(C[:M]))
for i in range(1,M+1):
    #if len(Y[i]) > 0:
    #C.extend(Y[i])
    C += Y[i]

    if len(C) > 0:
        C.sort(reverse=True)
        cnt = cnt + C.pop(0)
        #C.remove(max(C))
        #del C[0]
    if len(C) > M + 1 - i:
        C = C[:M+1-i]
print(cnt)