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:
from collections import defaultdict

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = defaultdict(int)
ans = 0
for i in range(m):
    for j in c[i]:
        choice[j] += 1
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
        if choice[use] <= 0:
            del choice[use]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int,input().split())
joblist = []
for i in range(n):
    a,b = map(int,input().split())
    joblist.append([a,b])
joblist.sort(key=lambda x :x[0])
kouho = []
 
ans =0
 
for i in range(1,m+1):
    count=0
    if joblist:
        for j,job in enumerate(joblist):
            if job[0]==i:
                
                heapq.heappush(kouho,(-1*job[1]))
                
                
            if job[0]!=i:
                if count:
                    for _ in range(count-1):
                        joblist.pop(0)
        if kouho:
            ans += -1*heapq.heappop(kouho)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = Counter()
ans = 0
for i in range(m):
    choice = choice + Counter(c[i])
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = defaultdict(int)
ans = 0
for i in range(m):
    for k, v in Counter(c[i]).items():
        choice[k] += v
    if choice:
        use = max(choice)
        v = choice.pop(use)
        if v - 1 > 0:
            choice[use] = v - 1
        ans += use
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = {}
ans = 0
for i in range(m):
    choice = dict(Counter(choice) + Counter(c[i]))
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
pab = [(i, k[0], k[1]) for i, k in enumerate(sorted(ab, key=lambda x: (-x[1], x[0])))]
hq = []
result = 0
for i in range(1, m + 1):
    for j in [k for k in pab if k[1] == i]:
        heappush(hq, j)
    if hq:
        result += heappop(hq)[2]
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = defaultdict(int)
ans = 0
for i in range(m):
    for k, v in Counter(c[i]).items():
        choice[k] += v
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
        if choice[use] <= 0:
            del choice[use]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys

    input = sys.stdin.readline
    N, M = map(int, input().split())

    import bisect

    ABs = [[] for _ in range(M + 1)]
    for i in range(N):
        A, B = map(int, input().split())
        if A <= M:
            ABs[A].append(B)
    ABs[0].sort()

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

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = {}
ans = 0
for i in range(m):
    choice = dict(Counter(choice) + Counter(c[i]))
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
list_ = sorted([tuple(map(int, input().split())) for i in range(n)], key=lambda x: x[1], reverse=True)
res = [0 for i in range(m)]

cnt = 0
for i in list_:
    if cnt > m:
        break
    tmp = i[0] - 1
    while tmp <= m - 1:
        if res[tmp] == 0:
            res[tmp] = i[1]
            cnt += 1
            break
        else:
            tmp += 1

print(sum(res))

Submission status: Time Limit Exceeded

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

for n in range(N):
    AB[n][0], AB[n][1] = map(int, input().split())
    AB[n][1] = 0 - AB[n][1]
AB.sort()

pop_list = []

earn = 0
for m in range(1, M + 1):
    max_earn = 0
    max_i = 0
    for i in range(len(AB)):
        if m < AB[i][0]:
            break

        if max_earn > AB[i][1] and i not in pop_list:
            max_earn = AB[i][1]
            max_i = i

    if max_earn != 0:
        earn += AB[max_i][1]
        pop_list.append(max_i)

