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

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

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値とindex(同値があった場合は一番左)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        # 1段目(最下段)の初期化
        for i in range(n2):
            self.index[i+n2] = i
        # 2段目以降の初期化
        for i in range(n2-1, -1, -1):
            # 全部左の子の値に更新
            self.index[i] = self.index[i*2]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[left]:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            else:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        # 範囲外なら初期値
        if r <= a or b <= l:
            return (self.init, -1)
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return (self.tree[k], self.index[k])
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        left = self._get_val(a, b, k << 1, l, m)
        right = self._get_val(a, b, (k << 1) + 1, m, r)
        if self.func(left[0], right[0]) == left[0]:
            return left
        else:
            return right

N, M = MAP()
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

sti = SegTreeIndex(10**5+1, max, -INF)
for i in range(10**5+1):
    days[i].sort()
    if len(days[i]):
        sti.update(i, days[i][-1])

ans = 0
for i in range(M-1, -1, -1):
    val, idx = sti.get_val(0, M-i+1)
    if val == -INF:
        continue
    ans += val
    days[idx].pop(-1)
    if len(days[idx]):
        sti.update(idx, days[idx][-1])
    else:
        sti.update(idx, -INF)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, M, AB):
    ans = 0
    cand = []
    AB.sort(key=lambda x: x[0], reverse=True)
    for i in range(1, M+1):
        while AB and AB[-1][0] <= i:
            _, b = AB.pop()
            heapq.heappush(cand, -b)
        if cand:
            ans -= heapq.heappop(cand)
    return ans 

