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 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.add(x)
            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()
while AB:
    x, y = AB.popleft()
    if x > M:
        continue
    else:
        while x in used:
            x += 1
        if x > M:
            continue
        used.add(x)
        answer += y

print(answer)

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(key=lambda x:x[0])
AB.append([10**5+1,0])
h=[]
ans=0
for i in range(1,M+1):
  while AB[0][0]<=i:
    heapq.heappush(h,-AB.pop(0)[1])
  if len(h)>0:
    ans+=-heapq.heappop(h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

for i in range(N):
    if i <= M:
        heapq.heapify(mission[i])
    A[i],B[i] = map(int,(input().split()))
    if A[i] <= M:
        mission[A[i]].append(-B[i])

for day in range(1,M+1):
    mission[day].extend(mission[day-1])
    if mission[day]:
        heapq.heapify(mission[day])
        work += heapq.heappop(mission[day])

print(-work)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n)]
    ab.sort()
    c=[0]*n
    ans=0
    for i in range(1,m+1):
        mb=0
        mnum=-1
        for j in range(n):
            if ab[j][0]<=i:
                if mb<ab[j][1] and c[j]==0:
                    mb=ab[j][1]
                    mnum=j
            else:
                break
        ans+=mb
        if mnum!=-1:
            c[mnum]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Summer Vacation
https://atcoder.jp/contests/abc137/tasks/abc137_d

