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:
#!/usr/bin/env python3
import sys
import collections
from operator import itemgetter


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    jobs_time = collections.defaultdict(list)
    for a,b in zip(A,B):
        jobs_time[b].append(a)

    jobs_time = sorted(jobs_time.items(),reverse=True)
    job_list = [0] * M

    for k,v in jobs_time: 
        v.sort()
        st = -1
        for vv in v:
            if vv <= M:
                for i in range(max(st,vv-1),len(job_list)):
                    if job_list[i] < k:
                        job_list[i] = k
                        st = min(i+1,len(job_list))
                        break
            else:
                break

        if all(j>0 for j in job_list):
            break

    print(sum(job_list))

    return

def solve2(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((b,a))

    jobs_time = sorted(jobs_time,key=itemgetter(0,1),reverse=True)
    job_list = [0] * M
    job_cnt = 0
    for b,a in jobs_time: 
        if a <= M:
            for i in range(a-1,len(job_list)):
                if job_list[i] < b:
                    if job_list[i] == 0:
                        job_cnt += 1
                    job_list[i] = b
                    break
        if job_cnt >= len(job_list):
            break

    print(sum(job_list))


# 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))
    solve2(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

BA=sorted(AB, key=lambda x: (x[1],x[0]))

scadule = [0]*M
full=0
for work in reversed(BA):
    if work[0]>M:
        continue
    try:
        day = scadule[work[0]-1:].index(0)
        scadule[day+work[0]-1] = work[1]
        full+=1
#        print(tmp_li,work,day,scadule)
    except:
        continue
    if full > M:
        break

ans=sum(scadule)

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

dp = [0 for _ in range(100000)]

def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split()))[::-1] for _ in range(N)]
    logging.info("Hello!")

    sorted_A_B = sorted(A_B, reverse=True)
    logging.info(sorted_A_B)


    total = 0
    for i in range(N):
        if i >= M:
            break
        
        if sorted_A_B[i][1] + i <= M and sorted_A_B[i][0] != -1:
            total += sorted_A_B[i][0]
            sorted_A_B[i][0] = -1

        else:
            for k in range(i, N):
                if sorted_A_B[k][1] + i <= M and sorted_A_B[k][0] != -1:
                    total += sorted_A_B[k][0]
                    sorted_A_B[k][0] = -1


    print(total)
    
if __name__ == "__main__":
    main()

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)

sorted_AB_list = 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 = map(int,input().split())
li=[[] for _ in range(m)]
for _ in range(n):
  ai,bi = map(int,input().split())
  if ai <= m:
    li[ai-1].append(bi)
pos = []
sm = 0
for i in range(m):
  pos.extend(li[i])
  pos.sort(reverse=True)
  if len(pos) > m-i:
    pos = pos[:m-i]
  if len(pos) > 0:
    s = pos.pop(0)
    sm += s
print(sm)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ba = []
m1 = m + 2
days = [0 for _ 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
    if a1 >= m1:
        continue
    mb = m1
    m1 = a1
    for i in range(m - a1 + 1):
        if days[a1 + i] == 0:
            days[a1 + i] = 1
            cnt += b1
            m1 = mb
            break
print(cnt)

Submission status: Time Limit Exceeded

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

CBList = []

for i in range(N):
    A, B = map(int, input().split())
    C = M - A
    CBList.append((C, B))

CBList = sorted(CBList)

ansList = [0] * (M+1)
for i in range(N):
    day = CBList[i][0]
    if day > 0:
        minB = min(ansList[0:day+1])
        minday = ansList.index(minB)
        if minB < CBList[i][1]:
            ansList[minday] = CBList[i][1]
    elif day == 0 and ansList[0] < CBList[i][1]:
        ansList[0] = CBList[i][1]
print(sum(ansList))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()
jobs = list(map(lambda s:list(map(int,s.split(" "))), sys.stdin.readlines()))

jobs.sort(key=lambda job: job[0])
jobs.sort(key=lambda job: job[1], reverse=True)


mark = [True] * (m+1)
ans = 0
for job in jobs:
    nouki = job[0]
    if nouki <= m:
        while (not mark[nouki]) and (nouki < m):
            nouki += 1
        if nouki > m:
            continue
        if mark[nouki]:
            ans += job[1]
            mark[nouki] = False
        # elif mark[m]:
            # # にぶたん
            # # left 既知の右端False
            # left = nouki
            # # right 既知の左端True
            # right = m
            # while(left < right-1):
            #     center = (left+right)//2
            #     if(mark[center]):
            #         right = center
            #     else:
            #         left = center
            # ans += job[1]
            # mark[right] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]
works.sort(key=lambda x:(-x[1], -x[0]))
days = [0] * (M+1)
ans = 0
for work in works:
  if work[0] > M:
    continue
  for day in range(work[0], M+1):
    if days[day] == 0:
      days[day] = 1
      ans += work[1]
      full = False
      break
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)]
for i in range(N):
    A, B = map(int,input().split())
    Y[A].append(B)