def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(10**9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

N, M = LIST()

A = [[] for _ in range(10**4+1)]
for _ in range(N):
    a, b = LIST()
    if a <= M:
        A[b].append(a)

for a in A:
    a.sort(reverse=True)

off = list(range(1, M+1))
ans = 0

i = 10**4
while i > 0:
    for a in A[i]:
        attempt = bisect.bisect_left(off, a)

        if attempt < len(off):
            off.pop(attempt)
            ans += i

    if off == []:
        break;
    else:
        i -= 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq

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

task.sort()

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
AB.sort(key=lambda x:x[0])
index = 0
Works = []
ans = 0

for d in range(1,M+1):#d日後までの支払いのうち一番高いやつ
    while 1:
        if index>=N:break
        if AB[index][0]<=d:
            heapq.heappush(Works,-AB[index][1])
            index += 1
        else:
            break
    if Works:
        ans -= heapq.heappop(Works)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ABS = sorted(AB, key=lambda x: -x[1])
ABSS = sorted(ABS, key=lambda x: x[0])
# print(ABS)
# print(ABSS)

heap = []
ans = 0
chkpos = 0

for i in range(1, M + 1):
  if chkpos < N:
    while ABSS[chkpos][0] <= i:
  #    print(chkpos, len(ABSS))
      heapq.heappush(heap, -1 * ABSS[chkpos][1])
      chkpos += 1
      if chkpos >= N:
        break
  #  print(heap)
    if len(heap) > 0:
      ans -= heapq.heappop(heap)
  else:
    ans -= heapq.heappop(heap)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

heapq.heapify(ABs)
availables = []
ans = 0
for i in range(1, M + 1):
    while ABs:
        a = heapq.heappop(ABs)
        if a[0] == i:
            heapq.heappush(availables, -a[1])
        else:
            heapq.heappush(ABs, a)
            break
    if availables:
        ans -= heapq.heappop(availables)

print(ans)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT

## take jobs 1,2,3,...
## d[i]
##last day useless
##
##sort by reward and then by days
import heapq 
days=[[] for i in range(10**5+1)]
N,M=list(map(int,input().strip().split(' ')))
for _ in range(N):
    a,b=list(map(int,input().strip().split(' ')))
    days[a]+=[b]

ans=0
possible=[]
for i in range(M+1):
    for x in days[i]:
        heapq.heappush(possible,-x)
    if len(possible)==0:
        continue
    MAX_val=heapq.heappop(possible)
    ans+=-MAX_val
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = [int(i) for i in input().split()]
d = [[] for i in range(m+1)]
for i in range(n):
    a, b = [int(_) for _ in input().split()]
    if a <= m:
        d[a].append(b)
ans = 0
cand = []
for i in range(1, m+1):
    for dd in d[i]:
        heapq.heappush(cand, -dd)
    if len(cand) > 0:
        ans += -heapq.heappop(cand)
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import bisect
import heapq
import sys
input = sys.stdin.readline

def main():
    N,M = [int(x) for x in input().split()]
    work = {}
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        if(a in work):
            work[a].append(-b)
        else:
            work[a] = [-b]

    cand = []
    heapq.heapify(cand)
    cnt = 0
    for i in range(1,M+1):
        if(i in work):
            for x in work[i]:
                heapq.heappush(cand,x)
        if(len(cand)==0):
            continue
        x = -heapq.heappop(cand)
        cnt += x

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  l.append([a,b])
l.sort()
l.append([0,0])
ans=0
k=[]
j=0
for i in range(1,m+1):
  while j<=n and l[j][0]<=i:
    heapq.heappush(k, -1*l[j][1])
    j+=1
  if len(k)!=0:
  	ans+=-1*k[0]
  	heapq.heappop(k)
print(ans)

Submission status: Accepted

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

import sys

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

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値とindex(同値があった場合は一番右)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        # 1段目(最下段)の初期化
        for i in range(n2):
            self.index[i+n2] = i
        # 2段目以降の初期化
        for i in range(n2-1, -1, -1):
            # 全部右の子の値に更新
            self.index[i] = self.index[i*2+1]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[right]:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            else:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        # 範囲外なら初期値
        if r <= a or b <= l:
            return (self.init, -1)
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return (self.tree[k], self.index[k])
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        left = self._get_val(a, b, k << 1, l, m)
        right = self._get_val(a, b, (k << 1) + 1, m, r)
        if self.func(left[0], right[0]) == right[0]:
            return right
        else:
            return left

N, M = MAP()
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

sti = SegTreeIndex(10**5+1, max, -INF)
for i in range(10**5+1):
    days[i].sort()
    if len(days[i]):
        sti.update(i, days[i][-1])

ans = 0
for i in range(M-1, -1, -1):
    val, idx = sti.get_val(0, M-i+1)
    if val == -INF:
        continue
    ans += val
    days[idx].pop(-1)
    if len(days[idx]):
        sti.update(idx, days[idx][-1])
    else:
        sti.update(idx, -INF)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

lst.sort(key=lambda x:(x[1]), reverse=True)
lst.sort(key=lambda x:(x[0]), reverse=False)

ans = 0
ind = 0
kouho = []
for i in range(1, m+1):
    tugi = True
    while tugi:
        if ind >= n:
            break
        if lst[ind][0] == i:
            heapq.heappush(kouho, -lst[ind][1])
            ind += 1
        else:
            tugi = False
    try:
        ans += heapq.heappop(kouho) * (-1)
    except:
        IndexError

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

D = {}
for i in range(N) :
    k,v = L[i]
    if k not in D :
        D[k] = [v]
    else :
        D[k].append(v)

class Heapq :
    def __init__(self, arr, desc=False) :
        if desc :
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
    
    def pop(self) :
        return heapq.heappop(self.hq) * self.sign
    
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
 
    def size(self):
        return len(self.hq)

q = Heapq([], True)
ans = 0
for k in range(1, M+1) :
    if k in D :
        for v in D[k] :
            q.push(v)
    if q.size() :
        ans += q.pop()
print(ans)

Submission status: Accepted

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

A = [[] for i in range(M)]

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

count = 0
for a in A:
    for b in a:
        heappush(heap, -b)
    if len(heap) == 0:
        continue
    num = heappop(heap)
    count += num

print(-count)

Submission status: Accepted

Solution code:
import heapq

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import heapq

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(-bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref: heapq.heapify(ref)
    while ref: heapq.heappush(cur,heapq.heappop(ref))
    #
    if not cur: continue
    tot+= heapq.heappop(cur)
#
print( -tot )

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
H = [[] for _ in range(M)]
for _ in range(N):
  A, B = map(int, input().split())
  if A <= M:
    H[A - 1].append(-B)
Q = []
c = 0
for d in range(M):
  for b in H[d]:
    heapq.heappush(Q, b)
  if Q:
    c -= heapq.heappop(Q)
print(c)

Submission status: Accepted

Solution code:
import heapq

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

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

#print(AB)

ans = 0
p = 0
h = []
heapq.heapify(h)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
H = [[] for _ in range(M)]
for _ in range(N):
  A, B = map(int, input().split())
  if A <= M:
    H[A - 1].append(-B)
Q = []
cnt = 0
for d in range(M):
  for b in H[d]:
    heapq.heappush(Q, b)
  if Q:
    cnt -= heapq.heappop(Q)
print(cnt)

Submission status: Accepted

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

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

ans = 0
q = []
for j in range(1, M+1):
    for k in days[j]:
        heapq.heappush(q, -k)

    if q:
        tmp = heapq.heappop(q)
        ans -= tmp
    
print(ans)

Submission status: Accepted

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

q = []  # 締切の小さい順に並べ替え
q1 = [] # するタスクリスト

for i in range(N):
    day, reward = map(int, input().split())
    heapq.heappush(q,(-day,-reward))
# delayは大きい順、rewardは大きい順で並べておく
while q:
    d, r = heapq.heappop(q)
    rest = M - len(q1)
    if rest >= -d:
        # できるリストに追加
        heapq.heappush(q1,-r)
    else:
        # 一番報酬が少ない奴を入れ替え
        heapq.heappush(q1,-r)
        heapq.heappop(q1)
        
print(sum(q1))

Submission status: Accepted

Solution code:
import heapq

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

daylist = [[] for _ in range(10**5)]
for a, b in w:
    daylist[a-1].append(b)

q = []
for i in range(M):
    for b in daylist[i]:
        heapq.heappush(q, -b)
    if q:
        ans += -heapq.heappop(q)
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+5)]
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:
import heapq as pq

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

