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:
import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()

A=[0]*m
heapq.heapify(A)
#日がたつごとに選択肢が少なくなる→後ろから見ていく
ans=0
for day in range(m):
    for a,b in ab:
        if a<day+1:continue
        if a==day+1:
            heapq.heappush(A,-b)
        else:
            temp=heapq.heappop(A)
            ans+=temp
            #print(temp)
            break
    else:
        ans+=heapq.heappop(A)
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, [])
    d[a].append(b)
ans = 0
l = []
for i in range(1, m+1):
    for p in sorted(d.get(i, []))[::-1]:
        index = bisect.bisect_left(l, p)
        if len(l) <= m-i or index != 0:
            l.insert(index, p)
        else:
            break
    if l:
        ans += l.pop(-1)
    while(len(l) > m-i):
        l.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

dls = list(reversed(sorted(dls)))
memo = {}

def doit(index, time):
  if index >= n:
    return 0
  if (index, time) not in memo:
    a = doit(index + 1, time)
    w, r = dls[index]
    if time + w > m:
      b = 0
    else:
      b = r + doit(index + 1, time + 1)
    memo[(index, time)] = max(a, b)
  return memo[(index, time)]

print(doit(0, 0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
N, M = [int(s) for s in input().split()]
rewards = []

allocation_day = [0]*M

for i in range(N):
    a, b = [int(s) for s in input().split()]
    rewards.append((a, b))

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

for a, b in rewards:
    while (a <= M):
        if allocation_day[a - 1] == 0:
            allocation_day[a - 1] = b
            break
        a += 1

print(sum(allocation_day))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, [])
    d[a].append(b)
ans = 0
l = []
for i in range(1, m+1):
    for p in sorted(d.get(i, []))[::-1]:
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
        else:
            break
    if l:
        ans += l.pop(-1)
    while(len(l) > m+1-i):
        l.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in sorted(d.get(i, []))[::-1]:
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
        else:
            break
    if l:
        ans += l.pop(-1)
    while(len(l) > m+1-i):
        l.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in sorted(d.get(i, []))[::-1]:
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
        else:
            break
    if l:
        ans += l[-1]
        l = l[:-1]
    while(len(l) > m+1-i):
        l = l[1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in sorted(d.get(i, []))[::-1]:
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
            while(len(l) > m+1-i):
                l = l[1:]
        else:
            break
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = sorted(d.get(a, []) + [b])[::-1]
ans = 0
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
            while(len(l) > m+1-i):
                l = l[1:]
        else:
            break
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        index = bisect.bisect_left(l, p)
        if len(l) <= m+1-i or index != 0:
            l.insert(index, p)
            while(len(l) > m+1-i):
                l = l[1:]
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
        while(len(l) > m+1-i):
            l = l[1:]
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
        while(len(l) > m+1):
            l = l[1:]
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(' ')))
#5 3
#1 2
#1 3
#1 4
#2 1
#3 3 
#------
#2 2 2
#3 3 3
#4 4 4
#1 1
#3
#------ 縦で最大のモノをとる
#    4
#  3
#3
import bisect
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
#print(d)
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
    if l:
        ans += l[-1]
        l = l[:-1]
        while(len(l) > m+10):
            l = l[1:]
#print(l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(' ')))
#5 3
#1 2
#1 3
#1 4
#2 1
#3 3 
#------
#2 2 2
#3 3 3
#4 4 4
#1 1
#3
#------ 縦で最大のモノをとる
#    4
#  3
#3
import bisect
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
#print(d)
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
    if l:
        ans += l[-1]
        l = l[:-1]
        while(len(l) > m+50):
            l = l[1:]
#print(l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m = list(map(int, input().split(' ')))
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
    if l:
        ans += l[-1]
        l = l[:-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split(' ')))
#5 3
#1 2
#1 3
#1 4
#2 1
#3 3 
#------
#2 2 2
#3 3 3
#4 4 4
#1 1
#3
#------ 縦で最大のモノをとる
#    4
#  3
#3
import bisect
d = {}
for i in range(n):
    a, b = list(map(int, input().split(' ')))
    d[a] = d.get(a, []) + [b]
