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:
# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
# 日数別に報酬の値を格納
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

que = []
ans = 0
# 制約の厳しい後半から確認していく
for i in range(M-1, -1, -1):
    a = M-i
    # 残日数aで使えるようになるタスクを追加
    for b in days[a]:
        heappush(que, (-b, a))
    # キューに中身があったら最大のものを取得
    if len(que):
        b, a = heappop(que)
        ans += -b
print(ans)

Submission status: Accepted

Solution code:
#input = raw_input
#import numpy as np

from heapq import heappush, heappop

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)

Submission status: Accepted

Solution code:
import heapq

N, M = [int(v) for v in input().split()]
items = [[] for _ in range(M)]
for i in range(N):
    a, b = (int(v) for v in input().split())
    if M - a >= 0:
        items[M - a].append(b)
q = []
res = 0
for i in range(M - 1, -1, -1):
    for v in items[i]:
        heapq.heappush(q, -v)
    if q:
        res += heapq.heappop(q)
print(-res)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    print(max(a+b,a-b,a*b))
    return

#B
def B():
    k,x = LI()
    ans = []
    for i in range(x-k+1,x+k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    def f(s):
        res = [0]*m
        for i in s:
            res[alp.index(i)] += 1
        return res
    alp = list("abcdefghijklmnopqrstuvwxyz")
    m = len(alp)
    n = I()
    s = [input() for i in range(n)]
    d = defaultdict(lambda : 0)
    for i in s:
        d[tuple(f(i))] += 1
    ans = 0
    for i in d.values():
        ans += (i*(i-1))//2
    print(ans)
    return

#D
def D():
    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:x[0])
    ans = 0
    f = [1]*n
    j = 0
    q = []
    for i in range(m)[::-1]:
        while j < n and m-g[j][0] >= i:
            a,b = g[j]
            heappush(q,(-b,a))
            j += 1
        if q:
            x,a = heappop(q)
            if i+a <= m:
                ans -= x
    print(ans)
    return

def D_():
    def add(i):
        while i <= m+1:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    g = LIR(n)
    g.sort(key = lambda x:-x[1])
    bit = [0]*(m+2)
    par = [i for i in range(m+2)]
    rank = [0]*(m+2)
    ans = 0
    for a,b in g:
        i = m-a+1
        if i <= 0:
            continue
        if sum(i) < i:
            ans += b
            if sum(i-1) == sum(i):
                l = i
                r = l+1
            else:
                l = 1
                r = i+1
                while r-l > 1:
                    mid = (l+r)//2
                    if root(mid) == root(i):
                        r = mid
                    else:
                        l = mid
            unite(l,r)
            add(l)
    print(ans)
    return

#E
def E():
    def dfs(x,f):
        for y,w in v[x]:
            if f[y]:
                if dp[y] < dp[x]+w:
                    f[y] = 0
                    dp[y] = dp[x]+w
                    dfs(y,f)
                    f[y] = 1
            else:
                if dp[y] < dp[x]+w:
                    dp[y] = float("inf")
                    dfs(y,f)
    n,m,p = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c-p))
    f = [1]*n
    dp = [-float("inf")]*n
    dp[0] = 0
    f[0] = 0
    dfs(0,f)
    ans = dp[n-1]
    if ans == float("inf") or ans == -float("inf"):
        print(-1)
    elif ans < 0:
        print(0)
    else:
        print(ans)
    return

#F
def F():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%p

    p = I()
    a = LI()
    fact = [1]
    for i in range(p-1):
        fact.append(fact[-1]*(i+1)%p)
    inv = [1]*p
    inv[p-1] = pow(fact[p-1],p-2,p)
    for i in range(1,p)[::-1]:
        inv[i-1] = inv[i]*i%p
    b = [0]*p
    for i in range(p):
        ai = a[i]
        if ai:
            b[0] += ai
            k = 1
            for j in range(p):
                c = ai*comb(p-1,j)*k%p
                k *= i
                if k >= p:
                    k %= p
                if j%2:
                    b[p-1-j] += c
                else:
                    b[p-1-j] -= c
                b[p-1-j] %= p
    print(*b)
    return