"""
import sys


from heapq import heapify, heappop
from bisect import bisect_left

def solve(N, M, jobs):
    days = [d for d in range(1, M+1)]
    heapify(jobs)
    ans = 0
    while jobs:
        B, A = heappop(jobs)
        i = bisect_left(days, -A)
        if i != len(days):
            days.pop(i)
            ans -= B
    return ans


def main(args):
    N, M = map(int, input().split())
    jobs = []
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append([-B, -A])
    ans = solve(N, M, jobs)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
def o():return map(int,input().split())
n,m=o()
c=[[0] for i in range(m)]
for i in range(n):
  a,b=o()
  if a<=m:
    c[m-a]+=[b]
d=[]
for i in range(m):
  c[i].sort()
  d+=[c[i].pop()]
ans=0
for i in range(m-1,-1,-1):
  j=i+d[i:].index(max(d[i:]))
  if d[j]>0:
    ans+=d[j]
    d[j]=c[j].pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int,input().split())
jobs = [[] for i in range(10 ** 5 + 1)]
lst = []

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

ans = 0

for i in range(1,M+1):
    lst += jobs[i]
    if lst:
        heapq.heapify(lst)
        k = heapq.heappop(lst)
        ans += (-1) * k

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))
ab.sort(key=lambda x:x[1], reverse=True)
ans = 0
for i in range(1, m+1):
    for j in range(len(ab)):
        if ab[j][0] <= i:
            res = ab.pop(j)
            ans += res[1]
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
finput = sys.stdin.readline
n,m = map(int, finput().split())

tasks = [0]*n
rewards = [0]*n
total = [0]*(m+1)

for i in range(n):
    tasks[i],rewards[i] = [int(j) for j in finput().split()]

que = [idx for idx, item in enumerate(rewards) if item == max(rewards)]

day = 0
minflag = [idx for idx, item in enumerate(tasks) if item == min(tasks)]

while que:
    subtasks = [tasks[i] for i in que]
    while subtasks:
        t = max(subtasks)
        idx = subtasks.index(t)
        if t+day <= m:
            total[t+day:m+1] = [total[i]+rewards[que[idx]] for i in range(t+day,m+1)]
            day += 1
        del subtasks[idx]
        del tasks[que[idx]]
        del rewards[que[idx]]
        if que[idx] in minflag:
            del minflag[minflag.index(que[idx])]
            if minflag==[]:
                minflag = [idx for idx, item in enumerate(tasks) if item == min(tasks)]
        del que[idx]
        
    if rewards==[]:
        break
    if day+min(tasks)>m:
        break
    que += [idx for idx, item in enumerate(rewards) if item == max(rewards)]

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
import sys
finput = sys.stdin.readline
n,m = map(int, finput().split())

tasks = [0]*n
rewards = [0]*n
total = [0]*(m+1)

for i in range(n):
    tasks[i],rewards[i] = [int(j) for j in finput().split()]

que = [idx for idx, item in enumerate(rewards) if item == max(rewards)]

day = 0

while que:
    subtasks = [tasks[i] for i in que]
    while subtasks:
        t = max(subtasks)
        idx = subtasks.index(t)
        if t+day <= m:
            total[t+day:m+1] = [total[i]+rewards[que[idx]] for i in range(t+day,m+1)]
            day += 1
        del subtasks[idx]
        del tasks[que[idx]]
        del rewards[que[idx]]
        del que[idx]
    if rewards==[]:
        break
    if day+min(tasks)>m:
        break
    que += [idx for idx, item in enumerate(rewards) if item == max(rewards)]

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
import sys
finput = sys.stdin.readline
n,m = map(int, finput().split())

tasks = [0]*n
rewards = [0]*n
total = [0]*(m+1)

for i in range(n):
    tasks[i],rewards[i] = [int(j) for j in finput().split()]

que = [idx for idx, item in enumerate(rewards) if item == max(rewards)]

day = 0

while que:
    subtasks = [tasks[i] for i in que]
    while subtasks:
        t = max(subtasks)
        idx = subtasks.index(t)
        if t+day <= m:
            total[t+day:m+1] = [total[i]+rewards[que[idx]] for i in range(t+day,m+1)]
            day += 1
        del subtasks[idx]
        del tasks[que[idx]]
        del rewards[que[idx]]
        del que[idx]
    if rewards==[]:
        break
    que += [idx for idx, item in enumerate(rewards) if item == max(rewards)]

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from heapq import heapify, heappop, heappush
N, M = map(int, input().split())
AB = []
heapify(AB)
d = {}
for _ in range(N):
    a, b = list(map(int, input().split()))
    if a > M:
        continue
    if a not in d.keys():
        d[a] = [-b]
    else:
        d[a].append(-b)
ans = 0
ables = []
now = 1
while now <= M:
    if now in d.keys():
        for v in d[now]:
            heappush(ables, v)
    if len(ables) > 0:
        v = heappop(ables)
        ans += -1 * v
    now += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, M = map(int, input().split())
AB = []
d = {}
g = {}
for _ in range(N):
    a, b = list(map(int, input().split()))
    # AB.append(tmp[:])
    if a > M:
        continue
    if a not in d.keys():
        d[a] = [b]
        g[a] = [False]
    else:
        d[a].append(b)
        g[a].append(False)
day = 0
ans = 0
for i in range(M):
    good = -1
    flag = False
    for key in list(sorted(d.keys(), reverse=True)):
        if key + day > M:
            continue
        for j in range(len(d[key])):
            if good < d[key][j] and not g[key][j]:
                good = d[key][j]
                idx = key
                jdx = j
                flag = True
    if flag:
        g[idx][jdx] = True
        ans += good
    day += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[] for i in range(m)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(-b)
tmp=[]
ans=0
for i in range(m):
  tmp+=l[i]
  heapq.heapify(tmp)
  if len(tmp)>0:
    ans+= heapq.heappop(tmp)
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m=map(int,input().split())
l=[[] for i in range(m)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(-b)
tmp=[]
ans=0
for i in range(m):
  tmp+=l[i]
  heapq.heapify(tmp)
  if len(tmp)>0:
    ans+= heapq.heappop(tmp)
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, M = map(int, stdin.readline().split())
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = map(int, stdin.readline().split())

salary = 0
for i in range(1, M+1):
    assignable = [j for j, a in enumerate(A) if a <= i]
    if assignable:
        most_attractive_i = assignable[0]
        for _ in assignable:
            if B[_] > B[most_attractive_i]:
                most_attractive_i = _
        salary += B[most_attractive_i]
        A[most_attractive_i] = 100000+1

print(salary)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

data_list = [[0] for _ in range(m)]

for i in range(n):
    if data[i][0]-1 < m:
        data_list[data[i][0]-1].append(-data[i][1])

heap_list = []
heapq.heapify(heap_list)

ans = 0
for i in range(0, m):
    heap_list.extend(data_list[i])
    heapq.heapify(heap_list)
    a = heapq.heappop(heap_list)
    ans += a

print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

ans = 0
for i in range(1, m+1):
    tmp = 0
    tmpidx = -1
    for j in range(len(data)-1, -1, -1):
        if data[j][0] <= i:
           if tmp < data[j][1]:
               tmp = data[j][1]
               tmpidx = j
    if tmpidx != -1:
        ans += tmp
        data[tmpidx][1] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

ans = 0
for i in range(1, m+1):
    tmp = 0
    tmpidx = -1
    for j in range(len(data)-1, -1, -1):
        if data[j][0] <= i:
           if tmp < data[j][1]:
               tmp = data[j][1]
               tmpidx = j
    if tmpidx != -1:
        ans += tmp
        del data[tmpidx]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
ab=np.array(ab)
cand=[]
ans=0
for i in range(1,m+1):
  t=ab[ab[:,0]==i][:,1].tolist()
  for j in range(len(t)):
    heapq.heappush(cand,-t[j])
  if len(cand)==0:
    continue
  ans-=heapq.heappop(cand)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q

    def length(self):
        return len(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N, M = Scanner.map_int()
    X = Scanner.int_list_list(N)
    X.sort()
    ans = 0
    tasks = PriorityQueue()
    for t in reversed(range(M)):
        while X != [] and X[0][0] + t <= M:
            tasks.push(-X[0][1])
            X = X[1:]
        if tasks.length() > 0:
            ans += -tasks.pop()
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    a[i][1]*=-1
hq.heapify(a)
k=1
ans=0
q=0
while a and k<=m:
    p=hq.heappop(a)
    if p[0]>k:
        hq.heappush(a,p)
        k+=1
    elif p[0]==k:
        ans-=p[1]
        k+=1
    elif p[0]<k:
        p[0]=k
        hq.heappush(a,p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = map(int,input().split())
    AB.append((-b,a))
heapify(AB)
ans = 0
for i in range(1,M+1):
    rem = []
    while True:
        if AB:
            ab = heappop(AB)
            if ab[1] <= i:
                ans -= ab[0]
                for j in rem:
                    heappush(AB,j)
                break
            else:
                rem.append(ab)
        else:
            for j in rem:
                heappush(AB,j)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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())
b,a = zip(*sorted(zip(b,a)))
bit_booked = [False]*(m+1)
last_max = m
ans = 0
for i in range(n):
    if a[n-1-i] > last_max:pass
    else:
        day = a[n-1-i]
        exit_bit = False
        while bit_booked[day]:
            day += 1
            if day > last_max:
                exit_bit = True
                break
        if not exit_bit:
            bit_booked[day] = True
            ans+= b[n-1-i]
        if a[n-1-i] == last_max:
            while True:
                last_max -= 1
                if bit_booked[last_max] == False:
                    break
#print(bit_booked)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

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

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


# print(A)
ans = 0
Q = []
hq.heapify(Q)

for i in range(1, M + 1):
    for j in (A):
        if j[1] * (-1) <= i:
            hq.heappush(Q, j)
            A.remove([j[0], j[1]])
            # print(Q)
    if Q:
        ans += hq.heappop(Q)[0] * (-1)


print(ans)

Submission status: Time Limit Exceeded

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

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


A.sort(reverse=True, key=lambda x: x[1])
# print(A)
ans = 0

for i in range(1, M + 1):
    for j in (A):
        if j[0] <= i:
            ans += j[1]
            A.remove([j[0], j[1]])
            # print(i, A)
            break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M=map(int,input().split())
    job=[[0,0] for i in range(0,N)]
    for i in range(0,N):
        job[i][0],job[i][1]=map(int,input().split())
    s=0
    job=sorted(job,reverse=True)
    for i in range(0,M):
        for j in range(0,N):
            if job[j][0]>M-i:
                job[j][1]=0
        jobsub=[job[k][1] for k in range(0,N)]
        s+=max(jobsub)
        job[jobsub.index(max(jobsub))][1]=0

    print(s)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# O(NM), absolutely TLE
n, m = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))

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

ans = 0
for i in range(1, m+1):
    if len(ab)==0:
        break
    for j in range(len(ab)):
        if ab[j][0]<=i:
            _, tmp = ab.pop(j)
            ans += tmp
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((b, a-1))
l.sort()
l = l[::-1]
schedule = [0 for i in range(m)]
for b, a in l:
    if a >= m:
        continue
    while schedule[a] != 0:
        a += 1
        if a >= m:
            break
    if a >= m:
        continue
    schedule[a] = b

print(sum(schedule))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b  = map(int, input().split())
    if a <= m:
        AB.append((a, b))
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = b
        counts[a - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
used = [False] * m
total = 0
score = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if used[i]:
            continue
        used[i] = True
        counts[a - 1] += 1
        total += 1
        score += b
        break
    if total == m:
        break
print(score)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for j in range(n):
    if AB[j][0] > m:
        continue
    for i in range(AB[j][0] - 1 + counts[AB[j][0] - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = AB[j][1]
        counts[AB[j][0] - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = b
        counts[a - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a <= m:
        for i in range(a - 1 + counts[a - 1], m):
            if cands[i] > 0:
                continue
            cands[i] = b
            counts[a - 1] += 1
            total += 1
            break
    if total == m:
        break
print(sum(cands))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A].append(-B)
# print(dic, sorted(dic.keys()))

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        heap.extend(dic[i + 1])
    heapq.heapify(heap)
    # print(heap)
    if heap:
        ans = ans - heapq.heappop(heap)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A] += [-B]

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        heap += dic[i + 1]
    heapq.heapify(heap)
    # print(heap)
    if heap:
        ans += -heapq.heappop(heap)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.sort()
salary = 0
salaries = [0]
num = 0
for i in range(m):
    if num < n:
        while ab[num][0] <= i + 1:
            salaries.append(ab[num][1])
            num += 1
            if num == n:
                break
    temp = max(salaries)
    salary += temp
    if temp > 0:
        salaries.remove(temp)
print(salary)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(-b)
    except:
        pass
ans = 0
a = []
for i in range(M):
    a += w[i]
    heapq.heapify(a)
    try:
        ans += -heapq.heappop(a)
    except:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(b)
    except:
        pass
for x in w:
    x.sort()
ans = 0
for i in range(M):
    if i>=1:
        w[i] += w[i-1][:-1]
        w[i].sort()
    try:
        ans += w[i][-1]
    except:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(b)
    except:
        pass
w.reverse()
a= [[] for i in range(M)]
ans = 0
for i in range(M):
    a[i] = w[M-i-1]
    if i>=1:
        a[i-1].sort()
        a[i] += a[i-1][:-1]
    try:
        ans += max(a[i])
    except:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) #list(range(m+1))
	for a,b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		#pa((a,b,m-a,nwdl))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) #list(range(m+1))
	for a,b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		#pa((a,b,m-a,nwdl))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            candidates.append(b)
        else:
            s = j
            break
    if len(candidates) > 0:
        max_v = max(candidates)
        candidates.pop(candidates.index(max_v))
        ans += max_v

print(ans)