day_to_reward = {}
for a, b in AB:
    if day_to_reward.get(a) is None:
        day_to_reward[a] = [b]
    else:
        day_to_reward[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    for reward in day_to_reward.get(i, []):
        pq.heappush(candidate, - reward)
    if candidate:
        ans += - pq.heappop(candidate)

print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
def main():
    n,m = map(int,input().split(' '))
    w = [list(map(int,input().split(' '))) for i in range(n)]
    w=sorted(w,reverse=True)
    ans = 0
    l = []
    tmp = 0
    for i in range(1,m+1):
        while w and w[-1][0] <= i:
            hq.heappush(l,-w.pop()[1])
        if l:
            ans -=hq.heappop(l)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

heap = []
total = 0
for day in range(1, M + 1):
    for reward in rewards[day]:
        heapq.heappush(heap, -reward)

    if len(heap) > 0:
        max_reward = heapq.heappop(heap)
        total += -max_reward

print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC137 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))
ans = 0
h = []
j = 0
for i in range(m)[::-1]:
    while j < n and m - ab[j][0] >= i:
        a,b = ab[j]
        heappush(h,(-b,a))
        j += 1
    if h:
        x,a = heappop(h)
        ans -= x
print(ans)

Submission status: Accepted

Solution code:
import heapq as pq

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

