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 = list(map(int,input().split()))
A = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append([in1, in2])

A = sorted(A)
ans = 0
day = 1
cnt = 0
x = []

for i in range(M):
    while(cnt < N):
        if A[cnt][0] == day:
            heapq.heappush(x, -A[cnt][1])
            cnt += 1
        else:
            break
    if x:  ans -= heapq.heappop(x)
    day += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,m=map(int, input().split())
    li=[]
    for _ in range(n):
        b,a=map(int, input().split())
        if m-b >= 0:
            li.append([a,m-b])
    li.sort(key=lambda x: x[1])
    h=[]
    for i in li:
        if len(h) >= i[1]+1:
            heapq.heappushpop(h, i[0])
        else:
            heapq.heappush(h, i[0])
    print(sum(h))
    

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def readinput():
    n,m=map(int,input().split())
    a=[]
    b=[]
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append(ai)
        b.append(bi)
    return n,m,a,b

def main(n,m,a,b):
    jobList=[]
    for i in range(10**5+1):
        jobList.append([])
    for i in range(n):
        jobList[a[i]].append(b[i])

    goodjobs=[]
    earn=0
    for d in range(1,m+1):
        for job in jobList[d]:
            heappush(goodjobs,-job)
        #print(goodjobs)
        if len(goodjobs)>0:
            earn+=heappop(goodjobs)
    return -earn

if __name__=='__main__':
    n,m,a,b=readinput()
    ans=main(n,m,a,b)
    print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
x = [[] for _ in range(m + 1)]
y = []
heapq.heapify(y)
for i in range(1, m + 1):
    heapq.heapify(x[i])
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        heapq.heappush(x[a], -b)
ans = 0
for i in range(1, m + 1):
    if x[i]:
        s = heapq.heappop(x[i])
        heapq.heappush(y, [s, i])
    if y:
        s, t = heapq.heappop(y)
        ans -= s
        if x[t]:
            s = heapq.heappop(x[t])
            heapq.heappush(y, [s, t])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush
N, M = map(int, sys.stdin.readline().split())
A = defaultdict(list)
for line in sys.stdin:
    a, b = map(int, line.split())
    if a <= M:
    	A[M-a].append(b)

ans = 0
q = []
for i, B in sorted(A.items()):
    for b in B:
        heappush(q, b)
        ans += b
    while len(q) > i+1:
        b = heappop(q)
        ans -= b
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
N, M = map(int, sys.stdin.readline().split())
A = [[] for _ in [0]*M]
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > M:
        continue
    A[M-a].append(b)

ans = 0
q = []
for i, B in enumerate(A):
    for b in B:
        heappush(q, b)
        ans += b
    while len(q) > i+1:
        b = heappop(q)
        ans -= b
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

lines = []
for line in sys.stdin:
    lines.append(line.rstrip('\r\n'))
#print(lines)
n,m = lines[0].split()
n = int(n)
m = int(m)

a=[]
for i in range(n):
    x,y = lines[i+1].split()
    x = int(x)
    y = int(y)*(-1)
    a.append((x,y))
a.sort()
a.append((0,0))

h = []

cur = 0
summ = 0
for i in range(1,m+1):
    while(cur<n and a[cur][0]<=i):
        heappush(h,a[cur][1])
        cur+=1
    if(len(h)>0):
        summ+=heappop(h)*(-1)
print(summ)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
 
N,M = map(int,readline().split())
from collections import defaultdict
tasks = defaultdict(list)
for i in range(N):
  a,b = map(int,readline().split())
  tasks[a].append(b)
  
import heapq as hq
q = []
ans = 0
for i in range(1, M + 1):
  newtask = tasks[i]
  for t in newtask:
    hq.heappush(q,-t)
  if q:
    ans += -hq.heappop(q)
 
print(ans)

Submission status: Accepted