print(0 - earn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
a_list = sorted([list(map(int, input().split()))
                 for _ in range(n)], key=lambda x: x[1], reverse=True)
s_list = [[] for _ in range(m+1)]
for a in a_list:
    if a[0] < m + 1:
        s_list[a[0]].append(a[1])

cnt = 0
for i in range(1, m+1):
    tmp_list = [s[0] for j, s in enumerate(s_list) if s and j <= i]
    if tmp_list:
        s_max = max(tmp_list)
        cnt += s_max
        tmp = next((s for s in s_list if s and s[0] == s_max))
        tmp.pop(0)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, m = map(int, input().split())
    ab = list(list(map(int, input().split())) for _ in range(n))
    # ab = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (x[0], -x[1]))
    now, earn = m - 1, 0
    while now != -1:
        candidates = [data for data in ab if data[0] <= m - now]
        if candidates:
            value = max(candidates, key=lambda x: x[1])
            ab.remove(value)
            earn += value[1]
        now -= 1
    return earn


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, m = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (x[0], -x[1]))
    now, earn = m - 1, 0
    while now != -1:
        candidates = [data for data in ab if data[0] <= m - now]
        if candidates:
            value = max(candidates, key=lambda x: x[1])
            ab.remove(value)
            earn += value[1]
        now -= 1
    return earn


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, m = map(int, input().split())
    ab = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (x[0], -x[1]))
    now, earn = m - 1, 0
    while now != -1:
        candidates = [data for data in ab if data[0] <= m - now]
        if candidates:
            value = max([data for data in ab if data[0] <= m - now], key=lambda x: x[1])
            ab.remove(value)
            earn += value[1]
        now -= 1
    return earn


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import operator

INF = 1e6

n_task, n_day = [int(x) for x in input().split()]
task_dict = defaultdict(list)
for _ in range(n_task):
    day, reward = [int(x) for x in input().split()]
    task_dict[day].append(reward)

for day, rewards in task_dict.items():
    task_dict[day] = sorted(rewards, reverse=True)

task_days = sorted(task_dict.keys())

reward_total = 0
for day_remain in range(1, n_day + 1):
    max_reward = - INF
    max_reward_day = None
    max_reward_i = None
    for i_day, day in enumerate(task_days):
        rewards = task_dict[day]
        if day > day_remain:
            break
        if rewards[0] > max_reward:
            max_reward = rewards[0]
            max_reward_day = day
            max_reward_i = i_day
    if max_reward > - INF:
        reward_total += max_reward
        del task_dict[max_reward_day][0]
        if len(task_dict[max_reward_day]) == 0:
            del task_days[max_reward_i]
print(reward_total)

Submission status: Time Limit Exceeded

Solution code:
import operator

INF = 1e6

n_task, n_day = [int(x) for x in input().split()]
ab_list = [[int(x) for x in input().split()] for _ in range(n_task)]

ab_list = sorted(ab_list, key=operator.itemgetter(0))

reward_total = 0
for day_remain in range(1, n_day + 1):
    max_reward = - INF
    max_reward_idx = None
    for i_task, (a, b) in enumerate(ab_list):
        if a > day_remain:
            break
        if b > max_reward:
            max_reward = b
            max_reward_idx = i_task
    if max_reward > - INF:
        reward_total += max_reward
        del ab_list[max_reward_idx]
print(reward_total)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
a_list = [list(map(int, input().split())) for i in range(n)]