#Solve
if __name__ == "__main__":
    D_()

Submission status: Accepted

Solution code:
import heapq
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
d=[[0]for i in range(b)]
sum=0
for i,j in c:
  if i<=b:
    d[i-1].append(j)
e=[]

for i in d:
  for j in i:
    heapq.heappush(e,-j)
  sum-=heapq.heappop(e)
      
    
  
print(sum)

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        elif q and q[0]<b:heappushpop(q,b)
print(sum(q))

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
h = []
for d in range(M-1,-1,-1):
    for b in job[d]:
        heapq.heappush(h, (-b,b))
    if len(h) > 0:
        ans += heapq.heappop(h)[1]

print ans

Submission status: Accepted

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

W = []  # 取り組める仕事のリスト
for _ in range(N):
    W.append(tuple(map(int, input().split())))
W = sorted(W, key=lambda x: (x[0], -x[1]))


a = []
heapq.heapify(a)  # リストaのheap化

ans = 0
c = 0
for day in range(1, M+1):
    day_c = 0
    while c != N and W[c][0] == day:
        if day_c <= M-day:
            x = W[c][1]
            heapq.heappush(a, -x)  # heap化されたリストaに要素xを追加
            day_c += 1
        c += 1
    if len(a) >= 1:
        ans += -heapq.heappop(a)  # heap化されたリストaから最小値を削除＆その最小値を出力

print(ans)

Submission status: Accepted

Solution code:
# from collections import defaultdict
import heapq
N, M = map(int, input().split())

W = []
for _ in range(N):
    W.append(tuple(map(int, input().split())))
W = sorted(W, key=lambda x: (x[0], -x[1]))


a = []
heapq.heapify(a)  # リストaのheap化

ans = 0
c = 0
for day in range(1, M+1):
    day_c = 0
    while c != N and W[c][0] == day:
        if day_c <= M-day:
            x = W[c][1]
            heapq.heappush(a, -x)  # heap化されたリストaに要素xを追加
            day_c += 1
        c += 1
    if len(a) >= 1:
        ans += -heapq.heappop(a)  # heap化されたリストaから最小値を削除＆その最小値を出力

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,key=lambda x:x[0])
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = {i + 1: [] for i in range(10 ** 5)}
for _ in range(N):
    A, B = map(int, input().split())
    AB[A].append(B)

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

print(ans)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for a in t[::2]:a>M or v[a-1].append(t[i+1]);i+=2
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Accepted

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
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:
import heapq

N, M = map(int, input().split())
AB_list = []
[heapq.heappush(AB_list, list(map(int, input().split()))) for _ in range(N)]
ans = 0
kouho = []

for day in range(1, M + 1):
    if len(AB_list) != 0:
        while AB_list[0][0] <= day:           
            heapq.heappush(kouho, heapq.heappop(AB_list)[1]*(-1))
            if len(AB_list) == 0:
                break
    if len(kouho) != 0:
        ans += heapq.heappop(kouho)

print(ans * (-1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        c[a - 1].append(b)
r=0
h = []
for l in c:
    for x in l:
        heappush(h, -x)
    if h:
        r -= heappop(h) 
print(r)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for _ in'_'*N:M<t[i]or v[t[i]-1].append(t[i+1]);i+=2
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


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

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    if M - a < 0:
        continue
    # 入れられる？
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        # どこに入れよう？
        ok = -1
        ng = M - a
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if mid - bit.sum(mid) + 1 != cap:
                ok = mid
            else:
                ng = mid
        bit.add(ok + 1, 1)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        c[m - a].append(b)
r=0
h = []
for l in reversed(c):
    for x in l:
        heappush(h, -x)
    if h:
        r -= heappop(h) 
print(r)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
z=i=0
for _ in'_'*N:M<t[i]or v[t[i]-1].append(t[i+1]);i+=2
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Submission status: Accepted

Solution code:
import heapq
maxB = 10 ** 1

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

AB.sort(key=lambda x: x[1])

ans, heap, idx, lAB = 0, [], 0, len(AB)
for i in range(M):
    while idx < lAB and AB[idx][1] <= i + 1:
        heapq.heappush(heap, AB[idx])
        idx += 1
    if len(heap) > 0:
        ans += maxB - heapq.heappop(heap)[0]

print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):M<t[2*i]or v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):
	if t[2*i]<=M:v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