Solution code:
def main():
    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]
        else:
            job[a].append(b)
    ans = 0
    hp = []
    for i in range(1,m+1):
        if i in job.keys():
            for j in range(len(job[i])):
                heapq.heappush(hp,-1*job[i][j])
        if len(hp)>0:
            ans += -1*heapq.heappop(hp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

n,m = map(int, input().split())
ab = [[] * (m+1) for i in range(m+1)]
for i in range(n):
  a,b = map(int, input().split())
  if m - a < 0:
    continue
  ab[a].append(b)

q=[]
ans = 0
heapq.heapify(q)
for i in range(1,m+1):
  for j in ab[i]:
    heapq.heappush(q, j*(-1))
  if q:
    b = heapq.heappop(q)
    ans += (-1) * b
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
limit = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        # 間に合わないので使えない        
        continue
    # m-a日目までに取り掛かれば間に合うバイトを格納
    limit[m-a].append(b)

available = []
ans = 0
for i in range(m-1, -1, -1):
    # 最終日から辿ることで、新たに選択不可となるバイトが生じない
    for item in limit[i]:
        heapq.heappush(available, -item)
    if available:
        ans += -heapq.heappop(available)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    B = [[] for _ in range(m)]
    for _ in range(n):
        a, b = map(int, input().split())
        if m - a >= 0:
            B[m - a].append(b)

    que = []
    res = 0
    for i in reversed(range(m)):
        for b in B[i]:
            heappush(que, -b)
        if que:
            res += heappop(que) * (-1)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M = map(int, input().split())
    a_to_b = {}
    for i in range(N):
        a, b = map(int, input().split())
        if a <= M:
            if a not in a_to_b:
                a_to_b[a] = []
            a_to_b[a].append(b)

    res = 0
    h = []
    for i in range(1,M+1):
        if i in a_to_b:
            b_list = a_to_b[i]
            for bi in b_list:
                heapq.heappush(h, (-1)*bi)
        if len(h) > 0:
            res -= heapq.heappop(h)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(n)]
ab=list(sorted(ab, key=lambda x: x[0]))

import heapq
hq=[]
ans=0
j=0
for i in range(1, m+1):  # m-i日後を考える
    while (j<n) and (ab[j][0]<=i):
        heapq.heappush(hq, -ab[j][1])
        j+=1
    if len(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())
D = defaultdict(list)

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

H = []
ans = [0]*(M+1)

for i in range(1, M+1):
  for j in D[i]:
    heappush(H, -j)
  if H:
    a = heappop(H)
    ans[i] = -a

print(sum(ans))

Submission status: Accepted

Solution code:
import sys

# import bisect
# map(int, sys.stdin.read().split())
from collections import Counter
import heapq
from collections import deque

def input():
    return sys.stdin.readline().rstrip()


def main():
    N,M = map(int,input().split())
    A =[]
    for i in range(N):
        a,b = map(int,input().split())
        A.append((a,-b))
    A.sort()
    A = deque(A)

    h = []
    ans =0
    for i in range(1,M+1):

        while A:
            if A[0][0] ==i:
                temp = A.popleft()
                heapq.heappush(h,temp[1])
            else:
                break

        if len(h)==0:
            continue
        else:
            ans += heapq.heappop(h)


    print(-ans)







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#<D>
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for n in range(N)], key = lambda x: x[0])
#print(X)
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

n, m = map(int,input().split())
ab = [[0] * 2 for i in range(n)]
for i in range(n):
    a, b = map(int,input().split())
    ab[i][0], ab[i][1] = a, -1*b
heapq.heapify(ab)

b = [0]
heapq.heapify(b)
ans = 0
for i in range(1, m+1):
    while ab:
        tmp = heapq.heappop(ab)
        if tmp[0] <= i:
            heapq.heappush(b, tmp[1])    
        else:
            heapq.heappush(ab, tmp)
            break
    if b:
        ans -= heapq.heappop(b)
print(ans)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

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

AB = []
for i in range(N):
    a,b = LI()
    AB.append((a,-b))

from operator import itemgetter

AB = sorted(AB,key = itemgetter(0))

import heapq

L = []
heapq.heapify(L)

ans = 0
r = 0
for i in range(1,M+1):
    for j in range(r,N):
        if AB[j][0] == i:
            heapq.heappush(L,AB[j][1])
        else:
            r = j
            break
    if len(L) >= 1:
        ans -= heapq.heappop(L)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    #print(AB)
    import heapq
    cands = []
    abidx = 0
    ans = 0
    day = M
    while day > 0:
        #print(abidx)
        while abidx < N and AB[abidx][0] <= M-day+1:
            _, point = AB[abidx]
            heapq.heappush(cands, -point)
            abidx += 1
        if len(cands) > 0:
            ans += heapq.heappop(cands)
            #print(-ans)
        day -= 1
    print(-ans)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N, M = MAP()
AB = [LIST() for _ in range(N)]
AB.sort(key = lambda x: x[0])

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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [[] for _ in range(10**5+1)]
for _ in range(N):
    a, b = map(int, input().split())
    AB[a].append(b)

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

