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: Accepted

Solution code:
import heapq

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

AB = sorted(AB, key=lambda x: x[0])
hq = []
ind = 0
ans = 0
for lim in range(1, M + 1):
    for i in range(ind, N):
        if AB[i][0] == lim:
            AB[i][0], AB[i][1] = -AB[i][1], AB[i][0]
            heapq.heappush(hq, AB[i])
            ind += 1
        else:
            break
    if hq:
        ans += -heapq.heappop(hq)[0]

print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys

finput = sys.stdin.readline

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

q = [[] for i in range(m)]

for i in range(n):
    a,b = [int(j) for j in finput().split()]
    if a>m:
        continue
    q[a-1].append(-b)

hq = []
heapq.heapify(hq)
ans = 0
for i in range(m):
    if len(hq)==0 and len(q[i])==0:
        continue
    for j in range(len(q[i])):
        heapq.heappush(hq, q[i][j])
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Accepted

Solution code:
import heapq
import numpy as np 

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

ab_list = []
for _ in range(N):
    a,b = map(int,input().split())
    ab_list.append([a,b])
ab_list = np.array(ab_list)
ab_list = ab_list[np.argsort(ab_list[:,0])]

ans = 0
h = []
# heapq.heapify(h)
flag = 0
for i in range(1,M+1):
    while flag<N:
        a = ab_list[flag][0]
        if a >i:
            break
        else: # 終了日までに報酬がももらえる
            b = ab_list[flag][1]
            heapq.heappush(h,-1 * b)
            flag+=1
    if len(h) > 0:
        ans += -1 * heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
X=[[] for _ in range(10**5+5)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[0]*m
heapq.heapify(p)
for i in range(m):
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
X=[[] for _ in range(10**5+5)]
for i in range(n):
    a,b=map(int,input().split())
    X[a-1].append(-b)

ans=0
p=[]
heapq.heapify(p)
for i in range(m):
    if len(p)==0 and len(X[i])==0:
        continue
    for j in range(len(X[i])):
        heapq.heappush(p,X[i][j])
    a=heapq.heappop(p)
    ans+=a*-1
print(ans)

Submission status: Accepted

Solution code:
import heapq # 優先度付きキュー(最小値取り出し)
n,m = map(int, input().split())
a = [list(map(int,input().split())) for i in range(n)]
a.sort(reverse = True)
b = []
heapq.heapify(b)   # ヒープ化
ans = 0

for i in range(1,m+1):
    while a and a[-1][0] == i:
        val = a.pop()[1]
        heapq.heappush(b, (-1)*(val))           # 今考えてる日にちの価値をpush
    if b:
        val = heapq.heappop(b)*(-1)             # 最大値の取り出し
        ans += val
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
lst = [0 for _ in range(m)]
dic = {}
for i in range(n):
    a,b = map(int,input().split())
    if a in dic:
        dic[a].append(-b)
    else:
        dic[a] = [-b]
q = []
heapq.heapify(q)
ans = 0
for i in range(1,m+1):
    if i in dic:
        for j in range(len(dic[i])):
            heapq.heappush(q,dic[i][j])
    if q:
        ans -= heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort()

i = 0
works = []
reward = 0
for d in range(m):
  while i < n and jobs[i][0] <= d + 1:
    heapq.heappush(works, -jobs[i][1])
    i += 1
  if works:
    reward -= heapq.heappop(works)
print(reward)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append([a,b])
AB.sort(key=lambda x:x[0])
import heapq
h=[]
day=1
count=0
ans=0
while True:
    if day>M:
        break
    while count!=N:
        if AB[count][0]!=day:
            break
        heapq.heappush(h,-AB[count][1])
        count+=1
    if len(h)!=0:
        ans-=heapq.heappop(h)
    day+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import *

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

dic = defaultdict(list)
for i in range(N):
    a, b = MAP()
    dic[a].append((-1) * b)

ans = 0
incre = []

# M日後から1 ~ M日前
for i in range(1, M+1):
    for j in dic[i]:
        heappush(incre, j)
    if incre:# is exist 
        ans += -heappop(incre)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

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

heap = []
ans = 0

j = -1
for i in range(M)[::-1]:
    while j < N-1 and job[j+1][0]+i <= M:
        j += 1
        heappush(heap,-job[j][1])
    if heap:
        ans += -heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
# イベントソートでもできると思う

import heapq

N, M = map(int, input().split())
event_list = [[m, 10**5] for m in range(1, M+1)]
for i in range(N):
  a, b = map(int, input().split())
  event_list.append([a, b])


event_list.sort()
jobs = []
ans = 0
for event in event_list:
  if event[1] < 10**5:
    heapq.heappush(jobs, -event[1])
  else:
    if jobs:
      ans -= heapq.heappop(jobs)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from heapq import heapify,heappop,heappush

    n,m=map(int,input().split())
    W=[list(map(int,input().split())) for _ in range(n)]
    W.sort(key=lambda x:x[0])
    
    q=[]
    heapify(q)
    j,income=0,0
    for i in range(1,m+1):
        while j<n and W[j][0]<=i:
            heappush(q,-W[j][1])
            j+=1

        if q:
            t=heappop(q)
            income+=-t
    print(income) 

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
A=[[0]*2for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
A=sorted(A)
ans=0
s=[]
j=0
for i in range(m+1):
  while j<n:
    if A[j][0]>i:
      break
    heapq.heappush(s,A[j][1]*(-1))
    j=j+1
  if len(s)==0:
    continue
  ans=ans-heapq.heappop(s)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
jobs = {}
for _ in range(n):
  a,b = map(int,input().split())
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]

import heapq
cand = []
heapq.heapify(cand)

ans = 0
for i in range(1,m+1):
  if i in jobs:
    for j in jobs[i]:
      heapq.heappush(cand,-j)
  if cand:
    ans += -heapq.heappop(cand)
print(ans)

Submission status: Accepted

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)
day = M - 1
ans = 0
ables = []
while day >= 0:
    now = M - day
    if now in d.keys():
        for v in d[now]:
            heappush(ables, v)
    if len(ables) > 0:
        v = heappop(ables)
        ans += -1 * v
    day -= 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    N, M = LI()
    jobsavailable = [[] for _ in range(10**5+1)]
    for _ in range(N):
        a, b = LI()
        if a > M:
            continue
        jobsavailable[M-a].append(b)
    cur_jobs = []
    cnt = 0
    for i in range(1, M+1):
        jobs = jobsavailable[M-i]
        for j in jobs:
            heapq.heappush(cur_jobs, -j)
        if cur_jobs != []:
            j = -heapq.heappop(cur_jobs)
            cnt += j
    print(cnt)

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