cnt = 0
C = [0]*100000
#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)
    a = max(C)
    cnt = cnt + a
    C.remove(a)
    #del C[0]

print(cnt)

Submission status: Time Limit Exceeded

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


time_reward_tuple = []


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

    
job_que = []


total = 0


for j in range(1, m+1):
    for l in [r for t, r in time_reward_tuple if t==j]:
        job_que.append(l)


    if job_que:
        job_que.sort()
        total += job_que.pop()
        
    
    
print(total)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# import bisect
# import math
from numpy import array, where

# from fractions import gcd
# import itertools

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def make_divisors(n):
    # divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            # divisors.append(i)
            return i
            # if i != n // i:
            #     divisors.append(n//i)


def n_to_10(X, n):
    if int(X / n):
        return n_to_10(int(X / n), n) + str(X % n)
    return str(X % n)


def main():
    ip = IP()
    id = Idea()
    """この下から書いてね"""
    n, m = ip.IL()
    ab = ip.SILS(n)
    id.S(ab, 1, 0)
    id.S(ab, 1, 1)
    hantei = [False for _ in range(m)]
    # print(hantei)
    # print(ab)
    ans = 0
    day = 1
    for x in ab:
        if not all(hantei[:x[0]]) and not all(hantei[x[0]-1:]):
            # print(x)
            # print(hantei)
            ans += x[1]
            day += 1
            memo = where(array(hantei[x[0]-1:]) == False)
            # print(hantei[x[0]-1:])
            # print("memo", memo)
            # print(memo[0][-1])
            hantei[memo[0][-1] + x[0] - 1] = True
        # if day == m:
            # break
    # print(hantei)
    print(ans)


main()

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 = map(int,input().split())
# AB_s = [list(map(int,input().split())) for _ in range(N)]
dicts = {i:[] for i in range(1,M+1)}
for _ in range(N):
    A,B = map(int,input().split())
    if A in dicts:
        dicts[A].append(B)
answer = 0
wages = []
for i in range(1,M+1):
    wages.extend(dicts[i])
    if wages:
        wages.sort()
        answer += wages.pop()
print(answer)
# AB_s = sorted(AB_s, key=lambda x:-x[0])
# print(AB_s)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n,m=map(int,input().split())
ab = {}
for _ in range(n):
    a,b=map(int,input().split())
    ab.setdefault(a, []).append(b)
for k in ab:
    ab[k] = sorted(ab[k], reverse=True)
c = 0
for i in range(1,m+1):
    t = []
    for j in range(i):
        idx=i-j
        if idx not in ab:
            continue
        t.append((idx,ab[idx][0]))
    if t:
        t = sorted(t, key=lambda v: (-v[1], v[0]))
        c += t[0][1]
        ab[t[0][0]].remove(t[0][1])
        if not ab[t[0][0]]:
            del ab[t[0][0]]
print(c)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect
N,M = [int(x) for x in input().split()]

work = [[int(x) for x in input().split()]for _ in range(N)]
#%%
dp = [0]*(M+1)
work.sort(key=itemgetter(0))
work.sort(key=itemgetter(1))
#%%
days = [i[0] for i in work]
seen = set()
cnt = 0
for i in range(1,M+1):
    nonused = []
    while(len(work)>0):
        x = work.pop()
        if(x[0]>i):
            nonused.insert(0,x)
        else:
            break
    #print(i,x)
    if(x[0]<=i):
        cnt += x[1]
    work += nonused

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if not A in C:
        C[A] = []
    C[A].append(B)