ans = 0
for a in range(1,M+1):
    for b in AB[a]:
        heapq.heappush(h, -b)
    heapq.heappush(h, 0)
    ans -= heapq.heappop(h)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import heapq

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    # 支給日ごとの報酬(降順)をまとめたリストを作成する。
    # 支給日が1日後:10,4,2円・・ 支給日が3日後:100,50円・・の場合 =  1[2,4,10] 3[50,100]　という感じ。
    # 降順にしておけば、取り出したい値=最大値が末尾にくるので、
    # 後述のキュー処理に要する処理量を抑えることができる。(list.pop()を使えるので)
    ab_list = [[] for i in range(100001)]
    for i in ab_s:
        ab_list[i[0]].append(i[1])
    for i in ab_list:
        if len(i) == 0:
            continue
        i.sort()

    a = []
    heapq.heapify(a)

    ans = 0
    # 　最適なバイトを、制限の多い地点から決めていく。(今回は、日が進むごとに制限が増えるので、
    # 　最も制限の多い最終日->最も制限のない1日目の順に決める)
    for i in range(1, m + 1):
        # (給与,支給日)の形でキューに追加。
        if len(ab_list[i]) != 0:
            heapq.heappush(a, (-ab_list[i].pop(), i))

        if len(a) != 0:
            act_work = heapq.heappop(a)
            ans += -act_work[0]

            if len(ab_list[act_work[1]]) != 0:
                heapq.heappush(a, (-ab_list[act_work[1]].pop(), act_work[1]))

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_original_1(self):
        test_input = """3 4
4 210
4 150
3 150"""
        output = """360"""
        self.assertIO(test_input, output)

    def test_original_2(self):
        test_input = """2 1
1 10
1 20
"""
        output = """20"""
        self.assertIO(test_input, output)

    def test_original_3(self):
        test_input = """1 2
1 10
"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_original_4(self):
        test_input = """5 3
4 50
4 50
3 10
3 10
1 10
"""
        output = """20"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

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

N,M = map(int,readline().split())
from collections import defaultdict
tasks = defaultdict(list)
for i in range(N):
  a,b = map(int,readline().split())
  tasks[a].append(b)
  
import heapq as hq
q = []
ans = 0
for i in range(1, M + 1):
  newtask = tasks[i]
  for t in newtask:
    hq.heappush(q,-t)
  if q:
    ans += -hq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import heapq
import collections

N, M = rl()
daytasks = collections.defaultdict(list)
for i in range(N):
	a, b = rl()
	daytasks[a].append(b)

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

Submission status: Accepted

Solution code:
def resolve():    
    import heapq
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n)]
    b=[[] for _ in range(10**5+1)]
    for i,j in ab:
        b[i].append(-j)
    q=[]
    ans=0
    for i in range(1,m+1):
        for j in b[i]:
            heapq.heappush(q,j)
        if q:
            ans+=heapq.heappop(q)
    print(-ans)
        
if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import heapq
x = [[] for _ in range(10**5+1)]
n,m = map(int,input().split())

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

ans = 0
for l in range(1,m+1):
    for k in x[l]:
        heapq.heappush(cur, k*(-1))
    
    if cur != []:
        mi = heapq.heappop(cur)
        ans += mi * (-1)
        
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N,M=map(int,input().split())
X=[[] for i in range(M)]
A,B=0,0
for i in range(N):
  A,B=map(int,input().split())
  if A>M:
    continue
  X[-A].append(B)
P=0
Q=[]
heapify(Q)
for i in range(M-1,-1,-1):
  for j in range(len(X[i])):
    heappush(Q,-X[i][j])
  if len(Q):
    P-=heappop(Q)
print(P)

Submission status: Accepted

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

N, M = map(int,input().split())
work = [[] for _ in range(10**5+1)]
ava = []
ans = 0

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

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

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
que = []
for _ in range(n):
    a, b = map(int, input().split())
    que.append((-b, a))
que.sort(key=lambda x: x[1], reverse=True)

def solve(que, m):
    ans = 0
    h = []
    heapq.heapify(h)
    for i in range(1, m + 1):
        while len(que) != 0 and que[-1][1] <= i:
            tmp = que.pop()
            heapq.heappush(h, tmp)
        if len(h) == 0: continue
        tmp = heapq.heappop(h)
        ans -= tmp[0]
    return ans

print(solve(que, m))

Submission status: Accepted

Solution code:
import collections
import heapq

n, m = map(int, input().split())
que = []
for _ in range(n):
    a, b = map(int, input().split())
    que.append((-b, a))
que.sort(key=lambda x: x[1])
que = collections.deque(que)
h = []
heapq.heapify(h)
ans = 0
for i in range(1, m + 1):
    while len(que) != 0 and que[0][1] <= i:
        tmp = que.popleft()
        heapq.heappush(h, tmp)
    if len(h) == 0: continue
    tmp = heapq.heappop(h)
    ans -= tmp[0]
print(ans)

Submission status: Accepted

Solution code:
_,m=map(int,input().split())
work=sorted([tuple(map(int,input().split()))for k in range(_)],key=lambda x:(-x[0],x[1]))
from heapq import heapify, heappop, heappush
now=[]
#print(work)
ans=0
for i in range(1,m+1):
    while work and work[-1][0]<=i:
        a,b=work.pop()
        heappush(now,-b)
        #print(a,b)
    
    if now:
        ans-=heappop(now)
    #print(i,ans)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m= map(int,input().split())
