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:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N ]

AB += [[10*M,0]]

AB.sort(reverse=True)

from heapq import *

q = []
ans = 0

for i in range(1,M+1):
    a,b = AB[-1]
    while a<=i:
        a,b = AB.pop()
        heappush(q,-b)
        a,b = AB[-1]
    if len(q)>0:
        ans += -heappop(q)
print(ans)

Submission status: Accepted

Solution code:
# pdf
from heapq import *

n, m = map(int, input().split())
hp = []
for _ in range(n):
    a, b = map(int, input().split())
    heappush(hp, [a, b])
ans = 0
mx = b
ch = []
a, b = heappop(hp)
flag = 1
for i in range(1, m + 1):
    while a <= i:
        if flag:
            heappush(ch, -b)
            flag = 0
        if not hp:break
        a, b = heappop(hp)
        flag = 1
    if ch:
        ans -= heappop(ch)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

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

earn = 0
q = []

for m in range(1, M + 1):

    for job in AB[m]:
        heapq.heappush(q, job)

    if q != []:
        earn += heapq.heappop(q)

print(0-earn)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [(a, b) for _ in range(N) for a, b in [map(int, input().split())] if M - a >= 0]

AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1

print(sum(x))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [(a, b) for _ in range(N) for a, b in [map(int, input().split())] if M - a >= 0]

AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
  n, m = map(int, input().split())
  ab = []
  for _ in range(n):
    ab.append(tuple(map(int, input().split())))
  ab = list(sorted(ab))
  abi = 0
  hb = []
  ans = 0
  for i in range(1, m+1):
    while abi<n and ab[abi][0] <= i:
      heappush(hb, -ab[abi][1])
      abi += 1
    if len(hb) == 0:
      continue
    b = heappop(hb)
    ans += -b
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import queue

N, M = map(int, input().split())
AB = [[] for _ in range(M + 1)]

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

earn = 0
q = queue.PriorityQueue()

for m in range(1, M + 1):

    for job in AB[m]:
        q.put(job)

    if not q.empty():
        earn += q.get()

print(0-earn)

Submission status: Accepted

Solution code:
import numpy as np
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab) * [-1, 1] + [m, 0]

at = [[] for _ in range(m)]
for a, b in ab:
    if a >= 0:
        at[a].append(b)

ans = 0
now = []
for value in at[::-1][:m]:
    for v in value:
        heapq.heappush(now, -v)
    if now:
        ans += heapq.heappop(now)
print(-ans)

Submission status: Accepted

Solution code:
from heapq import *
n, m = map(int, input().split())
pay = []
for _ in range(n):
    a, b = map(int, input().split())
    pay.append((a, b))
pay = sorted(pay, reverse=True)
q = []
ans = 0
for i in range(1, m+1):
    while pay and pay[-1][0] <= i:
        a, b = pay.pop()
        heappush(q, -b)
    if q:
        b = -heappop(q)
        ans += b
print(ans)

Submission status: Accepted

Solution code:
import sys, heapq
input=sys.stdin.readline
N,M=map(int,input().split())
L=sorted([tuple(map(int,input().split())) for _ in range(N)])
Llen=len(L)
k=0
ans=0
heap=[]
for i in range(1,M+1):
    while k<Llen:
        a,b=L[k]
        if a<=i: heapq.heappush(heap,-b)
        else: break
        k+=1
    if len(heap)>0:
        ans+=-heapq.heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
import sys
input = sys.stdin.readline

from heapq import heappush, heappushpop


def main():
    N, M = tuple(map(int, input().split()))
    T = [[] for _ in range(M + 1)]
    for _ in range(N):
        a, b = map(int, input().rstrip().split())
        if a <= M:
            T[M - a] += [b]
    q = []
    for i in range(M + 1):
        for v in T[i]:
            if len(q) <= i:
                heappush(q, v)
            else:
                heappushpop(q, v)
    print(sum(q))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
import sys
input = sys.stdin.readline

from heapq import heappush, heappushpop