ans = 0
#print(d)
l = []
for i in range(1, m+1):
    for p in d.get(i, []):
        bisect.insort_left(l, p)
    if l:
        ans += l[-1]
        l = l[:-1]
#print(l)
print(ans)

Submission status: Time Limit Exceeded

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

import heapq

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

dict = {}
for i in range(n):
    ta, tb = map(int, input().split())
    #後でheapqから最大値を取り出したいので-1倍して追加
    if dict.get(ta) == None:
        dict[ta] = []
        dict[ta].append(tb * -1) #新しいAiを追加
    else:
        dict[ta].append(tb * -1) #既存のAiにBiを追加
#print(dict)

cand = []
ans = 0
for i in range(1, m+1):
    #１　要素の追加
    if dict.get(i) == None:
        pass
    else:
        add = dict[i]
        cand.extend(add)
        heapq.heapify(cand) #ヒープ化
        #print(cand)

    #２　heapから最大値を取り出す
    try:
        max_val = heapq.heappop(cand)
        #print(max_val)
        ans += max_val * (-1) #最大値に直す
    except: #heapに何も入っていない
        pass
#print("----")
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split(' '))
    dict_works = dict()
    list_days = list()
    for n in range(1, N + 1):
        a, b = map(int, input().split(' '))
        if a > M:
            continue
        list_days.append(a)
        if a in dict_works:
            dict_works[a].append(b)
            dict_works[a].sort(reverse=True)
        else:
            dict_works[a] = [b]
    list_days = tuple(set(list_days))
    list_odd = [0]
    list_result_days = list()
    for t in range(1, M + 1):
        if t in list_days:
            t_max = dict_works[t][0]
            try:
                if t_max > max(list_odd):
                    if len(dict_works[t]) > 1:
                        list_odd += dict_works[t][1:]
                    list_result_days.append(t_max)
                else:
                    list_odd += dict_works[t]
                    list_result_days.append(max(list_odd))
                    list_odd.remove(max(list_odd))
            except ValueError:
                if len(dict_works[t]) > 1:
                    list_odd += dict_works[t][1:]
                list_result_days.append(t_max)
        elif len(list_odd) > 1:
            list_result_days.append(max(list_odd))
            list_odd.remove(max(list_odd))
        else:
            continue
    print(sum(list_result_days))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split(' '))
    dict_works = dict()
    for n in range(1, N + 1):
        a, b = map(int, input().split(' '))
        if a > M:
            continue
        if a in dict_works:
            dict_works[a].append(b)
            dict_works[a].sort(reverse=True)
        else:
            dict_works[a] = [b]
    result = 0
    for x in range(1, M + 1):
        max_value = 0
        day = 0
        for n in range(x, 0, -1):
            if n in dict_works:
                if dict_works[n][0] > max_value:
                    day = n
                    max_value = dict_works[n][0]
        if day:
            result += dict_works[day][0]
            del dict_works[day][0]
            if len(dict_works[day]) == 0:
                del dict_works[day]

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)


def solve(N, M, A):
    A = sorted(A, key=lambda x: x[1], reverse=True)

    sch = list(range(M))

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        id = koenai_saidai_x_index(sch, day)
        #print(sch)
        #print(nouki, money, id)
        if id is False:
            continue
        sch.pop(id)

        ret += money

    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)


def solve(N, M, A):
    A = sorted(A, key=lambda x: x[1], reverse=True)

    sch = list(range(M))
    heapq.heapify(sch)

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        id = koenai_saidai_x_index(sch, day)
        #print(sch)
        #print(nouki, money, id)
        if id is False:
            continue
        sch.pop(id)
        ret += money

    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)


def solve(N, M, A):
    A = sorted(A, key=lambda x: x[1], reverse=True)

    sch = list(range(M))

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        id = koenai_saidai_x_index(sch, day)
        #print(sch)
        #print(nouki, money, id)
        if id is False:
            continue
        sch.pop(id)
        ret += money

    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)


