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 ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],-B[i]])
a.sort(key = lambda x:(x[0]))

from bisect import bisect_left, bisect_right
import heapq

ans = 0
p = 0
h = []

for i in range(1,M+1):
  while p<N and a[p][0]==i:
    heapq.heappush(h,a[p][1])
    p += 1
  if h:
    x = heapq.heappop(h)
    ans += -x

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
tasks = []
for _ in range(N):
    A, B = map(int, input().split())
    tasks.append([A, B])

tasks.sort()

q = []
p = 0
ans = 0
for i in range(1, M+1):
    while p < N and tasks[p][0] <= i:
        heappush(q, -tasks[p][1])
        p += 1
    if len(q) == 0:
        continue
    ans -= heappop(q)

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
import heapq
from collections import defaultdict
dic = defaultdict(list)
l = []
heapq.heapify(l)
for i in range(n):
    a,b=map(int,input().split())
    b = -b
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    for i in dic[i+1]:
        heapq.heappush(l,i)
    if len(l) ==0 : M = 0
    else:
        # print(l)
        M = heapq.heappop(l)
        s += -M
print(s)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in [0]*n]
l.sort(key=lambda x:x[0])
ans = 0
tmpl = []
i = 0
for d in range(1,m+1):
  while i<=n-1 and l[i][0] <= d:
    #tmpl.append(l[i][1])
    heappush(tmpl,-l[i][1])
    i += 1
  if len(tmpl) > 0:
    #maxindex = tmpl.index(max(tmpl))
    #ans += tmpl[maxindex]
    #del tmpl[maxindex]
    ans -= heappop(tmpl)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1): 
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
    N, M = map(int, input().split())

    # 日数別に仕事を管理
    works = [[] for _ in range(M)]

    for i in range(N):
        A, B = map(int, input().split())
        
        if A > M:
            continue
        
        deadline = M - A
        # heapqは最小値を返す仕組みしかないので、最大値を返すため-する
        works[deadline].append(-B)
    
    ans = 0
    heapque = []

    # i日目に始めることができる仕事で報酬の高いものを選ぶ
    for i in range(M - 1, -1, -1):
        for work in works[i]:
            # heapqに候補を追加
            heappush(heapque, work)
        
        if heapque:
            ans += heappop(heapque)
    
    print(-ans)


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

works = []

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

works.sort(reverse = True)

hq = []
ans = 0

for i in range(1, m+1):
    while works and works[-1][0] <= i:
        a, b = works.pop()
        heappush(hq, -b)
    if hq:
        b = -heappop(hq)
        ans += b

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

read = lambda: map(int, raw_input().strip().split())
n, m = read()
jobs = [read() for _ in xrange(n)]
jobs_by_time = defaultdict(list)
for (a, b) in jobs:
  jobs_by_time[a].append(b)

ans = 0
q = [] # heapq
for t in xrange(0, m):
  day = t+1
  for job in jobs_by_time[day]:
    heapq.heappush(q, -job)
  
  if q:
    val = -heapq.heappop(q)
    ans += val
print ans

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()
pq = []
res, i = 0, 0
for day in range(1, m + 1):
	while i < n and AB[i][0] <= day:
		heapq.heappush(pq, -AB[i][1])
		i += 1
	if pq:
		res += -heapq.heappop(pq)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):
    while (j < N) and (X[j][0] <= i):
        heapq.heappush(hq, -X[j][1])
        j += 1
    if len(hq):
        ans += -heapq.heappop(hq)

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):
    while (j < N) and (X[j][0] <= i):
        heapq.heappush(hq, -X[j][1])
        j += 1
    if len(hq):
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = (int(i) for i in input().split())
ab = []
for i in range(n):
  tmp = [int(i) for i in input().split()]
  ab.append(tmp)
ab.sort()
heap = []
cur = 0
ans = 0

for i in range(1, m+1):
  while  (cur < n) and (ab[cur][0] <= i):
    heapq.heappush(heap, -ab[cur][1])
    cur += 1
  if heap:
    ans += -heapq.heappop(heap)
print(ans)

Submission status: Accepted

Solution code:

from heapq import heappop,heappush
from collections import defaultdict
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab_sort = sorted(ab,key=lambda x:x[0])
h_queue = []
j = 0
ans = 0
for i in range(1,m+1):
    while (j < n) and (ab_sort[j][0] <= i):
        heappush(h_queue,-ab_sort[j][1])
        j += 1
    if len(h_queue) :
        ans -= heappop(h_queue)
print(ans)

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()
hq=[]
tmp=0
ans=0
for i in range(1,m+1):
  while tmp<n and AB[tmp][0]<=i:
      heapq.heappush(hq,-AB[tmp][1])
      tmp+=1
  if hq:
      ans-=heapq.heappop(hq)
print(ans)

Submission status: Accepted

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

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

ans = 0
h_queue =[]
for i in range(1,m+1):
    for j in data[i]:
        heappush(h_queue,-j)
    if len(h_queue) > 0:
        ans -= heappop(h_queue)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

ans = 0
res = []
for i in range(1, m+1):
    if i in byte:
        for b in byte[i]:
            heappush(res, b)
    if res:
        ans -= heappop(res)
print(ans)

Submission status: Accepted

Solution code:
import logging
import heapq

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


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

    A_B.sort()
    logging.info(A_B)


    heap_Q = []
    curr = 0
    total = 0
    for i in range(1, M + 1):
        while curr < N and  A_B[curr][0] <= i:
            heapq.heappush(heap_Q, A_B[curr][1] * (-1))
            curr += 1

        if heap_Q:
            total += (-1) * heapq.heappop(heap_Q)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n,m = map(int,input().split())
byte = {}
for i in range(n):
    a,b = map(int,input().split())
    if a > m:
        continue
    if a not in byte:
        byte[a] = []
    heappush(byte[a], -b)

ans = 0
res = []
for i in range(1, m+1):
    if i in byte:
        while byte[i]:
            heappush(res, heappop(byte[i]))
    if res:
        ans -= heappop(res)
print(ans)

Submission status: Accepted