def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    T = [[] for _ in range(M + 1)]
    for a, b in A:
        if a <= M:
            T[M - a] += [b]
    q = []
    for i in range(M + 1):
        for v in T[i]:
            if len(q) <= i:
                heappush(q, v)
            else:
                heappushpop(q, v)
    print(sum(q))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    for a, b in zip(*[iter(ab)]*2):
        works[a].append(-b)

    candidates, pay = [], 0
    for day in range(1, m+1):
        if day in works:
            for x in works[day]:
                heappush(candidates, x)
        if candidates:
            pay += heappop(candidates)
    print(-pay)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    for a, b in zip(ab[0::2], ab[1::2]):
        works[a].append(-b)

    candidates, pay = [], 0
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay += heappop(candidates)
    print(-pay)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    # == zip(ab[0::2], ab[1::2])
    for a, b in zip(*[iter(ab)]*2):
        # 最大値が欲しいが、heappopは最小値を取り出すので-1倍しておく
        works[a].append(-b)

    # candidates, pay = [], []
    # for day in range(1, m+1):
    #     for x in works[day]:
    #         heappush(candidates, x)
    #     if candidates:
    #         pay.append(heappop(candidates))
    # print(-sum(pay))

    # こっちの方が遅い
    candidates, pay = [], 0
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay += heappop(candidates)
    print(-pay)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    # == zip(ab[0::2], ab[1::2])
    for a, b in zip(*[iter(ab)]*2):
        # 最大値が欲しいが、heappopは最小値を取り出すので-1倍しておく
        works[a].append(-b)

    candidates, pay = [], 0
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay -= heappop(candidates)
    print(pay)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappush, heappop
    _, m, *ab = map(int, open(0).read().split())
    works = defaultdict(list)
    # == zip(ab[0::2], ab[1::2])
    for a, b in zip(*[iter(ab)]*2):
        # 最大値が欲しいが、heappopは最小値を取り出すので-1倍しておく
        works[a].append(-b)

    candidates, pay = [], []
    for day in range(1, m+1):
        for x in works[day]:
            heappush(candidates, x)
        if candidates:
            pay.append(heappop(candidates))
    print(-sum(pay))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    heappush(avb, -j)
  if avb != []:
    ans -= heappop(avb)
print(ans)

Submission status: Accepted

Solution code:
import heapq


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

score_list = [[] for i in range(M+1)]


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


ans = 0
candidates = []

for i in range(0, M+1):

    for s in score_list[i]:
        heapq.heappush(candidates, -s)
    if len(candidates) == 0:
        continue
    ans -= heapq.heappop(candidates)


print(ans)

Submission status: Accepted

Solution code:
N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
    
days_limit = M

jobs = AB[:]
from collections import defaultdict
jobs_dict = defaultdict(lambda: [])
for d, r in jobs:
    jobs_dict[d].append(r)
#print(jobs_dict)

import heapq
hq = []

ans = 0
for d in range(1, M+1):
    for r in jobs_dict[d]:
        heapq.heappush(hq,-r)
    if hq:
        ans += -1 * heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from operator import itemgetter

na = lambda: map(int, sys.stdin.readline().split())

n, m = na()
ab = [list(na()) for _ in range(n)]
ab.sort(key=itemgetter(0))

ans = 0
p = 0
h = []
for day in range(1, m+1):
  for i in range(p, len(ab)):
    if ab[i][0] <= day:
      heappush(h, -ab[i][1])
      p += 1
    else:
      break
  if h:
    ans += -heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

dic = {}
for i in range(n):
    a, b = map(int, input().split())
    if a >= m+1:
        continue
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]

ans = 0
l = []
heapq.heapify(l)
for j in range(1, m+1):
    if j in dic.keys():
        for x in dic[j]:
            heapq.heappush(l, -x)
    if l:
        ans += -l[0]
        heapq.heappop(l)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
cd = []
heapify(ab)
ans = 0
for i in range(M)[::-1]:
    while len(ab):
        a, b = heappop(ab)
        if M < a+i:
            heappush(ab, [a, b])
            break
        heappush(cd, -b)
    if len(cd):
        ans -= heappop(cd)
print(ans)

Submission status: Accepted