for i in C:
    C[i] = deque(sorted(C[i])[::-1])

answer = 0
tmp = deque()

for i in range(1, M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = C[i]
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        else:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

Submission status: Time Limit Exceeded

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

# from fractions import gcd
# import itertools

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

    def lcm(self, x, y):
        return (x * y) // self.gcd(x, y)


"""ここからメインコード"""


def make_divisors(n):
    # divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            # divisors.append(i)
            return i
            # if i != n // i:
            #     divisors.append(n//i)


def n_to_10(X, n):
    if int(X / n):
        return n_to_10(int(X / n), n) + str(X % n)
    return str(X % n)


def main():
    ip = IP()
    id = Idea()
    """この下から書いてね"""
    n, m = ip.IL()
    ab = ip.SILS(n)
    id.S(ab, 1, 0)
    id.S(ab, 1, 1)
    hantei = [False for _ in range(m)]
    # print(hantei)
    # print(ab)
    ans = 0
    day = 1
    for x in ab:
        try:
            if not all(hantei[:x[0]]) and not all(hantei[x[0]-1:]):
                # print(x)
                # print(hantei)
                ans += x[1]
                day += 1
                memo = np.where(np.array(hantei[x[0]-1:]) == False)
                # print(hantei[x[0]-1:])
                # print("memo", memo)
                # print(memo[0][-1])
                hantei[memo[0][-1] + x[0] - 1] = True

        except IndexError:
            pass
        # if day == m:
            # break
    # print(hantei)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

dy = 0
ans = 0
total_dy = 0
cnt = 0
while total_dy <= M:
    for i, x in enumerate(B):
        if x == max(B):
            if cnt == 0:
                tmp_max_idx = i
                cnt += 1
            elif cnt > 0 and A[tmp_max_idx] < A[i]:
                tmp_max_idx = i
    cnt = 0
    tmp_max = max(B)
    if A[tmp_max_idx]+dy <= M:
        ans += tmp_max
        total_dy = A[tmp_max_idx] + dy
        dy += 1

    A.pop(tmp_max_idx)
    B.pop(tmp_max_idx)
    tmp_max_idx = 0
    if A == [] or B ==[]:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
T = defaultdict(list)
for _ in range(N):
    A, B = map(int, input().split())
    T[A].append(B)
num = 0
for m in range(1, M + 1):
    T[m].sort()
    if len(T[m]) > 0:
        x = T[m].pop()
        num += x
        T[m + 1].extend(T[m])
print(num)

Submission status: Time Limit Exceeded

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

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

BA=sorted(AB, key=lambda x: (x[1],x[0]))

scadule = [0]*M
for work in reversed(BA):
    try:
        tmp_li = scadule[work[0]-1:]
        day = tmp_li.index(0)
        scadule[day+work[0]-1] = work[1]
#        print(tmp_li,work,day,scadule)
    except:
        continue

ans=sum(scadule)

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for i in range(1,m+1):
    while True:
        if ab[t][0] > i:
            break
        index = bisect.bisect_left(x, ab[t][1])
        x.insert(index, ab[t][1])
        t += 1
    
    if len(x) != 0:
        ans += x.pop(len(x) - 1)

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

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]
        key_all.append(a)
    else:
        d[a].append(b)

key_all.sort()

ans = 0
l = []
import bisect

mm = key_all[-1]
for i in range(1, min(mm, m) + 1):
    if i == key_all[0]:
        for v in d[i]:
            bisect.insort(l, v)

        key_all.pop(0)

    if l != []:
        ans += l.pop()

if m > mm:
    for i in range(mm + 1, m + 1):
        if l != []:
            ans += l.pop()


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

workList = list()
for _ in xrange(N):
    workList.append(map(int, raw_input().split()))

# workList.sort(key=lambda x: (x[0], x[1]))
# workList.reverse()

d = defaultdict(list)

for day, wage in workList:
    d[day].append(wage)