for i in range(N):
  ab = list(map(int, input().split()))
  #Ai > M の仕事はいらない
  if ab[0] <= M:
    jobs[ab[0] - 1].append(ab[1])

#最終日はAi=1の仕事のみ選べる。その前の日はAi<=2, ...
#終わりから考えればよさそう
hq = []
ans = 0
for i in range(M):
  for b in jobs[i]:
    heappush(hq, -1 * b)
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from queue import PriorityQueue
n, m = map(int, input().split())
jobs = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[m - a].append(b)
pq = PriorityQueue()
ans = 0
for i in range(m)[::-1]:
    for b in jobs[i]:
        pq.put(-b)
    if not pq.empty():
        ans += -pq.get()
print(ans)

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] <= i:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from heapq import heappop
from heapq import heappush
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


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) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = []
    ti = 0
    for t in range(m + 1):
        # from (m days after) to today
        while ti < n and ab_s[ti][0] == t:
            a, b = ab_s[ti]
            ti += 1
            heappush(tasks, -b)
        if tasks:
            # do task
            ans -= heappop(tasks)

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:
		v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:
		heappush(q,-j)
	b=0
	if len(q):
		b=heappop(q)
	z-=b
print(z)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()
    AB = []
    for _ in range(N):
        AB.append(l_inpl())


    AB.sort(reverse=True)

    q = []
    ans = 0

    for remain_day in range(1, M+1):
        while True:
            if len(AB) > 0 and AB[-1][0] <= remain_day:
                _, b = AB.pop()
                heappush(q, -b)
            else:
                break
        if q:
            ans += -heappop(q)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
A_B = [[0] for i in range(M)]
for i in range(N):
  A, B = map(int,input().split())
  if A <= M:
    A_B[A-1].append(-B)
  
import heapq
q = []
ans = 0
heapq.heapify(q)

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

Submission status: Accepted

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from heapq import heappop
from heapq import heappush
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


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) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = []
    for t in range(m + 1):
        # from (m days after) to today
        while ab_s and ab_s[0][0] == t:
            a, b = ab_s.pop(0)
            heappush(tasks, -b)
        if tasks:
            # do task
            ans -= heappop(tasks)

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
A = dict()

for _ in range(N):
  a, b = map(int, input().split())
  if a in A:
    A[a].append(b)
  else:
    A[a] = [b]

h = []
reward = 0

for day in range(1, M+1):
  bb = A.get(day)
  if bb:
    for x in bb:
      heapq.heappush(h, -x)
  if h:
    reward += heapq.heappop(h)
    
print(-reward)

Submission status: Accepted

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

AB.sort(key=lambda ab: (ab[0], -ab[1]))

heap = []
abi = 0
ans = 0
for i in range(1, M + 1):
    # i までのやつは入れられる
    while abi < N and AB[abi][0] <= i:
        a, b = AB[abi]
        heapq.heappush(heap, (-b, a))
        abi += 1
    if heap:
        b, a = heapq.heappop(heap)
        ans += -b
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, work: "List[List[int]]"):
    wq = deque(work)
    paytree = []
    ans = 0

    for day in range(M + 1):
        while len(wq) > 0 and wq[0][0] <= day:
            heapq.heappush(paytree, wq.popleft()[1] * (-1))
        if len(paytree) > 0:
            ans -= heapq.heappop(paytree)

    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    work = [] # type: "List[List[int]]"
    for _ in range(N):
        work.append([int(next(tokens)), int(next(tokens))])
    solve(N, M, sorted(work))

if __name__ == '__main__':
    main()