Solution code:
def d_summer_vacation(N, M, Works):
    from collections import defaultdict
    from heapq import heappush, heappop  # 最小値を取り出すので、リストを-1倍する
    work_dict = defaultdict(list)
    for a, b in Works:
        work_dict[a].append(-b)

    candidate, ans = [], []
    for day in range(1, M + 1):
        for x in work_dict[day]:
            heappush(candidate, x)
        if len(candidate) != 0:
            ans.append(-heappop(candidate))
    return sum(ans)

N, M = [int(i) for i in input().split()]
Works = [[int(i) for i in input().split()] for j in range(N)]
print(d_summer_vacation(N, M, Works))

Submission status: Accepted

Solution code:
class MaxHeap:
    def __init__(self):
        self.__pq = []
        self.__length = 0
    def length(self):
        return self.__length
    def push(self,item):
        self.__pq.append(item)
        self.__length += 1
        i = self.__length - 1
        while i > 0:
            p = (i-1)//2
            tmp = self.__pq[p]
            if tmp >= item:
                break
            self.__pq[p] = item
            self.__pq[i] = tmp
            i = p    
    def popMax(self):
        if self.__length == 0:
            return None
        ret = self.__pq[0]
        if self.__length == 1:
            self.__length -= 1
            return self.__pq.pop(0)
        self.__pq[0] = self.__pq.pop(self.__length-1)
        self.__length -= 1
        i = 0
        while 2*i+1 < self.__length:
            larger = 2*i+1
            if 2*i+2 < self.__length:
                if self.__pq[2*i+2] > self.__pq[larger]:
                    larger = 2*i+2
            tmp = self.__pq[larger]
            if tmp <= self.__pq[i]:
                break
            self.__pq[larger] = self.__pq[i]
            self.__pq[i] = tmp
            i = larger
        return ret
    
    def isempty(self):
        return self.__length == 0
from collections import defaultdict
N,M = map(int,input().split())
PQ = MaxHeap()
dic = defaultdict(list)
for i in range(N):
    a,b = map(int,input().split())
    dic[a].append(b)
keys = list(dic.keys())
keys.sort()
n = 1
ans = 0
i = 0
ln = len(keys)
while n <= M:
    if i < ln and keys[i] == n:
        for l in dic[keys[i]]:
            PQ.push(l)
        i  += 1
    if not PQ.isempty():
        ans += PQ.popMax()
    n += 1
print(ans)

Submission status: Accepted

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


q = [[0] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b*-1)

# print(q)

from heapq import heappop, heappush

pool = []
answer = 0
for x in reversed(q):
    for y in x:
        heappush(pool, y)
    m = heappop(pool)*-1
    answer += m
    

print(answer)

Submission status: Accepted

Solution code:
import heapq
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N)]
day_gain = [[] for _ in range(10**5 + 1)]
for a, b in AB:
    day_gain[a] += [b]
ans = 0
work = 0
H = []
for d in range(M + 1):
    for g in day_gain[d]:
        heapq.heappush(H, -g)
    if H:
        ans -= heapq.heappop(H)
print(ans)

Submission status: Accepted

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


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

ans = 0
schedule = {}


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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))

from collections import defaultdict
from heapq import heappush, heappop
dd = defaultdict(list)

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

hq = []
ret = 0
for i in range(1,m+1):
    for j in dd[i]:
        heappush(hq,-j)
    if hq:
        ret+=heappop(hq)
print(-ret)

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)

#解法
rewards = 0
heap = []
for i in range(M):
	for reward in jobs[i]:
		heapq.heappush(heap,reward)

	if len(heap)>0:
		reward = heapq.heappop(heap)
		rewards += -reward

print(rewards)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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


jobs = [[] for _ in range(m)]
for a, b in ab:
    if a <= m:
        jobs[a - 1].append(-b)

ans = 0
available = []
for job in jobs:
    for jo in job:
        heappush(available, jo)

    if available:
        ans -= heappop(available)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

jobs = []
cnts = defaultdict(int)
rets = []

for i in range(N):
    a, b = map(int, input().split())

    heapq.heappush(jobs, (a, -b))
    cnts[a] += 1


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

    cnt = cnts.get(i)

    if cnt:
        while cnt > 0:
            a, b = heapq.heappop(jobs)
            heapq.heappush(rets, b)
            cnt -= 1

    if rets:
        b = heapq.heappop(rets)
        ans -= b

print(ans)

Submission status: Accepted

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])
#print(ab)

