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: Runtime Error

Solution code:
job = list()
salary = list()
k = m
n,m = map(int,input().split())

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

job.sort(reverse = True)

for x in job:
    s,t = x
    salary.append(t)

    if s - k > 0:
        salary.remove(min(salary))
    else:
        k -= 1

print(sum(salary))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
work_list = [list(map(int, input().split())) for _ in range(n)]
work_cand = []
salary = 0
for j in range(1, m + 1):
    for i in range(n):
        if work_list[i][0] == j:
            work_cand.append(work_list[i])
            del work_list[i]
        else:
            pass
    if work_cand != []:
         work_cand.sort(key = lambda x: x[1], reverse = True)
         salary += work_cand[0][1]
         del work_cand[0]
    else:
        pass
print(salary)
            pass

Submission status: Runtime Error

Solution code:
import heapq


class Job:

    def __repr__(self):
        return f'{self.days},{self.reward}'

    def __lt__(self, other):
        return self.reward < other.reward

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days

N, M = list(map(int, input().split()))
h = []
jobs = []

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.append(Job(job_id=i, reward=B, days=A))


jobs = sorted(jobs, key=lambda j: j.days)
idx = 0
c = 0

for i in range(1, M+1):
    while idx < N and jobs[idx].days <= i:
        heapq.heappush(h, -jobs[idx].reward)
        idx += 1

    if len(h) != 0:
        c += -heapq.heappop(h)

print(c)

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate


class Job:

    def __repr__(self):
        return f'{self.reward},{self.days}'

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days


def dfs(memo, jobs, remaing_days):
    reward = 0

    key = str(jobs)

    if key in memo[remaing_days]:
        # print('return memo')
        return memo[remaing_days][key]

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(memo, remaining_jobs, remaing_days - 1)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    memo[remaing_days][key] = reward

    return reward


N, M = list(map(int, input().split()))
jobs = set()

memo = { day: {}  for day in range(M+1) }

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(job_id=i, reward=B, days=A))

print(dfs(memo, jobs, M))

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate


class Job:

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days):
    reward = 0

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


N, M = list(map(int, input().split()))
jobs = set()

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(job_id=i, reward=B, days=A))

print(dfs(jobs, M))

Submission status: Runtime Error

Solution code:
import bisect
import time
import heapq


# N: バイトの種類
# M: 日数の最大
N,M = map(int,input().split(" "))

# A 日数
# b バイト代
A = []
B = []
for _ in range(N):
    a,b = map(int,input().split(" "))
    A.append(a)
    B.append(-b)

# 日数でソート
ind_sorted = sorted(range(N), key = lambda x:A[x])
tmp_a = 0
tmp_b_ls = [0]
money = 0
tmp_ind = 0
for i in range(N):
    if A[ind_sorted[i]] > M:
        break
    if tmp_a != A[ind_sorted[i]]:
        # 空いている日数
        print(d)
        print(tmp_b_ls)
        d = A[ind_sorted[i]]-tmp_a
        for _ in range(d):
            if tmp_b_ls == []:
                break
            money -= heapq.heappop(tmp_b_ls)
        tmp_a = A[ind_sorted[i]]
    heapq.heappush(tmp_b_ls,B[ind_sorted[i]])

d = M+1-tmp_a
print(d)
print(tmp_b_ls)

for _ in range(d):
    if tmp_b_ls == []:
        break
    money -= heapq.heappop(tmp_b_ls)
print(money)

Submission status: Runtime Error

Solution code:
class Job:

    def __init__(self, reward, days):
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days, selected_jobs):
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


N, M = list(map(int, input().split()))
jobs = set()

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))

Submission status: Runtime Error

Solution code:
class Job:

    def __repr__(self):
        return f'Job(reward={self.reward}, days={self.days})'

    def __init__(self, reward, days):
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days, selected_jobs):
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


N, M = list(map(int, input().split()))
jobs = set()

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))

Submission status: Runtime Error

Solution code:
import math
from itertools import accumulate
from typing import List, Set


class Job:

    def __repr__(self):
        return f'Job(reward={self.reward}, days={self.days})'

    def __init__(self, reward: int, days: int):
        self.reward = reward
        self.days = days


def dfs(jobs: Set[Job], remaing_days: int, selected_jobs: Set[Job]) -> int:
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