ans = 0
finish_list = [[]]
for i in range(1, m+1):
    tmp = [a for a in a_list if a[0] <= i and a not in finish_list]
    if not tmp:
        continue
    a_max = tmp[np.argmax(tmp, axis=0)[1]]
    finish_list.append(a_max)
    ans += a_max[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from heapq import heappop, heappush
from numpy import argmin
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    avb.append(-j)
  if avb != []:
    ans -= avb.pop(argmin(avb))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    avb.append(-j)
  if avb != []:
    ans -= avb.pop(avb.index(min(avb)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    avb.append(-j)
  if avb != []:
    ans -= min(avb)
    avb.remove(min(avb))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst = sorted(lst, key=lambda x:x[0])
lst = sorted(lst, key=lambda x:x[1], reverse=True)
#print(lst)
cnt = 0
ans = 0
cntup = m
while cntup != 0:
  cnt += 1
  lst_f = [j for j in lst if j[0]<=cnt]
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
  #print(lst_f)
  if lst_f != []:
    #print(lst)
    ans += lst_f[0][1]
    lst.remove(lst_f[0])
    cntup -= 1
  if lst == [] or cnt==m:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

na = lambda: map(int, sys.stdin.readline().split())

n, m = na()
ab = [list(na()) for _ in range(n)]

ans = 0
h = []
for day in range(1, m+1):
  d = 0
  for i in range(len(ab)):
    if ab[i-d][0] <= day:
      heappush(h, -ab.pop(i-d)[1])
      d += 1
  if h:
    ans += -heappop(h)

print(ans)

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l.pop()

print(ans)

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
# print(dic)

ans = 0
l = []
for j in range(1, m+1):
    if j in dic.keys():
        l += dic[j]
        l.sort()
    #print(l)
    if l:
        ans += l[-1]
        l = l[:-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        jobs = dict()
        for i in range(N):
            A, B = map(int, input().split())
            if A > M:
                continue
            if A not in jobs:
                jobs[A] = list()
            jobs[A].append(B)
        result = 0
        jobs_keys = sorted(jobs.keys())
        for j in range(M):
            m = m_s = None
            for s in jobs_keys:
                if s > j+1:
                    break
                if len(jobs[s]) == 0:
                    continue
                _m = max(jobs[s])
                if m is None:
                    m = _m
                    m_s = s
                    continue
                if _m < m:
                    continue
                if _m > m or s > m_s:
                    m = _m
                    m_s = s
            if m is not None:
                jobs[m_s].remove(m)
                result += m
        print(result)
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        jobs = dict()
        for i in range(N):
            A, B = map(int, input().split())
            if A not in jobs:
                jobs[A] = list()
            jobs[A].append(B)
        result = 0
        jobs_keys = sorted(jobs.keys())
        for j in range(M):
            m = m_s = None
            for s in jobs_keys:
                if s > j+1:
                    break
                if len(jobs[s]) == 0:
                    continue
                _m = max(jobs[s])
                if m is None:
                    m = _m
                    m_s = s
                    continue
                if _m < m:
                    continue
                if _m > m or s > m_s:
                    m = _m
                    m_s = s
            if m is not None:
                jobs[m_s].remove(m)
                result += m
        print(result)
    except EOFError:
        break

Submission status: Time Limit Exceeded

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

q = [[0] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b)

# print(q)

pool = [0]
answer = 0
for x in reversed(q):
    x.append(sorted(pool, reverse=True)[0])
    m = max(x)
    answer += m
    pool += x
    pool.remove(m)
    

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(r)

#解法
rewards = 0
li = []
for i in range(M):
    #候補をリストに追加(給料が間に合うもの仕事が一日ごとに増える)
    li.extend(jobs[i])
    if len(li) >0:
        #最大値を求める(給料が高いバイトをしたい)
        reward = max(li)
        rewards += reward
        #使った値は取り除く(同じバイトはNGのため)
        li.remove(reward)

print(rewards)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

A = []
B = []
for _ in range(N):
    a,b = map(int,input().split(" "))
    A.append(a)
    B.append(b)


# 日数でソート
ind_sorted = sorted(range(N), key = lambda x:A[x])

tmp_a = 0
tmp_b_ls = [0]
money = 0
for i in range(N):
    if A[ind_sorted[i]] > M:
        break
    if tmp_a != A[ind_sorted[i]]:
        d = A[ind_sorted[i]]-tmp_a
        tmp_money = sum(tmp_b_ls[-d:])
        money += tmp_money
        tmp_b_ls = tmp_b_ls[:-d]
        tmp_a = A[ind_sorted[i]]
    bisect.insort(tmp_b_ls,B[ind_sorted[i]])

d = M+1-tmp_a
tmp_money = sum(tmp_b_ls[-d:])
money += tmp_money

print(money)

Submission status: Time Limit Exceeded

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

ls = [[int(x) for x in input().split()] for _ in range(N)]

# これでからの配列を生成すると、全てのリストに値が入っちゃう
# q = [[]]*M
# q[0].append(1)

q = [[0] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b)

# print(q)

pool = []
answer = 0
for x in reversed(q):
    m = max(x+pool)
    # print(m, x, pool)
    answer += m
    pool += x
    pool.remove(m)
    

print(answer)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        jobs = dict()
        for i in range(N):
            A, B = map(int, input().split())
            if A not in jobs:
                jobs[A] = list()
            jobs[A].append(B)
        result = 0
        jobs_keys = sorted(jobs.keys(), reverse=True)
        for j in range(M):
            m = m_s = None
            for s in jobs_keys:
                if s > j+1 or len(jobs[s]) == 0:
                    continue
                _m = max(jobs[s])
                if m is None or _m > m:
                    m = _m
                    m_s = s
            if m is not None:
                jobs[m_s].remove(m)
                result += m
        print(result)
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
from heapq import merge


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

last_day_to_reward = {}

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

for k in last_day_to_reward:
    last_day_to_reward[k].sort()

ans = 0
candidate = []
for i in reversed(range(1, M+1)):
    if i in last_day_to_reward:
        candidate = list(merge(candidate, last_day_to_reward[i]))

    if candidate:
        r = candidate.pop(-1)
        ans += r

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import merge


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

last_day_to_reward = {}

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

for k in last_day_to_reward:
    last_day_to_reward[k].sort()

ans = 0
candidate = []
for i in reversed(range(1, M+1)):
    if i in last_day_to_reward:
        candidate = list(merge(candidate, last_day_to_reward[i]))

    if candidate:
        r = candidate[-1]
        ans += r
        candidate = candidate[:-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Reverse:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if len(self.hq) == 0:
            return None
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)

    def top(self):
        if self.desc:
            return self.hq[0].val
        else:
            return self.hq[0]

    def __len__(self):
        return len(self.hq)


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

ans = 0
h = Heapq([], desc=True)
for i in range(1, m+1):
    for j in filter(lambda x: x[0] == i, ab):
        h.push(j[1])
    ab = list(filter(lambda x: x[0] != i, ab))
    if len(h) == 0:
        continue
    ans += h.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
b = []
for i in range(n):
	k,l = map(int,input().split())
	a.append(k)
	b.append(l)

ans = 0
for v in range(1,m+1):
	tmp = [i for i,x in enumerate(a) if x <= v]
	if len(tmp)!=0:
		b_list = [b[i] for i in tmp]
		max_index = tmp[b_list.index(max(b_list))]
		ans += b[max_index]
		del(a[max_index])
		del(b[max_index])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Reverse:
    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        return self.val > other.val

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        if len(self.hq) == 0:
            return None
        if self.desc:
            return heapq.heappop(self.hq).val
        else:
            return heapq.heappop(self.hq)

    def push(self, a):
        if self.desc:
            heapq.heappush(self.hq, Reverse(a))
        else:
            heapq.heappush(self.hq, a)

    def top(self):
        if self.desc:
            return self.hq[0].val
        else:
            return self.hq[0]

    def __len__(self):
        return len(self.hq)


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

ans = 0
h = Heapq([], desc=True)
for i in range(1, m+1):
    for j in filter(lambda x: x[0] == i, ab):
        h.push(j[1])
    if len(h) == 0:
        continue
    ans += h.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def acinput():
    return list(map(int, input().split(" ")))

import numpy as np


N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])


res=0
do=[0]*(M+1)
nowdate=M-1
koho=np.array([])
k=0
while True:
    #print(k)
    i=k
    while True:
        if i>=len(ab):
            k=10**8
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        koho=np.append(koho,ab[i][1])
        i+=1
    #print(koho)
    if len(koho)>0:
        maxi=np.argmax(koho)
        #print(koho)
        res+=koho[maxi]
        koho=np.delete(koho,maxi)
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*50*M
v=[[]for _ in q]
z=0
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]
z=0
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:
input = raw_input
#import numpy as np

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    new_elms = sorted(values[i], reverse=True)[:M-i+1]
    elms += new_elms
    if len(elms) >= 1:
        max_val = max(elms)
        out += max_val
        elms.remove(max_val)

print(out)

Submission status: Time Limit Exceeded

Solution code:
#input = raw_input
#import numpy as np

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    new_elms = sorted(values[i], reverse=True)[:M-i+1]
    elms += new_elms
    if len(elms) >= 1:
        max_val = max(elms)
        out += max_val
        elms.remove(max_val)

print(out)

Submission status: Time Limit Exceeded

Solution code:
#input = raw_input
#import numpy as np

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    elms += values[i]
    if len(elms) >= 1:
        max_val = max(elms)
        out += max_val
        elms.remove(max_val)

print(out)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
d=[]
sum=0
e=0
for i in range(1,b+1):
  for j in range(e,a):
    if c[j][0]<=i:
      d.append(c[j][1])
    else:
      e=j
      break
  d.sort()
  if len(d)>0:
    sum+=d[-1]
    d.pop()
      
    
  
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
case = sorted([[int(j) for j in input().split()] for i in range(N)], key=lambda x: (-x[0]))

candidate_list = []
ans = 0

for i in range(1, M + 1):
    while case:
        if case[-1][0] <= i:
            candidate_list.append(case.pop(-1))
        else:
            break

    if candidate_list:
        candidate_list.sort(key=lambda x: (x[1]))
        ans += candidate_list.pop(-1)[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
H = [[] for _ in range(M)]
 
for _ in range(N):
    A, B = map(int, input().split())
    if A <= M:
        H[A - 1].append(-B)
        
Q = []
c = 0
for d in range(M):
    for b in H[d]:
        Q.append(b)
    if Q:
        c -= min(Q)
        Q.remove(min(Q))
print(c)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
AB = []

for i in range(N):
  ab = list(map(int, input().split()))
  #Ai > M の仕事はいらない
  if ab[0] <= M:
    AB.append(ab)

#最終日はAi=1の仕事のみ選べる。その前の日はAi<=2, ...
#終わりから考えればよさそう
AB.sort()
hq = []
ans = 0
for i in range(1, M + 1):
  while len(AB) > 0 and AB[0][0] <= i:
    heappush(hq, -1 * AB.pop(0)[1])
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
d=[[]for i in range(b+1)]
for i in c:
  if i[0]<=b:
    e=i[0]
    d[e].append(i[1])
    
for i in range(b+1):
  d[i].sort()
sum=0
for i in range(b+1):
  e=0
  f=0
  for j in range(i+1):
    if len(d[j])!=0:
      if e<=d[j][-1]:
        f=j
        e=d[j][-1]    
  sum+=e
  if f>0:
    d[f].pop()
      
    
  
print(sum)

Submission status: Time Limit Exceeded

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

for i in range(N):
  ab = list(map(int, input().split()))
  #Ai > M の仕事はいらない
  if ab[0] <= M:
    AB.append(ab)

#最終日はAi=1の仕事のみ選べる。その前の日はAi<=2, ...
#終わりから考えればよさそう
AB.sort()
q = []
ans = 0
for i in range(1, M + 1):
  while len(AB) > 0 and AB[0][0] <= i:
    q.append(AB.pop(0)[1])
  if len(q) > 0:
    m = max(q)
    q.remove(m)
    ans += m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d = list(map(int, input().split(" ")))
works = []
m = 0
for _ in range(n):
    x,y = map(int, input().split(" "))
    if x <= d:
        works.append([x,y])
        m += 1
works.sort(reverse=True)

money = 0

j = 0
chosen = []
while(0<d):
    candi_n = -1
    candi_m = 0
    searching_j = True
    for i in range(j,m):
        if i in chosen:
            continue
        if searching_j and works[i][0] < d:
            searching_j = False
            j = i
        if candi_m < works[i][1]:
            candi_n = i
            candi_m = works[i][1]
    if candi_n < 0:
        break
    chosen.append(candi_n)
    money += candi_m
    d -= 1

print(money)