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:
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    l = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    r = []
    heapq.heapify(l)
    heapq.heapify(r)
    t = 0
    for i in range(m + 1):
        while True:
            if len(l) != 0:
                a, b = heapq.heappop(l)
                if a <= i:
                    heapq.heappush(r, -b)
                else:
                    heapq.heappush(l, [a, b])
                    break
            else:
                break
        if len(r) != 0:
            t += -heapq.heappop(r)
    print(t)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def main():
     import heapq
     import sys
     input=sys.stdin.readline

     ans=0
     N,M=map(int,input().split())
     Ar=[]
     for _ in range(M):
           Ar.append([])
     for _ in range(N):
          A,B=map(int,input().split())
          if A <= M:
              Ar[A-1].append(-B)
     An=[]
     for i in range(M):
          for j in Ar[i]:
              heapq.heappush(An,j)
          if len(An)>0:
              ans+=-heapq.heappop(An)
     print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
a,b = map(int,input().split())
L = []
for _ in range(a):
    L.append( tuple(map(int,input().split())) )
L = sorted(L)
h = []
c = 0
ans = 0
for i in range(1,b+1):
    while True:
        if c >= len(L): break
        if L[c][0] <= i:
            heapq.heappush(h,-L[c][1])
            c += 1
        else:
            break
    try :
        ans += -heapq.heappop(h)
    except:
        pass
print(ans)

Submission status: Accepted

Solution code:
import heapq

N,M=map(int,input().split())
A=[0 for _ in range(N)]
B=[0 for _ in range(N)]
for i in range(N):
  A[i],B[i]=map(int,input().split())
#print(A)
#print(B)

tasks=[[] for _ in range(10**5+1)]
for i in range(N):
  tasks[A[i]-1].append(B[i])
#print(tasks)

pq=[]
ans=0
for i in range(M):
  for b in tasks[i]:
    heapq.heappush(pq,-b)
  if len(pq)!=0:
    temp=heapq.heappop(pq)
    ans-=temp
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N,M = map(int,input().split())
AB = []
for i in range(N):
  AB.append(list(map(int,input().split())))
AB.sort()
#print(AB)

hq = []
idx = 0
ans = 0
for day in range(1,M+1):
  while (idx < N and AB[idx][0] == day):
    heappush(hq, -AB[idx][1])
    idx += 1
  if len(hq) > 0:
    ans -= heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())
    jobs = [list(map(int, input().split())) for _ in range(n)]

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

    hq = []
    ans = 0

    for i in range(1, m+1):
        for j in range(len(jobs)-1, -1, -1):
            if jobs[j][0] != i:
                break
            heappush(hq, jobs[j][1]*-1)
            jobs.pop()
        if len(hq) > 0:
            ans += heappop(hq)*-1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        job= [int(number) for number in input().split()]
        part_times.append(job)
    part_times = [part_time for part_time in sorted(part_times, key = lambda x: x[0])] #if part_time[0] <= M]
    money = 0
    hp = []
    for day in range(M):
        while part_times != [] and part_times[0][0] <= day + 1:
            part_time = part_times[0]
            heapq.heappush(hp, - part_time[1])
            part_times.pop(0)
        if hp != []:
            money -= heapq.heappop(hp)

    print(money)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""#自分で考えたやつ
N, M = map(int, input().split())
AB = []
for i in range(N):
    a, b =  (int(x) for x in input().split())
    AB.append([a, b])
AB.sort(key=lambda x: x[1])