res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    #print(nowdate)
    i=k
    while True:
        if i>=len(ab):
            k=10**10
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)
    try:
        tmp=heapq.heappop(koho)
        res+=(-tmp)
    except:
        pass

    
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getsize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: -x[1])
ans, bit, uf = 0, BIT(M), UnionFind(M+2)
for a, b in ab:
    i = M-a+1
    if 0 < i and bit.sum(i) < i:
        ans += b
        if bit.sum(i-1) == bit.sum(i):
            lb, ub = i, i+1
        else:
            lb, ub = 0, i
            while lb+1 < ub:
                mid = (lb+ub)//2
                if uf.same(mid, ub):
                    ub = mid
                else:
                    lb = mid
        bit.add(lb, 1)
        uf.unite(lb, ub)
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq

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

AB.sort(key=itemgetter(0))
q = []
idx = 0
ans = 0

for i in range(1, M+1):
    while idx < N:
        a, b = AB[idx]
        if a <= i:
            heapq.heappush(q, -b)
            idx += 1
        else:
            break
    if len(q)>0:
        b = heapq.heappop(q)
        ans -= b
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getsize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: x[0])
ab.sort(key = lambda x: -x[1])
ans = 0
# print(ab)
uf = UnionFind(M+2)
bit = BIT(M)
ub = M+1
for a, b in ab:
    # print([bit.sum(i) for i in range(1, M+1)])
    i = M-a+1
    # print(bit.sum(i), i, ub)
    if 0 < i and bit.sum(i) < i:
        ans += b
        if bit.sum(i-1) == bit.sum(i):
            bit.add(i, 1)
            uf.unite(i, i+1)
        else:
            lb, ub = 0, i
            while lb+1 < ub:
                mid = (lb+ub)//2
                if uf.same(mid, ub):
                    ub = mid
                else:
                    lb = mid
            bit.add(lb, 1)
            uf.unite(lb, ub)
# print([bit.sum(i) for i in range(1, M+1)])
# print()
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
# from itertools import permutations
# from math import pi
# from operator import itemgetter
# from operator import mul
# from operator import xor
# from os import linesep


# def isprime(n: int) -> bool:
#     if n <= 1:
#         return False
#     if n in (2, 3, 5):
#         return True
#     if n % 2 == 0:
#         return False
#     if n % 3 == 0:
#         return False
#     lst = int(n**0.5)
#     f = 5
#     while f <= lst:
#         if n % f == 0:
#             return False
#         if n % (f + 2) == 0:
#             return False
#         f += 6
#     return True


# def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
#     return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


# def strbool(boolval: int) -> str:
#     return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    n, m, *t = map(int, open(0).read().split())

    # solve here
    d = [[] for i in range(m+1)]
    for i in range(n):
        a, b = t[2*i], t[2*i+1]
        if a > m:
            continue
        d[a].append(b)

    ans = 0
    tasks = []
    for t in range(m + 1):
        # from (m days after) to today
        for tasksize in d[t]:
            heappush(tasks, -tasksize)
        if tasks:
            # do task
            ans -= heappop(tasks)

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

w = [[] for _ in range(10**5)]

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

money = 0
l = []
for i in range(m):
  for item in w[i]:
    heappush(l, item * (-1))
  if len(l) == 0:
    continue

  money += heappop(l) * (-1)

print(money)

Submission status: Accepted

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

q = []
ans = 0
for i in range(M - 1, -1, -1):
    for b in jobs[i]:
        heapq.heappush(q, -b)
    if q:
        ans += heapq.heappop(q) * (-1)
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())

    AB.append([A,B])

AB.sort()


day = 1
i = 0
lis = []
ans = 0

while day <= M:

    if i < N and AB[i][0] == day:

        heapq.heappush(lis,-1 * AB[i][1])
        i += 1

    else:

        day += 1

        if len(lis) > 0:
            ans -= heapq.heappop(lis)

print (ans)

Submission status: Accepted

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from heapq import heappop, heappush
from collections import defaultdict
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, m = map(int, input().split())

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

    s = 0
    c = []
    for i in range(m):
        for j in d[i + 1]:
            heappush(c, -j)
        if c:
            s += -heappop(c)

    print(s)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()