N, M = list(map(int, input().split()))
jobs: Set[Job] = set()

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  index=0
  for j in range(1,i+1):
    if len(h[j])!=0 and max_<=h[j][-1]:
      max_=h[j][-1]
      index=j
  if index!=0 and len(h[index])!=0:
    h[index].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  index=0
  for j in range(1,i+1):
    if len(h[j])!=0 and max_<=h[j][-1]:
      max_=h[j][-1]
      index=j
  if index!=0:
    h[index].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  index=0
  for j in range(1,i+1):
    if len(h[j])!=0 and max_<=h[j][-1]:
      max_=h[j][-1]
      index=j
    if index!=0:
      h[index].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  index=0
  for j in range(1,i+1):
    if len(h[j])!=0 and max_<=li[j][-1]:
      max_=h[j][-1]
      index=j
    if index!=0:
      h[index].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  index=0
  for j in range(i+1):
    if len(h[j])!=0 and max_<=[j][-1]:
      max_=h[j][-1]
      index=j
    if index!=0:
      h[index].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
from heapq import *

n,m=map(int,input().split())
h=[[] for _ in range(10**5)]
result=0

for i in range(n):
  a,b=map(int,input().split())
  heappush(h[a], b)

for i in range(1,m+1):
  max_=0
  for j in range(i+1):
    if len(h[j])!=0 and max_<h[j][-1]:
      max_=h[j][-1]
      h[j].pop(-1)
  result+=max_
print(result)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
s=[[int(j) for j in input().split()] for i in range(n)]
ans=0
s.sort(reverse=True,key=lambda x:x[1])
for k in range(m):
    for i in range(n):
        if s[i][0]+k>m:
            print(s[i])
            s[i:i+1]=[]
            n=n-1
    if s==[]:
        break
    else:
        ans+=s[0][1]
        print(s[0])
        s[0:1]=[]
        n=n-1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = [input() for i in range(n)]
# print(n)
# print(s)
s = list(map(list, s))
# print(s)
for i in range(n):
    s[i].sort()
    s[i] = "".join(s[i])
# print(s)
dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic.setdefault(s[i],1)
a = list(dic.values())
# print(a)
import math
count = 0
for i in range(len(a)):
    if a[i] >= 2:
        count += math.factorial(a[i])//(math.factorial(a[i]-2)*2)
print(count)

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int, input().split(' '))
works = [[] for _ in range(100001)]

for i in range(n):
    a, b = map(int, input().split(' '))
    heapq[a].append(b)