day_to_reward = {}
for a, b in AB:
    if day_to_reward.get(a) is None:
        day_to_reward[a] = [b]
    else:
        day_to_reward[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    for reward in day_to_reward.get(i, []):
        pq.heappush(candidate, - reward)
    if candidate:
        work_reward = - pq.heappop(candidate)
        ans += work_reward


print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
import heapq

def solve(n, m, a):
  #pprint(a)
  cands = []
  ans = 0
  for i in xrange(m+1):
    # print i
    if i in a and len(a[i]) > 0:
      for v in a[i]:
        heapq.heappush(cands, v)

    # pprint(cands)
    if len(cands) > 0:
      w = heapq.heappop(cands) 
      # pprint(-1 * w)
      ans += -1 * w

  print(ans)


if __name__ == '__main__':

  n, m = map(int, sys.stdin.readline().strip().split(" "))
  # print n, m
  a = {}
  # pprint(a)
  for _ in xrange(n):
    a_i, b_i = map(int, sys.stdin.readline().strip().split(" "))
    # print a_i, b_i
    
    if a_i not in a:
      a[a_i] = []
    a[a_i].append(-1 * b_i)
  solve(n, m, a)

Submission status: Accepted

Solution code:
"""
AtCoder
    :author: vierbein
"""
from __future__ import absolute_import, division, print_function

# import itertools as it
# import collections
import sys
from heapq import *

def pp(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


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

idx = 0
h = []
res = 0

for rest in range(1, M + 1):
    while idx < N:
        a, b = pairs[idx]
        # pp(a, b, h)
        if a <= rest:
            heappush(h, -b)
            idx += 1
        else:
            break
    try:
        res += -heappop(h)
    except IndexError:
        pass

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = [None]*N
for i in range(N):
    AB[i] = inpl()
AB.sort(key=lambda x: -x[0])
q = []
ans = 0
for m in range(1,M+1):
    while len(AB) > 0 and AB[-1][0] <= m:
        ab = AB.pop()
        heapq.heappush(q,-ab[1])
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import heapq
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(1),reverse = True)
x = sorted(x,key=itemgetter(0))

work = []
j = 0
answer = 0
for i in range(1,m+1,1):
    while j < n and x[j][0] == i:
        heapq.heappush(work,-x[j][1])
#        print(work)
        j += 1
    if work:
        answer -= heapq.heappop(work)

print(answer)

Submission status: Accepted

Solution code:
from heapq import *

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

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:
        r = heapq.heappop(heap)
        rewords -= r

print(rewords)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = []
heapq.heapify(tmp)

for i in range(M+1):
    if i in C:
        right = C[i]
        for j in right:
            heapq.heappush(tmp,-1*j)
        
    if tmp != []:
        answer += -1*heapq.heappop(tmp)
print(answer)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
r=0
from heapq import heappop,heappush
q=[]
l=[[] for i in range(10**5)]
for a,b in AB:
    l[a-1].append(b)
for i in range(M):
    for e in l[i]:
        heappush(q,-e)
    if len(q)>0:
        r+=-heappop(q)
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    work = [None for _ in range(N)]
    q = []
    heapq.heapify(q)
    for i in range(N):
        a, b = map(int, input().split())
        work[i] = (a, -b)
    
    work.sort()
    ans = 0
    id = 0
    for i in range(M):
        while id < N:
            if work[id][0] <= i + 1:
                heapq.heappush(q, (work[id][1], work[id][0]))
                id += 1
            else: break
        
        if q:
            gain, day = heapq.heappop(q)
            ans -= gain

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq

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

tank = []

p = []

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

q = 0
res = 0

for i in range(m+1):
    while q <= n-1 and p[q][0] <= i:
        heapq.heappush(tank,-p[q][1])
        q += 1
    
    if len(tank) == 0:
        continue
    else:
        res -= heapq.heappop(tank)
    #print(res)

print(res)

Submission status: Accepted

Solution code:
import heapq
Heappop=heapq.heappop
Heappush=heapq.heappush
N,M=map(int,input().split())
L=[]
for _ in range(N):
    a,b=map(int,input().split())
    L.append([a,-b])
L.sort()
q=[0]*10**5
ans=0
d=1
memo=0
while d<=M:
    while memo<=N-1:
        a,b=L[memo]
        if d<a:
            break
        else:
            Heappush(q,b)
            memo+=1
    ans-=Heappop(q)
    d+=1
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for i in range(n)]
ab = sorted(ab,key=lambda x: x[0],reverse=True)
heap = []
ans = 0
for i in range(1,m+1):
    while True:
        if not ab:
            break
        elif ab[-1][0] <= i:
            x = ab.pop(-1)
            heapq.heappush(heap,x[1]*-1)
        else:
            break
    if heap:
        y = heapq.heappop(heap)
        ans += y*-1
print(ans)