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 sys
import heapq
 
N, M = list(map(int, input().split()))
jobs = []

#上限内で報酬を得られる単発を一度リストに入れる。
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue
    jobs.append((A, B))

#逆順にsort
jobs.sort(reverse=True)

#heatpqでpriority quene，最大値を取り出すときは-qを加えて挿入し，-1をかけて取り出す
q = []
ans = 0
#後ろの日にちから回す
for i in range(1, M + 1):
    #日数が足りる単発をheatpqのリストに加えていく
    while jobs and jobs[-1][0] <= i:
        A, B = jobs.pop()
        heapq.heappush(q, -B)
 
    if q:
        #できる仕事がある場合，最大の給料のを取り出す
        ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
dic = {}
for i in range(N):
  A,B = map(int,input().split())
  if A <= M:
    if A in dic.keys():
      dic[A].append(B)
    else:
      dic[A] = [B]
      
ans = 0
plan = []
for i in range(1,M+1):
  if i in dic.keys():
    for w in dic[i]:
        heapq.heappush(plan,-w)
  if len(plan) != 0:
    ans += heapq.heappop(plan)

print(-ans)

Submission status: Accepted

Solution code:
import heapq

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

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

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

abl = []
for i in range(n):
    abl.append(tuple(map(int, input().split())))
abl.sort()

q = []
count = 0
ans = 0

for i in range(1, m+1):
    while count < n:
        a, b = abl[count]
        if a > i:
            break
        heappush(q, -b)
        count += 1
    if q:
        ans += -heappop(q)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    X = [None] * N
    for i in range(N):
        A, B = map(int, input().split())
        X[i] = (A, B)
    X.sort()
    idx = 0
    day = 1
    ans = 0
    h = []
    while day <= M:
        while idx < N and X[idx][0] <= day:
            heappush(h, -X[idx][1])
            idx += 1
        if len(h):
            ans += -heappop(h)
        day += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = {}
q = []
ans = 0

for i in range(N):
    A, B = map(int, input().split())
    
    if A in AB:
        AB[A].append(-B)
    else:
        AB[A] = [-B]

for i in range(1, M+1):
    if i in AB:
        for B in AB[i]:
            heapq.heappush(q, B)
        
    if len(q):
        ans -= heapq.heappop(q)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M =map(int, input().split())
A = [[] for i in range(10**5+1)]
 
for i in range(N):
    a, b = map(int,input().split())
    if a > M:
        continue
    A[a].append(-b)
 
work_cand = []
sum = 0
 
for i in range(M+1):
    add_jobs = A[i]
    if len(add_jobs) != 0:
        for j in add_jobs:
            heapq.heappush(work_cand, j)
    if len(work_cand) == 0:
        continue
    sum += heapq.heappop(work_cand)
ans = -(sum)
print(ans)

Submission status: Accepted

Solution code:
class Node:
    
    def __init__(self, i):
        self.end = i + 1
        self.days = {i}


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

ans = 0
schedule = {}
BA.sort(reverse=True)
for b, a in BA:
    x = a
    if a in schedule:
        x = schedule[a].end
    if x > M:
        continue
    ans += b
    if x - 1 in schedule:
        w1 = schedule[x - 1]
        if x + 1 in schedule:
            w2 = schedule[x + 1]
            if len(w1.days) < len(w2.days):
                w1, w2 = w2, w1
            else:
                w1.end = w2.end
            w1.days |= w2.days
            for i in w2.days:
                schedule[i] = w1
            schedule[x] = w1
            w1.days.add(x)
        else:
            schedule[x] = w1
            w1.end += 1
            w1.days.add(x)
    elif x + 1 in schedule:
        w2 = schedule[x + 1]
        schedule[x] = w2
        w2.days.add(x)
    else:
        schedule[x] = Node(x)
print(ans)

Submission status: Accepted

Solution code:
class Node:
    
    def __init__(self, i):
        self.end = i + 1
        self.days = {i}


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

ans = 0
schedule = {}


def concat(node1, node2, x):
    if len(node1.days) < len(node2.days):
        node1, node2 = node2, node1
    else:
        node1.end = node2.end
    node1.days |= node2.days
    for i in node2.days:
        schedule[i] = node1
    schedule[x] = node1
    node1.days.add(x)

BA.sort(reverse=True)
for b, a in BA:
    x = a
    if a in schedule:
        x = schedule[a].end
    if x > M:
        continue
    ans += b
    if x - 1 in schedule:
        w1 = schedule[x - 1]
        if x + 1 in schedule:
            w2 = schedule[x + 1]
            concat(w1, w2, x)
        else:
            schedule[x] = w1
            w1.end += 1
            w1.days.add(x)
    elif x + 1 in schedule:
        w2 = schedule[x + 1]
        schedule[x] = w2
        w2.days.add(x)
    else:
        schedule[x] = Node(x)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(AB, (a, b))

# print(N, M, AB)

ans = 0
work = []
for i in range(M):
    remain = i + 1
    # print('remain={}, AB={}, ans={}'.format(remain, AB, ans))
    while len(AB) > 0:
        ab = heapq.heappop(AB)
        if ab[0] > remain:
            heapq.heappush(AB, ab)
            break
        heapq.heappush(work, (-ab[1], ab[0]))
    if len(work) == 0:
        continue
    v = heapq.heappop(work)
    ans -= v[0]
    # print('work={}'.format(work))
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(N)]
l.sort(reverse=True)

h=[]
ans=0
for i in range(1,M+1):
    while l and l[-1][0]==i:
        heapq.heappush(h,l.pop()[1]*(-1))
    if h:
        ans-=heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq
#N = int(input())
N, M = list(map(int,input().split()))
jobs = [[] for _ in range(M)]
#AB = [list(map(int,input().split())) for _ in range(N)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)

#print(jobs)
ans = 0
heap = []

for i in range(M) :
    #print(jobs[:i])

    for hou in jobs[i] :
        heapq.heappush(heap, hou)
    if len(heap) > 0 :
        thou = heapq.heappop(heap)
        ans += -thou

print(ans)

# print(AB)
# AB = sorted(AB, key = lambda x : x[1], reverse=True)
# AB = sorted(AB, key = lambda x : x[0])
# print(AB)
# hou = 0
# nokori = M
#
# for i in range(N)  :
#     ab = AB[i]
#     if ab[0] <= nokori :
#         hou += ab[1]
#         nokori -= 1
# print(hou)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
lst = []
for _ in range(N):
    A, B = map(int, input().split())
    lst.append([A, -B])
lst.sort()

ans = 0
index = 0
hq = []
for i in range(M):
    while index < N and lst[index][0] <= i + 1:
        heapq.heappush(hq, lst[index][1])
        index += 1
    #heaqpはソートではないから順番は降順にはならないこともあるが最小値は先頭に来る
    if len(hq) > 0:
        ans -= heapq.heappop(hq)
    # print ('ans, i', ans, i)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int, input().split())
jobs=[[] for i in range(m)]
for i in range(n):
    a,b=map(int, input().split())
    if a > m:
        continue
    jobs[m-a].append(b)
q=[]
ans=0
for i in range(m,0,-1):
    for job in jobs[i-1]:
        heapq.heappush(q, -job)
    if len(q) > 0:
        ans += (-heapq.heappop(q))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
import heapq


N, M = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
AB.sort(key=lambda x: (x[0], -x[1]))
work = [deque([]) for _ in range(M + 1)]

for ab in AB:
    if ab[0] <= M:
        work[ab[0]].append(ab[1])

ans = 0
day = 1
available_work = []
while day <= M:
    for w in work[day]:
        heapq.heappush(available_work, -w)
    if len(available_work) > 0:
        ans += heapq.heappop(available_work)
    day += 1

print(-ans)

Submission status: Accepted

Solution code:
import bisect
N,M = map(int,input().split())
A = []
for _ in range(N):
    a,b = map(int,input().split())
    if a<=M: A.append([a,b])
A.sort(reverse=True)
import heapq
h = []
ans = 0
for m in range(1,M+1):
    while A and A[-1][0] == m:
        heapq.heappush(h, A.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
hq = []
ab = []
for i in range(n):
    ab.append([int(_) for _ in input().split()])
ab.sort(key = lambda x:(x[0],-x[1]))
ab.append([m+1,-1])
now = 1
ans = 0
idx = 0
while now <= m:
    while ab[idx][0] <= now:
        heapq.heappush(hq,-ab[idx][1])
        idx += 1
    if hq != []:
        ans -= heapq.heappop(hq)
    now += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

q = []
ans = 0
for i in range(M-1, -1, -1):
    for b in jobs[i]:
        heapq.heappush(q, b*(-1))
    if len(q) > 0:
        ans += heapq.heappop(q)*(-1)

print(ans)

Submission status: Accepted

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

import heapq

n, m = map(int, input().split())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))
a.sort()
a.append([m+1, 0])

h = []
ptrA = 0
ans = 0
for i in range(m):
	while a[ptrA][0] <= i + 1:
		heapq.heappush(h, a[ptrA][1] * (-1))
		ptrA += 1
	if len(h) > 0:
		ans += heapq.heappop(h)
print(-ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
ab=[]
for _ in range(n):
    tmpa, tmpb=map(int, input().split())
    ab.append((tmpa,tmpb))
ab.sort(reverse=True)
import heapq
h = []
ans = 0
for i in range(1, m+1):
    while ab and ab[-1][0] == i:
        heapq.heappush(h,ab.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
jobs = {}
for job in AB:
    if job[0] in jobs:
        jobs[job[0]].append(job[1])
    else:
        jobs[job[0]] = [job[1]]

hq = []
reword_sum = 0
for i in range(1, M + 1):
    if i in jobs:
        for reword in jobs[i]:
            heapq.heappush(hq, -reword)

    if len(hq):
        reword_sum += heapq.heappop(hq)

print(-reword_sum)

Submission status: Accepted

Solution code:
import sys
import heapq

N, M = list(map(int, input().split()))
possiblyValidJobs = {}
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue

    if A in possiblyValidJobs:
        possiblyValidJobs[A].append(B)
    else:
        possiblyValidJobs[A] = [B]

validJobsOnThisDay = []
ans = 0
for daysBeforeDeadline in range(1, M + 1):
    if daysBeforeDeadline in possiblyValidJobs:
        for wage in possiblyValidJobs[daysBeforeDeadline]:
            heapq.heappush(validJobsOnThisDay, -wage)
    if validJobsOnThisDay:
        ans += -heapq.heappop(validJobsOnThisDay)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]
# 必要な日数の照準にソートする
jobs.sort()
# 次に選ぶバイト候補の保存場所
money = []
ans = 0

i = 0
# より制約の強い、最終リミットに近い日に行うバイトの割当てから攻めていく
for limit in range(1, m + 1):
    # limit日までに報酬のもらえるアルバイトを抽出
    while i < n and jobs[i][0] <= limit:
        a = jobs[i][0]
        b = jobs[i][1]
        # 次に選ぶバイト候補に追加
        heapq.heappush(money, -b)
        i += 1
    # 要素数が空の場合のエラー処理
    if money != []:
        ans -= heapq.heappop(money)

print(ans)