ans = 0
h = []
for day in range(1, m + 1):
    for gain in works[day]:
        heapq.heappush(h, -gain)

    if h:
        gain = -heapq.heappop(h)
        ans += gain

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(b)
h = []
s=0
for i in range(1,m):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(m+1):
    a,b=map(int,input().split())
    ab[a].append(-1*b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-1*b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if h:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+2):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+2):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(m,-1,-1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
    
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_list = []
b_list = []

ans_list= []
for i in range(m):
    ans_list.append(0)

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

    if ans_list[b] < a:
        ans_list[b]




    a_list.append(a)
    b_list.append(b)



ans = 0
for i in range(m):
    i = i+1
    if min(a_list) <= i:
        # ind = a_list.index(max(b_list[list(map(lambda x : x < i+1,b_list))]))
        max_num = max( map(lambda y: y[0] * (y[1] <=i) ,zip(b_list,a_list)))
        # ind = a_list.index(max(b_list * list(map(lambda x : x <= i,a_list))))
        ind = b_list.index(max_num)
        ans = ans + b_list[ind]
        a_list[ind] = m + 1

print(ans)

# print( list(map(lambda x : x < 3,[1,2,3,4])))
# list(map(lambda x : x < i+1,b_list))

# print( [1,2,3,4] * [True,False,True,False])
# print(1 * False)

Submission status: Runtime Error

Solution code:
import sys
import heapq 
input = sys.stdin.readline
n,m = map(int,input().split())
alwork = [() for i in range(m+1)]
w = []
hpop = heapq.heappop
hpush = heapq.heappush
ans = 0

for i in range(n):
  a,b = map(int,input().split())
  alwork[a] += (-b,)

for i in range(1,m+1):
  for j in alwork[i]:
    hpush(w,j)
  if w:
    ans += hpop(w)
print(-ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
AB = []
for n in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
avalist=[i for i in range(N)]
AB.sort(key=lambda k:k[0])
def maxReward(avalist,date):
    #print(avalist)
    mreward = 0
    if avalist == None:
        return 0
    else:
        count=0
        for i,ava in enumerate(avalist):
            
            if date+AB[ava][0] <= M:
                count=1
                
                #print(f'{ava} in {avalist}')
                newavalist= avalist[:i]+avalist[i+1:]
                reward = AB[ava][1] + maxReward(newavalist, date+1)
                if mreward < reward:
                    mreward = reward
            else:#sortされているので、これ以降はすべてelseになる。よってbreakしてよい
                break
              #  print(f'reject {ava}')
        if count==0:#有効なバイトがない
            return 0
        else:
            return mreward
print(maxReward(avalist, 0))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = []
B = []
for n in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
avalist=[i for i in range(N)]
def maxReward(avalist,date):
    #print(avalist)
    mreward = 0
    if avalist == None:
        return 0
    else:
        count=0
        for i,ava in enumerate(avalist):
            
            if date+A[ava] <= M:
                count=1
                
                #print(f'{ava} in {avalist}')
                newavalist= avalist[:i]+avalist[i+1:]
                reward = B[ava] + maxReward(newavalist, date+1)
                if mreward < reward:
                    mreward = reward
           # else:
              #  print(f'reject {ava}')
        if count==0:#有効なバイトがない
            return 0
        else:
            return mreward
print(maxReward(avalist, 0))

Submission status: Runtime Error

Solution code:
import heapq
def main(n,m,c):
    cost_map = dict([(i, [])for i in range(1,n+1)])
    for a, b in c:
        if a <= m:
            cost_map[a].append(b)
        
    hp =[]
    ret = 0
    for i in range(1, m+1):
        costs = cost_map[i]
        [heapq.heappush(hp, -c) for c in costs]
        if(len(hp) > 0):
            c = heapq.heappop(hp)
            ret -= c
    return ret
if __name__ == "__main__":
    n,m = map(lambda x: int(x), input().strip().split())
    c = [ list(map(lambda x: int(x), input().strip().split())) for i in range(n)]
    print(main(n,m,c))

Submission status: Runtime Error

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

def my_sort(word):
    sorted_word_list = sorted(word)
    sorted_word = ""
    for letter in sorted_word_list:
        sorted_word += letter
    return sorted_word

n = int(input())
words = {}
for i in range(n):
    word = my_sort(input())
    if word in words.keys():
        words[word] += 1
    else:
        words[word] = 0

print(sum(words.values()))

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
l = [0]*n
for i in range(n):
  l[i] = list(map(int,input().split()))
l.sort()

L = [[] for i in range(m+1)]
for i in range(n):
  if l[i][0] <= m:
    L[l[i][0]].append(l[i][1])

a = []
ans = 0
for i in range(m):
  key = i+1
  for j in L[key]:
    heapq.heappush(a, -L[i][j])
  if a != []:
    heapq.heapify(a)
    ans += heapq.heappop(a)
print(-ans)

Submission status: Runtime Error

Solution code:
import heapq

N, M = map(int, input().split())
l = [0 for i in range(N)]

for i in range(N):
    A, B = map(int, input().split())
    l[i] = [A,-B]
l.sort()

tmp = []
ans = 0

for i in range(1, M + 1):
    while l[i][0] <= i:
        heapq.heappush(tmp, l[i])
    ans -= heapq.heappop(tmp)[1]
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        ab.append((a,b))
        
    ab = sorted(ab, key=lambda x:(x[0],-x[1]))
    pq = []
    heapify(pq)
    
    ans = 0
    for i in range(1,M+1):
        ind = []
        for j,val in enumerate(ab):
            a,b = val
            ind = -1
            if a > i:
                break
            if i == a:
                heappush(pq, -b)
                ind = j
                
        if len(pq) > 0:
            tmp = heappop(pq) * (-1)
            ans += tmp
            
        ab = ab[j:]
    
    print(ans)
    
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        ab.append((a,b))
        
    ab = sorted(ab, key=lambda x:(x[0],-x[1]))
    pq = []
    heapify(pq)
    
    ans = 0
    for i in range(1,M+1):
        ind = []
        for j,val in enumerate(ab):
            a,b = val
            if a > i:
                break
            if i == a:
                heappush(pq, -b)
                ind.append(j)
                
        if len(pq) > 0:
            tmp = heappop(pq) * (-1)
            ans += tmp
            
        for k in ind:
            ab.pop(k)
    
    print(ans)
    
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from heapq import *
n,m = map(int,input().split())
t = [[] for i in range(m+1)]
for i in range(n):
    a,b = map(int,input().split())
    t[a].append(b)

ans = 0
h = []
for i in range(1,m+1):
    #print(i,"日目")
    for j in t[i]:
        heappush(h, -j)
        #print("heappush",j)
    if h:
        a = -heappop(h)
        #print("heappop",a)
        ans += a
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

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

table = [list(map(int, input().split())) for k in range(n)]
table.sort()

ans = 0
pay = []

for day in range(1, m+1):
    for t in table:
        if t[0] <= day:
            heapq.heappush(pay, -t[1])
            choice = t
        else:
            break
    if pay:
        ans -= heapq.heappop(pay)
        table.remove(choice)

print(ans)

Submission status: Runtime Error

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

for i in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  jobs[m-a].append(b)

que = []#候補入れ
ans = 0
for i in range(m-1, -1, -1):
  for wage in jobs[i]:
    heapq.heappush(que, wage*-1)
  if len(que):
    ans += heapq.heappop(que)*-1
    
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
AB =[tuple(map(int,input().split())) for i in range(n)]
ans,memo=0,0
hq=[]
AB.sort(key=lambda tup:tup[0])
for day in range(m):
	for i in range(memo,n):
		if AB[i][0]<=(day+1):
			heapq.push(hq,AB[i][1])
			memo+=1
		else:
			break
	if len(hq):	
		ans += -heapq.heappop(hq)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
AB =[tuple(map(int,input().split())) for i in range(n)]
ans,memo=0,0
hq=[]
AB.sort(key=lambda tup:tup[0])
for day in range(m):
	for i in range(memo,n):
		if AB[i][0]<=(day+1):
			heapq.push(hq,AB[i][1])
			memo+=1
		else:
			break
	ans += -heapq.heappop(hq)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
j = []
for i in range(n):
    j1 = list(map(int,input().split()))
    j.append(j1)
j.sort(key=lambda x:x[1],reverse=True)
j.sort(key=lambda x:x[0])
day = 1
i = 0
q = []
ans = 0
count = 0
while day <= m and i < n:
    if day == j[i][0]:
        heapq.heappush(q,-(j[i][1]))
        ans = ans + heapq.heappop(q)*(-1)
        day = day + 1
        i = i + 1
    elif day > j[i][0]:
        heapq.heappush(q,-(j[i][1]))
        i = i + 1
        count = count + 1
    else:
        day = day + 1
        if count > 0:
            ans = ans + heapq.heappop(q)*(-1)
while day <= m and count > 0:
        ans = ans + heapq.heappop(q)*(-1)
        day = day + 1
        count = count - 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

N,M = map(int,input().split())
d = defaultdict(list)

for _ in range(N):
  a,b = map(int,input().split())
  d[a].append(b)
  
h = []
res = 0

for a in range(1,M + 1):
  for b in d[a]:
    heappush(h,-b)
  if h > 0:
    c = heappop(h)
    res -=c
    
print(res)

Submission status: Runtime Error

Solution code:
class Work:
    count=0
    def __init__(self,payday,money):
        Work.count+=1
        self.count=count
        self.payday=payday
        self.money=money
 #moneyが大きい方、同じなら早くもらえる方、それも同じなら最初に書いてある方が強い方
    def __ft__(self,other):
        if self.money>other.money:
            return True
        if self.money==other.money:
            if self.payday<other.payday:
                return True
            if self.payday==other.payday:
                if self.count<other.count:
                    return True
        return False

    def __gt__(self,other):
        if self.money<other.money:
            return True
        if self.money==other.money:
            if self.payday>other.payday:
                return True
            if self.payday==other.payday:
                if self.count>other.count:
                    return True
        return False

#バイトの数、いつまでに稼ぐのか 
n,limit=[int(i) for i in input().split()]

#バイトのリストを作り、クラスを入れる O(n)
baitolist=[]
for i in range(n):
    payday,money=[int(i) for i in input().split()]
    work=Work(payday,money)
    baitolist.append(work)

#日数でランク付け　O(n)
summoney=0    
rank=[[] for i in range(limit+1)]
for baito in baitolist:
    if baito.payday<=limit:
        rank[baito.payday].append(baito)

        
import heapq
accessible=[]
count=1


for i in range(limit):
    for baito in rank[count]:
        heapq.heappush(accessible,baito)
    if accessible!=[]:
        dowork=heapq.heappop(accessible)
        summoney+=dowork.money
    count+=1
    
    
print(summoney)

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int, input().split())
job = {}
for i in range(n):
    a,b = map(int, input().split())
    if a not in job.keys():
        job[a] = [(-b,a)]
    else:
        job[a].append((-b,a))

hq = []

max_income = 0
for i in range(1,m+1):
    if i in job.keys():
        for j in job[i]:
            heapq.heappush(hq,(j))
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Submission status: Runtime Error

Solution code:
from itertools import groupby

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

sorted_ABs = list(map(lambda x: list(x[1]), list(groupby(ABs, key=lambda v: v[0]))))
print(sorted_ABs)

reward = 0
cands = []
for i in range(M):
    cands.extend(sorted_ABs[i])
    if len(cands) > 0:
        best = max(cands, key=lambda v: v[1])
        reward += best[1]
        cands.remove(best)

print(reward)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def sol():
    n,m=map(int,input().split())
    d=[]
    ans=[0]*(m+1)
    t=0
    ans[0]=1
    y=m
    for i in range(n):
        a,b=map(int,input().split())
        d.append((b,a))
    d.sort(reverse=True)
    for bb,aa in d:
        if max(ans.index(0),aa)==y:
            ans[y]=1
            t+=bb
            y-=1
        else:
            for j in range(max(ans.index(0),aa),y+1):
                if ans[j]==0:
                    ans[j]=1
                    t+=bb
                    break

    print(t)

if __name__=="__main__":
    sol()