availableWorkList = list()
totalWage = 0
for remainingDay in xrange(1, M+1):
    availableWorkList.extend(d[remainingDay])
    if availableWorkList:
        todaysWage = max(availableWorkList)
        totalWage += todaysWage
        availableWorkList.pop(availableWorkList.index(todaysWage))

print totalWage

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
work = [0] * N
for i in range(N):
    work[i] = [0] * 2
    work[i][1], work[i][0] = map(int, input().split())
ans = 0
work_money = sorted(work)
schedule = [0]*M
for j in range(N):
    day = M - work_money[N - 1 - j][1]
    day_index = day
    while day_index >= 0:
        if schedule[day_index] == -1:
            break
        if schedule[day_index] == 0:
            if day_index > 0:
                if schedule[day_index - 1] == -1:
                    schedule[day_index] = -1
                    ans += work_money[N - 1 - j][0]
                    break
            schedule[day_index] = 1
            ans += work_money[N - 1 - j][0]
            break
        day_index -= 1
        if day_index == -1:
            schedule[day] = -1
print(ans)

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:
            i = 1
            while(True):
                if dayprice[a_b[0] + i] == 0:
                    dayprice[a_b[0] + i] = a_b[1]
                    break
                i += 1
    except Exception as e:
        continue

print(sum(dayprice))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
# N, M = 10**5, 10**5
ab = [0]*N
for i in range(N):
    a, b = map(int, input().split())
    # a, b = i, i
    ab[i] = (a, b)


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

# print(ab)

ans_list = [(0, 0)]*M
for i in range(1, M+1):
    if not ab:  # 仕事がなくなる
        break
    if ab[0][0] > i:  # 次にできる仕事の始められる日にジャンプ
        continue

    index = 0
    kane = 0
    for j, (a, b) in enumerate(ab):
        if a > i:
            break
        if kane <= b:
            kane = b
            index = j
    ans_list[i-1] = ab.pop(index)

# print(ans_list)
ans = 0
for a, b in ans_list:
    ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ls = []
for n in range(N):
  ls.append(list(map(int,input().split())))
ls = sorted(ls, key=lambda x:x[1],reverse=True)

days = {i:0 for i in range(1,M+1)}
sum = 0
max_d = max(days.keys())
for work in ls:
  d = work[0]
  while(d<=max_d):
    if d in days:
      sum+=work[1]
      days.pop(d)
      key = days.keys()
      if len(key)==0:
        max_d = 0
      else:
        max_d = max(days.keys())
      d=M+1
    else:
      d+=1
print (sum)

Submission status: Time Limit Exceeded

Solution code:

import sys
from operator import attrgetter

def main():
    N,M = [int(i) for i in sys.stdin.readline().strip().split()]
    works = [[] for i in range(10**5+1)]
    ans = 0
    for i in range(N):
        A,B = [int(i) for i in sys.stdin.readline().strip().split()]
        works[A].append(B)
    
    avaiable_works = []
    for i in range(M+1):
        avaiable_works.extend(works[i])
        if len(avaiable_works) > 0:
            revenue = max(avaiable_works)
        else:
            continue
        ans += revenue
        avaiable_works.remove(revenue)
    
    print("%d" % ans)



def solve(N, M, works):
    ans = 0

    return 0



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a_b_list = []


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


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

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

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

print(total_value)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

A=[]
B=[]
for i in range(N):
	a, b = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7
	A.append([a,b])

B = sorted(A, key=lambda x:(-x[1],-x[0]))

X=[0]*(M+1)

p("A ",A)
p("B ",B)
p("X ",X)


i_min = 1
for L in B:
	d = L[0]
	m = L[1]
	
	
	for i in range(i_min+d-1, M+1):
		if X[i]==0:
			i_min = min(i_min, i)
			X[i]=m
			break

p("X ",X)

print( sum(X) )

Submission status: Time Limit Exceeded

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

dic = set([i+1 for i in range(m)])
ans = 0
for a, b in ab:
  while(True):
    if a <= m:
      if a in dic:
        dic.remove(a)
        ans += b
        break
      else:
        a += 1
    else:
      break
print(ans)