dic = {}
for i in range(M):
"""

import heapq

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

# 仕事の制約が厳しい順にリストに格納する
Blist = [[] for _ in range(M)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M: # AがMより大きいといつやっても間に合わない
        Blist[A-1].append(-B) # heapdを使うことを考慮して-倍しておく

ans = 0
q = [] # heapd.heapify(q)でリストのヒープ化ができるがここではlen(q)を使いたいためにしないでおく

# 可能な仕事をqに入れて扱う。その中でもBが最大(「-」倍しているのでここでは最小)のものを優先して取り出す。
for i in range(M):
    for b in Blist[i]: # ヒープ化されたリストqに2次元のBlistのi番目のリストの要素を全て入れる
        heapq.heappush(q, b)
    if len(q) > 0: # qに要素があるならば、qから最小の要素を取り出して(「-」倍してあるので)それを引き算する
        ans -= heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
lst = [[] for i in range(m)]
for i in range(n):
  a, b = map(int, input().split())
  if a <= m:
    lst[a-1].append(b)
q = []
res = 0
for i in range(m):
  while lst[i]:
    b = lst[i].pop()
    heapq.heappush(q, -b)
  if len(q) > 0:
    b = heapq.heappop(q)
    b = -b
    res += b
print(res)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def getlist():
	return list(map(int, input().split()))

N, M = getlist()
task = []
for i in range(N):
	A, B = getlist()
	heappush(task, [A, B])

Q = []
ans = 0
for i in range(M):
	while True:
		if task != [] and task[0][0] ==1 + i:
			a, b = heappop(task)
			heappush(Q, [-b, a])
		else:
			break
	if Q != []:
		x, y = heappop(Q)
		ans += -x


print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
# setrecursionlimit(10**7)


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = defaultdict(list)
    v = 0
    for i in range(N):
        a,b = [int(n) for n in input().split()]
        if a <= M:
            jobs[a].append(-b)
    cand = []
    ans = 0
    for i in range(1,M+1):
        for e in jobs[i]:heapq.heappush(cand,e) 
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
import heapq
# from collections import defaultdict
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    # {期限:価値}
    jobs = [[]]*N
    v = 0
    for i in range(N):
        jobs[i] = [int(n) for n in input().split()]
    # 価値降順→期間昇順
    jobs = sorted(jobs,key=lambda x:-x[1])
    jobs = sorted(jobs,key=lambda x:x[0])
    cur = 0
    ans = 0
    cand = []
    for i in range(1,M+1):
        while(cur < N and i >= jobs[cur][0]):
            heapq.heappush(cand,-jobs[cur][1])
            cur += 1
        if len(cand) != 0:
            ans -= cand[0]
            heapq.heappop(cand)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict
N, M = map(int, input().split())
H = []
D = defaultdict(list)
for _ in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    else:
        D[a].append(b)

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

print(ans)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    paylist = [[] for _ in range(M)]
    for _ in range(N):
        a,b = map(int,input().split())
        if M >= a:
            heapq.heappush(paylist[a-1],-b)
    work = []
    payment = 0
    for i in range(M):
        for j in paylist[i]:
            heapq.heappush(work,j)
        if work:
            payment += heapq.heappop(work)

    print(-payment)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#D問題
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    ab = list(map(int,input().split()))
    heapq.heappush(AB,ab)
    
ans = 0
cand = []
for i in range(M):
    while AB:
        ab = heapq.heappop(AB)
        if ab[0] <= (i+1):
            heapq.heappush(cand,10**5-ab[1])
        else:
            heapq.heappush(AB,ab)
            break
    
    if len(cand) >= 1:
        cd = heapq.heappop(cand)
        ans+=(10**5-cd)
    
print(ans)

Submission status: Accepted

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

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)
rewords = 0
heap = []
for i in range(M):
    for reword in jobs[i]:
        heapq.heappush(heap, reword)
    if len(heap) >0:
        reword = heapq.heappop(heap)
        rewords += -reword

print(rewords)

Submission status: Accepted

Solution code:
import heapq

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

#仕事の制約の厳しい順にリストに格納する
Blist = [[] for _ in range(M)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M: # AがMより大きいといつやっても間に合わない
        Blist[A-1].append(-B) # heapqを使うことを考慮して「-」倍しておく

ans = 0
q = [] # heapq.heapify(q)でリストのヒープ化ができるがここではlen(q)を使いたいためにしないでおく

# 可能な仕事をqに入れて扱う。その中でもBが最大(「-」倍しているのでここでは最小)のものを優先して取り出す。
for i in range(M):
    for b in Blist[i]: # ヒープ化されたリストqに2次元のBlistのi番目のリストの要素を全て入れる
        heapq.heappush(q, b)
    if len(q) > 0: # qに要素があるならば、qから最小の要素を取り出して(「-」倍してあるので)それを引き算する
        ans -= heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq
 
N, M = map(int, input().strip().split())
 
A = {}
 
for i in range(N):
  a, b = map(int, input().strip().split())
  if a not in A: A[a] = []
  A[a].append(b)

total = 0
days = [] #heap先
for i in range(1, M + 1): #1～M
  if i in A: #i日かかる仕事が候補にあったら
    for a in A[i]:
      heapq.heappush(days, -a) #daysにi日かかる金額をすべて入れる（最大値を出すため-1かける）
  if len(days) > 0:
    total += - heapq.heappop(days) #最大値（金額）を追い出して足す
                                   #i日かかる仕事が無ければ前回ためてたのが出る
 
print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
n, m = map(int, input().split())
baito_dict = defaultdict(list)
for _ in range(n):
    day, weight = map(int, input().split())
    baito_dict[day].append(weight)


max = 0

available_works = []

for day in range(1, m+1):
    for weight in baito_dict[day]:
        heappush(available_works, -weight)
    if available_works:
        max += heappop(available_works)

print(-max)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N,M = map(int, input().split())
a = [[int(i) for i in input().split()] for i in range(N)]

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

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N,M = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB,key= lambda x: x[0])
hq = []
ans = 0
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 len(hq):
  	ans += -heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

dict = defaultdict(list)
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    dict[A].append(B)

h = []
total = 0
for x in range(1, M + 1):
    for y in dict[x]:
        heapq.heappush(h, -y)
    if h:
        total += heapq.heappop(h)

print(-total)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]
ab = deque(sorted(ab, key=lambda x: x[0]))

ans = 0
q = []
for i in range(1, m+1):
  while len(ab) and ab[0][0]<=i:
    a, b = ab.popleft()
    heappush(q, -b)
  if len(q):
    ans += -heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

for i in range(M):
    
    for j in A[i]:
        heapq.heappush(cand, j)
        
    if cand:
        ans -= heapq.heappop(cand)
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
work=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    if a>=m:continue
    heapq.heappush(work[a],-b)
#print(work)
ans=0
nowwork=[]
for i in range(m):
    for j in work[i]:
        heapq.heappush(nowwork,j)
    #print(nowwork)
    if nowwork==[]:
        continue
    ans+=heapq.heappop(nowwork)
print(-ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

ans = 0
hq = []
n,m = inpl()
ab = [[] for i in range(m)]
for i in range(n):
    a,b = inpl()
    if a <= m:
        ab[a-1].append(b)

heapq.heapify(hq)
for i in range(m):
    for j in ab[i]:
        heapq.heappush(hq,-j)
    if hq:
        ans -= heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:

import heapq
from collections import defaultdict

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

a_b_dict = defaultdict(list)
for _ in range(N):
    a, b = tuple(map(int, input().split()))
    a_b_dict[a].append(b)

result = []
h = []
num_days = 0
for i in range(1, 1+M):
    for b in a_b_dict.get(i, []):
        heapq.heappush(h, -b)
    if len(h) > 0:
        result.append(-1*heapq.heappop(h))
print(sum(result))

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())
	if a>m:
		continue
	works.append((a,b))
works.sort(reverse=True)
q=[]
ans=0

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

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

works.sort(reverse=True)

q = []
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict
n, m = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dic = defaultdict(list)
for ele in a_b:
    dic[ele[0]].append(ele[1])

#print(dic)
L =[]
money = 0
for d in range(1, m+1):
    for e in dic[d]:
        heapq.heappush(L, -e)
    if L:
        money +=heapq.heappop(L)
print(-money)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
ab=[]
n,m=map(int,input().split())
for i in range(n):
	x,y=map(int,input().split())
	ab.append([x,y])
ab.sort()
k=0
ans=0
hq=[]
cnt=0
for i in range(1,m+1):
	if k>n-1:
		break
	while ab[k][0]<=i:
		heappush(hq,-ab[k][1])
		k+=1
		if k>n-1:
			break
	if len(hq)!=0:
		ans+=heappop(hq)
	cnt+=1
if cnt<m:
	for i in range(m-cnt):
		ans+=heappop(hq)
print(-ans)

Submission status: Accepted

Solution code:
import heapq as hp

n,m =[int(i) for i in input().split()]
lists = [[] for i in range(m)]

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  if a<=m:
  	lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if len(h)>0:
    ans -= hp.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

print(-ans)

Submission status: Accepted

Solution code:
def slove():
    import sys, heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    heapq.heapify(ab)
    s_q = []
    heapq.heapify(s_q)
    r = 0
    for d in range(1, m + 1):
        while True:
            if len(ab) != 0:
                p = heapq.heappop(ab)
                if p[0] <= d:
                    heapq.heappush(s_q, -p[1])
                else:
                    heapq.heappush(ab, p)
                    break
            else:
                break
        if len(s_q) != 0:
            mr = -heapq.heappop(s_q)
            r += mr
        d -= 1
    print(r)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    job_list = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        job_list[a].append(-b)

    pool = []
    ans = 0
    for i in range(1, M+1):
        for reward in job_list[i]:
            heappush(pool, reward)
        if 0 < len(pool):
            ans -= heappop(pool)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

ab.sort()
ans = 0
hq = []
idx = 0
for i in range(1, m+1):
    for j in range(idx, n):
        if ab[j][0] == i:
            heappush(hq, (-ab[j][1], ab[j][0]))
            idx += 1
        else:
            break
    if len(hq) != 0:
        ans -= heappop(hq)[0]
    
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
reward = [[] for _ in range(M)]
for i in range(N):
  A, B = map(int, input().split())
  if A <= M:
    reward[A - 1].append(B)
q = []
ans = 0
for day in range(M):
  for r in reward[day]:
    heapq.heappush(q, -r)
  if len(q) > 0:
    ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(N)]
l = sorted(l,reverse=True)
heap = []
ans = 0
for i in range(1,M+1):
        while l and l[-1][0] == i:
            heapq.heappush(heap, -(l.pop()[1]))
        if heap :
            ans -= (heapq.heappop(heap))
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(N)]
l = sorted(l,reverse=True)
heap = []
ans = 0
for i in range(1,M+1):
        while l and l[-1][0] == i:
            heapq.heappush(heap, (l.pop()[1]*(-1)))
        if heap :
            ans -= (heapq.heappop(heap))
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())

x = []
y = []

for i in range(n):
  day, salary = map(int, input().split())
  heapq.heappush(x, (-day,-salary))
  
while x:
  d, s = heapq.heappop(x)
  r = m-len(y)
  if r >= -d:
    heapq.heappush(y, -s)
  else:
    heapq.heappush(y, -s)
    heapq.heappop(y)

print(sum(y))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def solve():
    N, M = map(int , input().split())
    arbeit_A_B = list(list(map(int , input().split())) for _ in range(N))
    arbeit_A_B = sorted(arbeit_A_B, key=lambda x: (x[0], -x[1]))
    # print(arbeit_A_B)
    day = 1
    result = 0
    index_arbeit = 0
    heap_q = []
    while day <= M:
        while index_arbeit < N:
            A,B = arbeit_A_B[index_arbeit]
            if A <= day:
                heappush(heap_q, (-1)*B)
            else: break
            index_arbeit += 1
            
        if heap_q:
            result -= heappop(heap_q)
        day += 1
            
    print(result)
    
solve()

Submission status: Accepted

Solution code:
import heapq
N, M = map(int,input().split())
reward = [[] for _ in range(M)]
for i in range(N):
  A,B = map(int,input().split())
  if A <= M:
    reward[A-1].append(B)
q = []
ans = 0
for day in range(M):
  for r in reward[day]:
    heapq.heappush(q,-r)
  if len(q) >0:
    ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
job = []

for i in range(N):
  a, b = map(int, input().split())
  job += [(a,b)]
job.sort(key=lambda x:x[0])
ls = []
ans = 0
j = 0
a = -1
for i in range(1,M+1):
  while a<=i and j<len(job):
    a, b = job[j]
    if a>i:
      break
    heappush(ls, -b)
    j += 1
  if ls:
    x = (-1)*heappop(ls)
#    print(x, i)
    ans += 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())
    if a > m:
        continue
    ab.append((a, b))
ab = sorted(ab, key=lambda a: a[0])
q = []
day = 0
index = 0
total = 0
while day <= m:
    while index < len(ab) and day >= ab[index][0]:
        heapq.heappush(q, - ab[index][1])
        index += 1
    if len(q) > 0:
        total += - q[0]
        heapq.heappop(q)
    day += 1
print(total)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
works=[[] for i in range(m+1)]
for i in range(n):
    day,pay=map(int,input().split())
    try:
        works[day].append(pay)
    except IndexError:
        pass
#print(works)

heapls=[]
day=1
ans=0

for i in range(m):
    day=i+1
    for j in works[day]:
        heapq.heappush(heapls,-j)
    if heapls!=[]:
        tmp=heapq.heappop(heapls)
        ans=ans+tmp
print(-ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
can = []
for _ in range(n):
  can.append(list(map(int,input().split())))
can.sort()
pool = []
import heapq
here = 0
ans = 0
for i in range(1,m+1):
  while can[here][0] == i:
    heapq.heappush(pool,-can[here][1])
    here += 1
    if here == n:
      here -= 1
      break
  if pool != []:
    ans += heapq.heappop(pool)
print(-ans)

Submission status: Accepted

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


import heapq as hq 
ans = 0
stack = []
for i in range(m+1):
    for j in pay[i]:
        hq.heappush(stack, -j)
    ans -= hq.heappop(stack) if stack else 0

print(ans)

Submission status: Accepted

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


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

m_list = [[] for _ in range(m+1)]

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

    if a <= m:
        m_list[a].append(b)


all_r = 0
hq = []

for i in range(1, m+1):
    for v in m_list[i]:
        heappush(hq, -1*v)

    if len(hq) != 0:
        max_v = -1 * heappop(hq)
        all_r += max_v

print(all_r)

Submission status: Accepted

Solution code:

from heapq import *
n, m = map(int, input().split())

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

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

Submission status: Accepted

Solution code:
from queue import PriorityQueue


def main():
    N, M = map(int, input().split(' '))
    jobs = [[] for _ in range(M + 1)]
    for i in [input() for i in range(N)]:
        A, B = map(int, i.split(' '))
        if A > M:
            continue
        jobs[A].append(B)

    pq = PriorityQueue()
    reward = 0

    for sameJobs in jobs:
        for job in sameJobs:
            pq.put(-job)
        if not pq.empty():
            reward += -(pq.get())

    print(reward)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from queue import PriorityQueue
 
 
def main():
    N, M = map(int, input().split(' '))
    jobs = [[] for _ in range(M + 1)]
    for i in [input() for i in range(N)]:
        A, B = map(int, i.split(' '))
        if A > M:
            continue
        jobs[A].append(B)
 
    pq = PriorityQueue()
    reward = 0
 
    for sameJobs in jobs:
        for job in sameJobs:
            pq.put(-job)
        if not pq.empty():
            reward += -(pq.get())
 
    print(reward)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [ list(map(int,input().split())) for i in range(n) ]
# print(ab)
ab.sort()
# print(ab)
import heapq
heap = []
ans = 0
i = 0
for day in reversed(range(m)):
    while i<n and ab[i][0]==(m-day):
        heapq.heappush(heap,-ab[i][1])
        i += 1
    if len(heap) > 0:
        ans += -heapq.heappop(heap)
    # print(day,i,ans,heap)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

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

q = []
for day in range(M+1):
  for v in tasks[day]:
    if len(q) < day+1:
      heappush(q, v)
    else:
      heappushpop(q,v)
print(sum(q))

Submission status: Accepted

Solution code:
import heapq

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

A = [[] for _ in range(M)]
Q = []

for _ in range(N):
	day, money = map(int, input().split())
	if day <= M:
		A[day - 1].append(money)

ans = 0

for i in range(0, M):
	for money in A[i]:
		heapq.heappush(Q, -money)
	# print(Q)
	if Q:
		ans += heapq.heappop(Q)
		
print(-ans)

Submission status: Accepted

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

n, m = map(int, input().split())
ABList = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a-1>m-1:
        continue
    ABList[a-1].append(-b) # because of min heap

ans = 0
heap = []
for i in range(m):
    for j in ABList[i]:
        heapq.heappush(heap, j)
    if len(heap)>0:
        B = heapq.heappop(heap)
        ans += -B       

print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = list(map(lambda x: int(x), input().split()))

jobs = {}
for i in range(n):
    a,b = list(map(lambda x: int(x), input().split()))
    if a in jobs.keys():
        jobs[a].append(b)
    else:
        jobs[a] = [b]

# 貪欲解法
# 最終日から決める
ans = 0
day = m

possible_job = []
# heapqでjobを管理すれば現時点で最大の給与を得ることのできる仕事を容易に取り出せる
for i in range(m+1):
    if i in jobs.keys():
        for x in jobs[i]:
            heapq.heappush(possible_job, -1 * x)
    if len(possible_job)>0:
        day_work = heapq.heappop(possible_job)
        ans += -1 * day_work
    
print (ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
x={}
for i in range(M+1):
    x[i]=[]
for i in range(N):
    a,b=map(int,input().split())
    if a>M:
        continue
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    for n in x[i]:
        heapq.heappush(y,n)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
n, m = map(int, input().split())
q = [0]
heapq.heapify(q)
to = [[] for _ in range(m)]
count = 0
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    to[a-1].append(b)
for i in range(m):
    for j in to[i]:
        heapq.heappush(q, -j)
    if len(q) != 0:
        count += heapq.heappop(q) * -1
print(count)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

cand = defaultdict(list)
for a, b in X:
    cand[a].append(b)

pq = []
ans = 0
for i in range(1, M + 1):
    for c in cand[i]:
        heappush(pq, -c)
    if pq:
        ans -= heappop(pq)
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())

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

heap = [0] * M
ans = 0
for i in range(1, M+1):
    N = len(Data)
    for j in range(N-1, -1, -1):
        if Data[j][0] > i:
            break
        if (Data[j][0] <= i):
            heappush(heap, -(Data.pop(j)[1]))

    ans += -(heappop(heap))

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int,input().split())
reward = [[] for _ in range(M)]
for i in range(N):
  A,B = map(int,input().split())
  if A <= M:
    reward[A-1].append(B)
q = []
ans = 0
for day in range(M):
  for r in reward[day]:
    heapq.heappush(q,-r)
  if len(q) >0:
    ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
can = []
for i in range(n):
  a,b = map(int,input().split())
  can.append([a,-b])
can.sort()
#print(can)
here = 0
import heapq
pool = []
ans = 0
for i in range(1,m+1):
  while here < n:
    if can[here][0] == i:
      heapq.heappush(pool,can[here][1])
      here += 1
    else:
      break
  if pool != []:
    ans -= heapq.heappop(pool)
print(ans)