Solution code:
def main():
    # ヒープキューをインポート
    from heapq import heappush, heappop
 
    n, m = map(int, input().split())
    jobs = [[] for _ in range(m)]  # 締め切り別に，報酬を管理
 
    # See:
    # https://www.youtube.com/watch?v=1Z6ofKN03_Y
    for i in range(n):
        ai, bi = map(int, input().split())
 
        # 報酬が振り込まれる日がM日よりも後になる場合は除外
        if ai > m:
            continue
 
        # i件目のアルバイトを遅くてもいつまでに始める必要があるかを計算
        # heappopは最小値を返す．biを-1倍することで，最大値が取り出せる
        deadline = m - ai
        jobs[deadline].append(-bi)
 
    ans = 0
    reward = []
 
    # M-1日に始める必要があるアルバイトのうち，最も報酬の高いものを選択
    # 以降，今日始める必要があるアルバイトまで，順番に調べる
    # ある時点で得られる報酬の大小に着目
    for i in range(m - 1, -1, -1):
        for job in jobs[i]:
            # ヒープキューに，報酬の候補を追加
            heappush(reward, job)
 
        # 条件を満たすもののうち，最大の報酬を選択
        if reward:
            ans += heappop(reward)
 
    # ヒープキューに追加するときに，-1倍した分を元に戻す
    print(-ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n,m = map(int,input().split())
byte = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in byte:
        byte[a] = []
    heappush(byte[a], [-b,a])

ans = 0
res = []
for i in range(1, m+1):
    if i in byte:
        heappush(res, heappop(byte[i]))
    if not res:
        continue
    b,a = heappop(res)
    ans -= b
    if byte[a]:
        heappush(res, heappop(byte[a]))
     
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
L=[[] for _ in range(m)]
for _ in range(n):
        a,b=map(int,input().split())
        if a<=m:
                L[a-1].append(-b)
h=[]
heapq.heapify(h)

ans=0
for i in range(m):
        for j in L[i]:
                heapq.heappush(h,j)
        if len(h)==0:
                continue
        ans+=heapq.heappop(h)*(-1)
print(ans)

Submission status: Accepted

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

N, M = [int(x) for x in stdin.readline().rstrip().split()]
data = defaultdict(list)

for _ in range(N):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    data[A].append(B)

ans = 0
h_queue = []

for i in range(1,M+1):
    for j in data[i]:
        heappush(h_queue,-j)
    if len(h_queue) > 0:
        ans -= heappop(h_queue)

print(ans)

Submission status: Accepted

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

    n, m = map(int, input().split())
    ab = [[] for _ in range(m+1)]

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

    q = []
    o = 0

    for i in range(m+1):
        for a in ab[i]:
            heappush(q, -a)
        if q:
            o += -heappop(q)
    
    print(o)


if __name__ == "__main__":
    f_d()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    mix_list = [[a, b] for a, b in zip(A, B)]
    mix_list = sorted(mix_list, key=lambda x:(x[0], x[1]))
    A, B = zip(*mix_list)

    heap = []
    heapq.heapify(heap)

    head = 0
    earned = 0
    for i in range(1, M+1):
        while (head < len(A)) and (A[head] <= i):
            heapq.heappush(heap, -B[head])
            head += 1
        if len(heap) == 0:
            pass
        else:
            accepted = -heapq.heappop(heap)
            earned += accepted
    print(earned)



def solve_dp(N: int, M: int, A: "List[int]", B: "List[int]"):
    """
    動的計画法による実装、解としては合っているが遅い
    """
    mix_list = [[a, b] for a, b in zip(A, B)]
    # mix_list = sorted(mix_list, key = lambda x: x[0])
    A = [a for a, b in mix_list]
    B = [b for a, b in mix_list]
    dp = [[0 for i in range(N)] for j in range(M)]
    for i in range(M):
        if A[0] <= (i + 1):
            dp[i][0] = B[0]
    for j in range(1, N):
        if A[j] <= 1:
            dp[0][j] = max(B[j], dp[i][j - 1])
    for i in range(1, M):
        for j in range(1, N):
            if A[j] <= (i + 1):
                dp[i][j] = max(B[j] + dp[i - 1][j - 1], dp[i][j - 1])
            else:
                dp[i][j] = dp[i][j - 1]
    print(dp[M - 1][N - 1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
n, m = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(n)]
jobs.sort()
cur = 0
ans = 0
q = []
for i in range(1, m+1):
	while cur < n and jobs[cur][0] <= i:
		heappush(q, -jobs[cur][1])
		cur += 1
	if q:
		ans += -heappop(q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
P = [[] for i in range(M+1)]
for i in range(N):
    a, b = map(int, input().split())
    if a <= M:
        P[a].append(b)
que = []
ans = 0
for i in range(M+1):
    for a in P[i]:
        heappush(que, -a)
    if que:
        ans += -heappop(que)
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)
sum_salary = 0
h=[]
for i in range(M-1, -1, -1):
  for b in jobs[i]:
    heapq.heappush(h,-b)
  if(len(h)!=0):
    a = -heapq.heappop(h)
    sum_salary += a
print(sum_salary)

Submission status: Accepted

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


def main():
    # ヒープキューをインポート
    from heapq import heappush, heappop

    n, m = map(int, input().split())
    jobs = [[] for _ in range(m)]  # 締め切り別に，報酬を管理

    # See:
    # https://www.youtube.com/watch?v=1Z6ofKN03_Y
    for i in range(n):
        ai, bi = map(int, input().split())

        # 報酬が振り込まれる日がM日よりも後になる場合は除外
        if ai > m:
            continue

        # i件目のアルバイトを遅くてもいつまでに始める必要があるかを計算
        # heappopは最小値を返す．biを-1倍することで，最大値が取り出せる
        deadline = m - ai
        jobs[deadline].append(-bi)

    ans = 0
    reward = []

    # M-1日に始める必要があるアルバイトのうち，最も報酬の高いものを選択
    # 以降，今日始める必要があるアルバイトまで，順番に調べる
    # ある時点で得られる報酬の大小に着目
    for i in range(m - 1, -1, -1):
        for job in jobs[i]:
            # ヒープキューに，報酬の候補を追加
            heappush(reward, job)

        # 条件を満たすもののうち，最大の報酬を選択
        if reward:
            ans += heappop(reward)

    # ヒープキューに追加するときに，-1倍した分を元に戻す
    print(-ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    # ヒープキューをインポート
    from heapq import heappush, heappop

    n, m = map(int, input().split())
    jobs = [[] for _ in range(m)]  # 締め切り別に，報酬を管理

    for i in range(n):
        ai, bi = map(int, input().split())

        # 報酬が振り込まれる日がM日よりも後になる場合は除外
        if ai > m:
            continue

        # i件目のアルバイトを遅くてもいつまでに始める必要があるかを計算
        # heappopは最小値を返す．biを-1倍することで，最大値が取り出せる
        deadline = m - ai
        jobs[deadline].append(-bi)

    ans = 0
    reward = []

    # M-1日に始める必要があるアルバイトのうち，最も報酬の高いものを選択
    # 以降，今日始める必要があるアルバイトまで，順番に調べる
    # ある時点で得られる報酬の大小に着目
    for i in range(m - 1, -1, -1):
        for job in jobs[i]:
            # ヒープキューに，報酬の候補を追加
            heappush(reward, job)

        # 条件を満たすもののうち，最大の報酬を選択
        if reward:
            ans += heappop(reward)

    # ヒープキューに追加するときに，-1倍した分を元に戻す
    print(-ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from sys import stdin

n,m = map(int,stdin.readline().rstrip().split())
jobs = [[] for i in range(m)]

for i in range(n):
    tmp,tmp2 = map(int,stdin.readline().rstrip().split())
    if(tmp>m):
        continue
    jobs[m-tmp].append(tmp2)
ans = 0
h=[]
for i in range(m-1,-1,-1):
    for b in jobs[i]:
        heapq.heappush(h,-b)
    if(len(h)!=0):
        a = -heapq.heappop(h)
        ans += a
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
X=[tuple(map(int,input().split())) for i in range(N)]
X.sort(key=lambda x:x[0])
ans=0
index=0
#print(X)
q=[]
for k in range(M):
    while(1):
        if not(index<N):
            break
        if X[index][0]<=k+1:
            heapq.heappush(q,-X[index][1])
            index+=1
        else:
            break
    
    if len(q)>0:
        ans-=heapq.heappop(q)
    #print(k,index,q,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

n,m=map(int,input().split())
job=[]
que=[]
heapq.heapify(que)
for i in range(n):
    a,b=map(int,input().split())
    job.append([a,b])
job.sort()
point=0
idx=0
for i in range(m):
    while(idx<n and job[idx][0]<=i+1):
        heapq.heappush(que,-1*job[idx][1])
        idx+=1
    if que:
        point+=heapq.heappop(que)*-1
print(point)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin
 
def main():
    n, m = map(int, input().split())
    dd = defaultdict(list)
    for _ in range(n):
        a, b = map(int, input().split())
        dd[a].append(b)
    
    ans = 0
    heap = []
    for i in range(1, m+1):
        if i in dd:
            for v in dd[i]:
                heappush(heap, v*-1)
        if len(heap) > 0:
            ans += -1 * heappop(heap)

    print(ans)
 
input = lambda: stdin.readline().rstrip()
main()

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 in dic:
    pass
  else:
    dic[a] = []
  
  dic[a].append(-b)
  
dic = dict(sorted(dic.items(),key=lambda x: -x[0]))

count = 0

lst = []
for i in range(1,m+1):
  if i in dic.keys():
    for num in dic[i]:
      heapq.heappush(lst, num)
  if len(lst) != 0:
    tmp = heapq.heappop(lst)
    count -= tmp
  

print(count)

Submission status: Accepted

Solution code:
import heapq

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

AB = [[] for _ in range(M)]

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

res = 0
cand = []

for i in range(M):
    AB[i].sort(reverse=True)
    for b in AB[i]:
        heapq.heappush(cand, b)
    if cand:
        mb = heapq.heappop(cand)
        res -= mb

print(res)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
import heapq

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    jobs = list(map(string_to_int, inputs))
    jobs.sort(key=lambda x: x[0], reverse=True)
    selectable = []
    money = 0
    for day in range(1, M + 1):
        while len(jobs) != 0 and jobs[-1][0] <= day:
            heapq.heappush(selectable, jobs.pop()[1] * -1)
        if len(selectable) != 0:
            money += heapq.heappop(selectable) * -1
    return money


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)

Submission status: Accepted

Solution code:
import heapq

def intoheap(l):
    for i in l:
        heapq.heappush(Q, -i)
        
n,m = map(int,input().split())
P = {i:[] for i in range(1,m+1)}
Q = []
ans = 0
for _ in range(n):
    a,b = map(int, input().split())
    if a > m:
        continue
    P[a].append(b)
        

for i in range(1,m+1):
    if i in P.keys():
        intoheap(P[i])
    if Q == []:
        continue
    ans += -heapq.heappop(Q)
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import *


n, m = list(map(int, input().split()))
job = [list(map(int, input().split())) for _ in range(n)]
job.sort(reverse=True)
q = []
ans = 0
for i in range(m-1, -1, -1):
    while job and job[-1][0] + i <= m:
        a, b = job.pop()
        heappush(q, -b)

    if q:
        ans -= heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int,input().split())
jobs = [list(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
q = []
sum = 0

for i in range(m+1):
    #1行後でpopで取り出すので，-1で指定しないといけない
    while jobs and jobs[-1][0] < i+1:
        a,b = jobs.pop()#jobsの一番最後の要素を取り出して削除
        #あとで最大の要素を取り出したいが，heappopは最小の要素を取り出すので-1倍して格納
        heapq.heappush(q,-b)
            
    
    if q:#リストqが空のときはskip
        #heappopで最小の要素を-1倍して取り出すと最大の要素
        sum += -heapq.heappop(q)
print(sum)

Submission status: Accepted

Solution code:
import heapq

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

d = {}
for a,b in ab_list:
    if a in d:
        d[a].append(-b)
    else:
        d[a] = [-b]

b_list = []
heapq.heapify(b_list)
reward = 0
for i in range(1,M+1):
    if i in d:
        for b in d[i]:
            heapq.heappush(b_list,b)
    if len(b_list) > 0:
        reward += -(heapq.heappop(b_list))

print(reward)

Submission status: Accepted

Solution code:
import heapq as h
n,m = map(int,input().split())
ans = 0
l = [0]*m
d = {i:[] for i in range(1,m+1)}
for _ in range(n):
  a,b = map(int,input().split())
  if a>m:
    continue
  d[a].append(b)
for i in range(1,m+1):
  if i in d:
    for x in d[i]:
      h.heappush(l,-x)
  ans -= h.heappop(l)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
Wlist = []
for i in range(N):
    A, B = map(int, input().split())
    Wlist.append([A,B])
Wlist.sort(key=lambda x:x[0])

h = []
Ans = 0
Index = 0
for day in range(1,M+1):
    while Index < N:
        if Wlist[Index][0] <= day:
            heapq.heappush(h, -Wlist[Index][1])
            Index += 1
        else:
            break
    if len(h):
        Ans += -heapq.heappop(h)

print(Ans)

Submission status: Accepted

Solution code:
import heapq
num, day = map(int, input().split())

dic = dict()
for i in range(num):
    days, pay = map(int, input().split())
    dic.setdefault(days, []).append(pay)
#print(dic)
taku = []
ans = 0
today = day
while today >= 0:
    key = day - today
#    print("today is "+str(today)+", key is "+str(key))
    if key in dic:
        for s in dic[key]:
            heapq.heappush(taku, s*(-1))
#    print(taku)
    if len(taku) != 0:
        ans -= heapq.heappop(taku)
    today -= 1
#    print(taku)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = (int(i) for i in input().split())
jobs = [[] for i in range(m)]
for i in range(n):
    tmp,tmp2 = (int(i) for i in input().split())
    if(tmp>m):
        continue
    jobs[m-tmp].append(tmp2)
    
ans = 0
h=[]
for i in range(m-1,-1,-1):
    for b in jobs[i]:
        heapq.heappush(h,-b)
        
    if(len(h)!=0):
        a = -heapq.heappop(h)
        ans += a

print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int, input().split())
works = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a not in works:
        works[a] = [b]
    else:
        works[a].append(b)
rewards = []
reward_sum = 0
for k in range(M+1):
    if k in works:
        print()
        for j in works[k]:
            heapq.heappush(rewards, -j)
    if len(rewards) != 0:
        reward_sum -= heapq.heappop(rewards)
print(reward_sum)

Submission status: Accepted

Solution code:
import heapq
#listから複数index削除するやつ
dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

[N,M]=[int(x) for x in input().split()]
work=[[int(x) for x in input().split()] for _ in range(N)]

work.sort() #日付の短い順にsortしておく　これいる？いる！！！！
tank=[] #候補を入れる
res=0 #回答
j=0

for i in range(M+1): #日付を後ろから見ていく
  while j<=N-1 and work[j][0]<=i: #forじゃないのはheapqに入れた分はずっと候補なのでもうみなくていいため
    heapq.heappush(tank,-work[j][1])
    j+=1
  #print("tank1:",tank)
  
  if len(tank)==0: #候補がなければ次の日へ
    #print("continue.")
    continue

  else: #候補があればもっとも良いのを回答に足す
    res -= heapq.heappop(tank)
    #print("res=",res)
    
  #print("tank2:",tank)
    
print(res)

Submission status: Accepted

Solution code:
import heapq

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

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

AB_array = sorted(AB_array, key=lambda x: x[0])


h = []

ab_index = 0
ans = 0
for m in range(1, M+1):
    while ab_index != N:
        if AB_array[ab_index][0] == m:
            heapq.heappush(h, -AB_array[ab_index][1])
            ab_index += 1
        else:
            break

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
from sys import exit, stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
AB = [[] for _ in range(M)]

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

ans = 0
heap = []

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

print(ans)

Submission status: Accepted

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

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

AB_array = sorted(AB_array, key=lambda x: -x[1])

# print(AB_array)

used_array = [0] * M
next_array = [i for i in range(M)]

ans = 0

for AB in AB_array:
    A, B = AB
    # print(A, B)
    ok_flag = 0
    start = M - A
    if start < 0:
        continue
    while(ok_flag == 0):
        start = next_array[start]
        if start == -1:
            next_array[M-A] = -1
            break
        if used_array[start] == 0:
            ok_flag = 1
    else:
        ans += B
        used_array[start] = 1
        next_array[start] = start - 1
        next_array[M-A] = start - 1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
d = dict()
for _ in range(n):
    a, b = map(int, input().split())
    d.setdefault(a, [])
    d[a].append(-b)

h = []
ans = 0
for i in range(1, m + 1):
    for b in d.get(i, []):
        heappush(h, b)
    if len(h) > 0:
        m = heappop(h)
        ans -= m
print(ans)

Submission status: Accepted

Solution code:
import heapq

(n, m) = map(int, input().split())
jobs = {}
for _ in range(n):
    (a, b) = map(int, input().split())
    if not a in jobs:
        jobs[a] = []
    jobs[a].append(-b)

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

Submission status: Accepted

Solution code:
import heapq

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

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [-b]
    else:
        jobs[a].append(-b)
# print(jobs)
sum_money = 0
money_list = [0]
heapq.heapify(money_list)
for i in range(1, m+1):
    if i in jobs.keys():
        for money in jobs[i]:
            heapq.heappush(money_list, money)
    # print(money_list)
    max_money = -heapq.heappop(money_list)
    sum_money += max_money
    if max_money == 0:
        heapq.heappush(money_list, 0)
print(sum_money)

Submission status: Accepted

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

for i in range(n):
  a,b = (int(x) for x in input().split())
  if(m-a >= 0):
    arr[m-a].append(b)
q = []  
ans = 0
for i in range(m-1,-1,-1):
  for item in arr[i]:
    heapq.heappush(q, -item)
  if(len(q) != 0):
    ans += -1*(heapq.heappop(q))
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

rewards_list_vs_days = [[] for _ in range(M+1)]
for _ in range(N):
    days,reward = list(map(int, input().split()))
    if days <= M:
        rewards_list_vs_days[days].append(reward)

#print(rewards_list_vs_days)

minus_rewards_of_available_jobs = []

total_reward = 0

for day in reversed(list(range(M))):
    rest_days = M-day
    for reward in rewards_list_vs_days[rest_days]:
        heapq.heappush(minus_rewards_of_available_jobs, -reward)
    if len(minus_rewards_of_available_jobs) > 0:
        max_reward = - heapq.heappop(minus_rewards_of_available_jobs)
        total_reward += max_reward
    
print(total_reward)