feeindays = [[] for _ in range(m)]
for i in range(n):
    a,b= map(int,input().split())
    if a<=m:feeindays[a-1]+=[b]
q=[]
heapq.heapify(q)
pay=0
for l in feeindays:
    for c in l:heapq.heappush(q,-c)
    if len(q)!=0:pay+=-1 * heapq.heappop(q)
print(pay)

Submission status: Accepted

Solution code:
from heapq import heappop, heapify, heappush
from collections import defaultdict
N, M = map(int,input().split())
d = defaultdict(list)
for i in range(N):
    a, b = map(int, input().split())
    d[a].append(b)
h = []
ans = 0
for i in range(1, M+1):
    if len(d[i]) != 0:
        for x in d[i]:
            heappush(h, -x)
    if len(h) != 0:
        ans -= heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = map(int, input().split())
day_rews_l = [ [] for _ in range(m+1)]
for _ in range(n):
    a,b = map(int, input().split())
    if a > m: continue
    day_rews_l[a].append(b)


jobs = []
ans = 0
for i in range(1,m+1):
    for rew in day_rews_l[i]:
        heapq.heappush(jobs, (-1)*rew)
    if jobs:
        rew_i = heapq.heappop(jobs)
        ans += (-1)*rew_i

print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    job = [[] for i in range(m+1)]
    for i in range(n):
        a,b = map(int,ipt().split())
        if a <= m:
            job[a].append(-b)
    ma = 0
    hq = []
    for i in range(m+1):
        for j in job[i]:
            hpq.heappush(hq,j)
        if hq:
            ma += hpq.heappop(hq)
    print(-ma)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

pq = []
for a, b in X:
    heappush(pq, (a, b))
    
cand = []
ans = 0
for t in range(1, M + 1):
    while pq:
        a, b = heappop(pq)
        if a <= t:
            heappush(cand, -b)
        else:
            heappush(pq, (a, b))
            break

    if cand:
        v = heappop(cand)
        ans += -v

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()
query = [getList() for i in range(N)]

A_list = [[] for i in range(10 ** 5 + 1)]
for a, b in query:
    A_list[a].append(b)

job = []
heapq.heapify(job)

ans = 0
for i in range(1, M + 1):
    for j in A_list[i]:
        heapq.heappush(job, -j)
    if len(job) > 0:
        u = heapq.heappop(job)
        ans += -u
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  if a<=m:
    ab[m-a].append(-b)

ans=0
l=[]
for i in range(m-1,-1,-1):
  for b in ab[i]:
    heappush(l,b)

  if l:
    ans-=heappop(l)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

n,m=[int(x) for x in input().rstrip().split()]
ab=[[] for i in range(10**5)]

for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  ab[a-1].append(-b)

ans=0
time=0
l=[]
for i in range(m):
  for b in ab[i]:
    heappush(l,b)
  if l:
    ans-=heappop(l)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(10**5)]
    for i in range(N):
        a, b = map(int, input().split())
        AB[a-1].append(b)
    
    q = []
    ans = 0
    i = 0
    while i < M:
        for ab in AB[i]:
            heappush(q,-ab)
        if q:
            ans -= heappop(q)
        i += 1
    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 i in range(n)]
ab.sort(key=lambda x:x[0])
counter = 0
content = 0
ans = 0
h = []
heapq.heapify(h)
for i in range(m):
  while counter < n and ab[counter][0]==i+1:
    heapq.heappush(h,-ab[counter][1])
    counter+=1
    content+=1
  if content != 0:
    ans-=heapq.heappop(h)
    content-=1
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
W = ILL(N)

W.sort(reverse=True)

ans = 0
q = []
for i in range(M+1):
  while W:
    if W[-1][0] > i: break
    d,v = W.pop()
    heapq.heappush(q,-v)
  if q:
    ans -= q[0]
    heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
#18:10~
#Aが短いものから貪欲で行けそう
from heapq import *
n,m=map(int,input().split())
#何日かかるのかで(1-indexed)
ab=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    #超えないように
    if a<=m:
        ab[a-1].append(b)
x=[]
l=0
ans=0
for i in range(m-1,-1,-1):
    for j in ab[m-1-i]:
        heappush(x,-j)
        l+=1
    if l:
        l-=1
        ans+=heappop(x)
print(-ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    que = []
    res = 0
    for i in reversed(range(m)):
        for b in AB[i]:
            heappush(que, -b)
        if que:
            res += heappop(que) * -1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

import heapq
q = []
ans = 0
heapq.heapify(q)
for i in range(1,m+1):
    for v in V[i]:
        heapq.heappush(q,v)

    if len(q) == 0:
        pass
    else:
        ans -= heapq.heappop(q)
print(ans)