def main():
    N, M = LI()
    jobsavailable = [[] for _ in range(10**5+1)]
    for _ in range(N):
        a, b = LI()
        if a > M:
            continue
        jobsavailable[M-a].append(b)
    cur_jobs = []
    cnt = 0
    for i in range(1, M+1):
        # a <= iのなかで最大のbがあるものをとりだす
        jobs = jobsavailable[M-i]
        for j in jobs:
            _heappush_max(cur_jobs, j)
        if cur_jobs != []:
            j = _heappop_max(cur_jobs)
            cnt += j
    print(cnt)

main()

Submission status: Accepted

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=[]
heapq.heapify(tmp)
ans=0
for i in range(m):
  for j in l[i]:
    heapq.heappush(tmp,j)
  if len(tmp)>0:
    ans+= heapq.heappop(tmp)
print(-ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
import heapq
c=[[] for _ in range(m+1)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
        c[a].append(-b)
  
q=[]
ans=0
for i in range(1,m+1):
  for j in c[i]:
    heapq.heappush(q,j)
  if q:
    ans-=heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
works = dict()
for _ in range(N):
  a, b = map(int, input().split())
  if a in works.keys():
    works[a].append(-1 * b)
  else:
    works[a] = [-1 * b]
#print(works)

import heapq
cando = []
total = 0
day = M - 1
while day >= 0:
  lt = M - day

  if lt in works.keys():
    for salary in works[lt]:
      heapq.heappush(cando, salary)

  #print('day:{}, lt:{}, len(cando):{}'.format(day, lt, len(cando)))

  if len(cando) > 0:
    total += -1 * heapq.heappop(cando)

  #print('day:{}, total:{}'.format(day, total))

  day -= 1

print(total)

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heapify, heappop, heappush
from bisect import bisect_right

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

salary = 0
hq = []
j = 0
for i in range(1, M+1):
    while j < N and AB[j][0] == i:
        heappush(hq, -AB[j][1])
        j += 1
    if hq:
        salary -= heappop(hq)
print(salary)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
ab = [inpl() for i in range(n)]
hq = []
res = 0
ind = 0
ab.sort()
for i in range(1,m+1):
    while True:
        if ind >= n: break
        a,b = ab[ind]
        if a <= i:
            heappush(hq,[-b,a])
            ind += 1
        else: break
    if hq == []: continue
    tmp = heappop(hq)
    res -= tmp[0]
    # print(tmp,res)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(reverse=True)
hq = []
ans = 0
for i in range(1,M+1):
  while ls:
    if ls[-1][0]-i==0:
      heappush(hq,-ls[-1][1])
      ls.pop()
    else:
      break
  if hq==[]:
    continue
  ans -= heappop(hq)
print(ans)

Submission status: Accepted

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)
# heapq.heapify(data_list)

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

print(-ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

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

dp = [0] * (M + max(a for a, b in AB))

AB.sort(key=lambda x:x[0])
q = []
heapq.heapify(q)
i = 0
ans = 0
for day in range(1, M+1):
  while i < len(AB) and AB[i][0] <= day:
    heapq.heappush(q, -1*AB[i][1])
    i += 1
  if q:
    ans += -1 * heapq.heappop(q)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    res = [0] * m
    hq = []
    i = 0
    for j in range(1, m+1):
        while i < n:
            a, b = ab[i]
            if a <= j:
                heappush(hq, -b)
                i += 1
            else:
                break
        if not hq:
            continue
        res[-j] = -heappop(hq)
    
    return sum(res)
        
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import heapq
N , M =map(int,input().split())
L = [[] for _ in range(M + 1)]

for i in range(N):
  a,b = map(int,input().split())
  if a <= M:
    L[M - a].append(-b)

work = []
heapq.heapify(work)
ans = 0

for i in range(M,-1,-1):
  for j in range(len(L[i])):
    heapq.heappush(work,L[i][j])
  if len(work) > 0:
    ans -= heapq.heappop(work)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
ab=[[] for _ in range(m+1)]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    ab[a].append(-b)

cand=[]
heapq.heapify(cand)
ans=0
for i in range(1,m+1):
  for j in range(len(ab[i])):
    heapq.heappush(cand,ab[i][j])
  if len(cand)>0:
    ans-=heapq.heappop(cand)

print(ans)

Submission status: Accepted

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()
    i = 0
    for t in reversed(range(M)):
        while i < N and X[i][0] + t <= M:
            tasks.push(-X[i][1])
            i += 1
        if tasks.length() > 0:
            ans += -tasks.pop()
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n,m= map(int, input().split())
ab_list=[]
for _ in range(n):
    a, b = map(int, input().split())
    ab_list.append([a,b])
ab_list.sort()

import heapq
l = []
heapq.heapify(l)

ind=0
ans=0
for i in range(1,m+1):
    while n>ind and ab_list[ind][0] <= i:
        heapq.heappush(l,-ab_list[ind][1])
        ind+=1

    if len(l) !=0:
        b = -heapq.heappop(l)
        ans+=b
print(ans)

Submission status: Accepted

Solution code:
n,m= map(int, input().split())
ab_list=[]
for _ in range(n):
    a, b = map(int, input().split())
    ab_list.append([a,b])
ab_list.sort()

import heapq
l = []
heapq.heapify(l)

ind=0
ans=0
for i in range(1,m+1):
    while n>ind and ab_list[ind][0] <= i:
        heapq.heappush(l,-ab_list[ind][1])
        ind+=1

    if len(l) !=0:
        b = -heapq.heappop(l)
        ans+=b
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
AB=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    b*=-1
    AB[i]=[a,b]

AB.sort()
h=[]
heapq.heapify(h)
count=0
i=0
for day in range(AB[0][0],M+1):
    while i<N-1:
        if AB[i][0]==day:
            heapq.heappush(h,AB[i][1])
            i+=1
        elif AB[i][0]!=day:
            if len(h)!=0:
                count+=-heapq.heappop(h)
            break
    if i==N-1:
        if AB[i][0]==day:
            heapq.heappush(h,AB[i][1])
            count+=-heapq.heappop(h)
        elif AB[i][0]!=day:
            if len(h)!=0:
                count+=-heapq.heappop(h)
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
N,M = map(int,input().split())
AB = [[] for i in range(M+1)]
for i in range(N):
    a,b = map(int,input().split())
    if a <= M:
        AB[a].append(-b)
AB2 = []
work = 0
heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heappush(AB2,j)
    if len(AB2):
        b = heappop(AB2)
        work -= b
print(work)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
heapq.heapify(l)
a=[]
heapq.heapify(a)
fd=heapq.heappop(l)
heapq.heappush(a,-fd[1])
ans=0
for day in range(fd[0],m+1):
    while l:
        temp=heapq.heappop(l)
        if temp[0]>day:
            heapq.heappush(l,temp)
            break
        else:
            heapq.heappush(a,-temp[1])
    if a:
        ans+=heapq.heappop(a)
print(-ans)

Submission status: Accepted

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

import heapq
h = []
ans = 0
L.sort()
m = 1
i = 0
while i < N and L[i][0] <= M:
    if L[i][0] == m:
        heapq.heappush(h, -L[i][1])
        i += 1
    else:
        m += 1
        if h:
            ans -= heapq.heappop(h)
while m <= M and h:
    ans -= heapq.heappop(h)
    m += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((u, v))
a.sort(key = lambda x: -x[0])
h = []
res = 0
#print(a)
for i in range(M + 1):
  while len(a):
    if a[-1][0] > i: break
    heapq.heappush(h, -a.pop()[1])
  if len(h):
    res += heapq.heappop(h)
print(-res)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int,input().split())
J = [[] for k in range(M+1)]
for k in range(N):
    A, B = map(int,input().split())
    if A <= M:
        J[A].append(B)

Q = []
ans = 0
for d in range(1,M+1):
    for e in J[d]:
        heapq.heappush(Q,-e)
    if len(Q) > 0:
        ans += -heapq.heappop(Q)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    from collections import defaultdict
    dic = defaultdict(list)
    for a, b in AB:
        dic[a].append(-b)
    AB.sort()
    from heapq import heapify, heappop, heappush
    h = dic[1][:]
    heapify(h)
    ans = 0
    for d in range(1, M+1):
        # Aiがd以下のうち、Bi最大の仕事を受ける
        if d != 1:
            for v in dic[d][:]:
                heappush(h, v)
        if h:
            ans += -heappop(h)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    N,M=MI()
    AB=LLIN(N)
    AB.sort(reverse=True)

    ans = 0
    pri_work = []
    for date in range(1,M+1):
        while AB and AB[-1][0]<=date:
            heappush(pri_work, -AB.pop()[1])
        if pri_work:    
            ans += -heappop(pri_work)
    print(ans)
            


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
work = []
# 最終日からさかのぼっていって、できるバイトの中で一番収入が多いやつをする
for i in range(1, M + 1):
    while AB:
        if AB[-1][0] <= i:
            _, b = AB.pop()
            heapq.heappush(work, -b)
        else:
            break

    if work:
        ans -= heapq.heappop(work)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d = defaultdict(lambda: [])
for a,b in AB:
    d[a].append(b)

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

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

q = Heapq([], True)

ans = 0
for m in range(1,M+1):
    for a in d[m]:
        q.push(a)
    if q.size():
        ans += q.pop()
print(ans)

Submission status: Accepted

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([a, b * (-1)])

A.sort()
# print(A)

ans = 0
j = 0
Q = []
hq.heapify(Q)

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


print(ans)

Submission status: Accepted

Solution code:
# ABC137 D - Summer Vacation
import heapq as hp
n,m=map(int,input().split())
AB=[[] for i in range(m+1)]
l=[]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        AB[a].append(-b)
ans=0
hp.heapify(l)
for ab in AB:
    for x in ab:
        hp.heappush(l,x)
    if len(l)>0:
        ans-=hp.heappop(l)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

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

N, M = lr()
works = [[] for _ in range(M+1)]
# M-1日後から選んでいく,
for _ in range(N):
    a, b = lr()
    if a <= M:
        works[a].append(-b)

heap = []
answer = 0
for work in works:
    for x in work:
        heappush(heap, x)
    if heap:
        answer -= heappop(heap) # heap構造なので

print(answer)
# 08

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

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

N, M = lr()
works = [[] for _ in range(M+1)]
# M-1日後から選んでいく,
for _ in range(N):
    a, b = lr()
    if a <= M:
        works[a].append(-b)

heap = []
answer = 0
for i in range(1, M+1):
    for x in works[i]:
        heappush(heap, x)
    if heap:
        answer -= heappop(heap) # heap構造なので

print(answer)
# 08

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

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

N, M = lr()
works = [[] for _ in range(M+1)]
# M-1日後から選んでいく,
for _ in range(N):
    a, b = lr()
    if a > M:
        continue
    works[a].append(-b)

heap = []
answer = 0
for i in range(1, M+1):
    for x in works[i]:
        heappush(heap, x)
    if len(heap) == 0:
        continue
    answer += heappop(heap)

answer *= -1
print(answer)
# 08