def solve(N, M, A):
    A = sorted(A, key=lambda x: x[1], reverse=True)

    sch = [False] * M

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        do = True
        while True:
            if sch[day]:
                day -= 1
            else:
                break
            if day == -1:
                do = False
                break
        if not do:
            continue

        sch[day] = True
        ret += money

        # print(nouki, money)

    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)

def solve(N, M, A):
    A = sorted(A, key=lambda x:x[1], reverse=True)

    sch = [False] * M

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        do = True
        while True:
            if sch[day]:
                day -= 1
            else:
                break
            if day == -1:
                do = False
                break
        if not do:
            continue

        sch[day] = True
        ret += money

        #print(nouki, money)

    return ret




#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

W = [[0]*2 for i in range(N)]

for i in range(N):
   W[i][0], W[i][1] = map(int, input().split())

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

P = [0]*M

for i in range(N):
    for j in range(M-1, -1, -1):
        if P[j] == 0 and j+W[i][0]<=M:
            P[j] = W[i][1]
            break

print(sum(P))

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
l=[]
e=0
for i in range(1,m+1):
  while e<n and ab[e][0]==i:
    l.append(ab[e][1])
    e+=1
  if len(l)>0: 
    ans+=max(l)
    l.remove(max(l))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
X = []
for i in range(N):
    X.append(list(map(int, input().split())))
X.sort(key=lambda x: (-x[1], x[0]))

days = [i for i in range(1, M+1)]
ans = 0
for a, b in X:
    if len(days) == 0:
        break
    if days[-1] < a:
        continue
    index = bisect.bisect_right(days, a)
    if index > 0 and days[index-1] >= a:
        days.pop(index-1)
    elif index > 0 and days[index-1] <a:
        days.pop(index) 
    elif index == 0 and days[0] >= a:
        days.pop(0)
    else:
        continue
    ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
job = {}
for i in range(N):
    A,B = map(int,input().split())
    job.setdefault(A,[]).append(B)
ans = 0
last = min(job.keys())
for i in range(last,M+1):
    option = sorted(job[i])
    if(option != []):
        today = option.pop()
        ans += today
    job.setdefault(i+1,[]).extend(option)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
job = {}
for i in range(N):
    A,B = map(int,input().split())
    job.setdefault(A,[]).append(B)
ans = 0
last = min(job.keys())
for i in range(last,M+1):
    if(job[i] != []):
        today = max(job[i])
        ans += today
        job[i].remove(today)
    job.setdefault(i+1,[]).extend(job[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop, merge, heapify

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
works = [[] for _ in range(M+1)]
#Bが報酬
for _ in range(N):
    a, b = lr()
    if a <= M:
        works[a].append(-b)

cand = []
answer = 0
for i in range(1, M+1):
    cand = list(merge(cand, works[i]))
    heapify(cand)
    if cand:
        answer -= heappop(cand)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(N)]
#Bが報酬
AB = [(a, b) for a, b in AB if a<=M]
AB.sort(reverse=True, key=lambda x: x[1])
AB = deque(AB)
answer = 0
used = set()
out = set()
while AB:
    x, y = AB.popleft()
    if x > M or x in out:
        continue
    else:
        z = x
        while z in used:
            if z in out:
                z = M+1
            z += 1
        if z > M:
            out = out.union(set(range(x, z)))
            continue
        used.add(z)
        answer += y

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(N)]
#Bが報酬
AB = [(a, b) for a, b in AB if a<=M]
AB.sort(reverse=True, key=lambda x: x[1])
AB = deque(AB)
answer = 0
used = set()
out = set()
while AB:
    x, y = AB.popleft()
    if x > M or x in out:
        continue
    else:
        z = x
        while z in used:
            z += 1
        if z > M:
            out = out.union(set(range(x, z)))
            continue
        used.add(z)
        answer += y

print(answer)