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: Wrong Answer

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

AB.sort()

STOCK = []
now = 1
ans = 0

idx = 0
for d in range(1, M+1):
    for i in range(idx, N):
        a, b = AB[i]

        if a <= d:
            heappush(STOCK, (-b, a))
        else:
            idx = i
            break

    if STOCK:
        p, _ = heappop(STOCK)
        p = -p
        ans += p


print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
X = []
for i in range(N):
    X.append(list(map(int, input().split())))
X.sort(key=lambda x: (-x[1], x[0]))

days = [i for i in range(1, M+1)]
ans = 0
for a, b in X:
    if len(days) == 0:
        break
    if days[-1] < a:
        continue
    left = bisect.bisect_right(days, a)
    if left > 0:
        days.pop(left-1)
    elif left == 0 and days[0] >= a:
        days.pop(0)
    else:
        continue
    ans += b
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
X = []
for i in range(N):
    X.append(list(map(int, input().split())))
# 給与が早くて，その中で大きい順
X.sort(key=lambda x: (-x[1], x[0]))
# A, B = [], []
days = [i for i in range(1, M+1)]
# print(days)
# for a, b in X:
#     A.append(a)
#     B.append(b)
ans = 0
for a, b in X:
    if len(days) == 0 or days[-1] < a:
        break
    left = bisect.bisect_right(days, a)
    ans += b
    if left > 0:
        days.pop(left-1)
    elif left == 0 and days[0] >= a:
        days.pop(0)
print(ans)

Submission status: Wrong Answer

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

cd = []
heapq.heapify(cd)
cnt = 0
ans = 0
# b, a
# aの条件
for k in range(m+1):
    # a = kの仕事をheappush
    
    for i in range(cnt, n):
        a, b = work[i]

        if a <= k:
            heapq.heappush(cd, [-b, a])
        else:
            cnt = i
            break
        
        if i == n-1:
            cnt = n-1

    if not cd:
        continue
    ans -= heapq.heappop(cd)[0]
print(ans)

Submission status: Wrong Answer

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

cd = []
heapq.heapify(cd)
cnt = 0
ans = 0
# b, a
# aの条件
for k in range(m+1):
    # a = kの仕事をheappush
    for i in range(cnt, n):
        a, b = work[i]

        if a <= k:
            heapq.heappush(cd, [-b, a])
        else:
            cnt = i
            break

    if not cd:
        continue
    ans += -heapq.heappop(cd)[0]
print(ans)

Submission status: Wrong Answer

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

cd = []
heapq.heapify(cd)
cnt = 0
ans = 0

# aの条件
for k in range(1, m+1):
    for i in range(cnt, n):
        a, b = work[i]

        if k < a:
            cnt = i
            break
        heapq.heappush(cd, [-b, a])

    if not cd:
        continue
    ans += -heapq.heappop(cd)[0]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda x: x[1], reverse=True)
AB.sort(key=lambda x: x[0])
# print(AB)
day = 0
ans = 0
for a, b in AB:
    if day < a and a <= M:
        # print(a, b)
        ans += b
        day = a
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda x: x[0], reverse=True)
AB.sort(key=lambda x: x[1], reverse=True)
# print(AB)
day = 0
ans = 0
for a, b in AB:
    if day + a <= M:
        ans += b
        day += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
D - Summer Vacation
https://atcoder.jp/contests/abc137/tasks/abc137_d

"""
import sys


from heapq import heapify, heappop

def solve(N, M, jobs):
    heapify(jobs)
    ans = 0
    while jobs:
        B, A = heappop(jobs)
        A, B = -A, -B
        if M >= A:
            M -= 1
            ans += B
    return ans


def main(args):
    N, M = map(int, input().split())
    jobs = []
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append([-B, -A])
    ans = solve(N, M, jobs)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ab = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if m > a:
        ab[a-1].append(-b)
heap = []
ans = 0
for i in range(m):
    for j in ab[i]:
        heapq.heappush(heap, j)
    if heap:
        res = heapq.heappop(heap)
        ans += -res
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

class Sato():

	def __init__(self):
		pass


N, M = map(int,input().split())
S = []
money = 0
max_money = 0

for _ in range(N):
	S.append(list(map(int, input().split())))

C = list(itertools.permutations(range(N), M))

for i in C:
	for j,elem in enumerate(i):
		if S[elem][0] + j <= M:
			money += S[elem][1]
	if money > max_money:
		max_money = money
	money = 0
print(max_money)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append([a,b])
AB.sort(key=lambda x:-1*x[1]*10**6-x[0])
cnt=0
ans=0
while True:
    end=False
    for i in range(0,N):
        if M-cnt>=AB[i][0]:
            ans+=AB[i][1]
            cnt+=1
            AB[i][0]=10**7
            break
        if i==N-1:
            end=True
    if end:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from operator import itemgetter 
    n,m=map(int,input().split())
    W=[list(map(int,input().split())) for _ in range(n)]

    W.sort(key=itemgetter(1,0),reverse=True)

    
    i,j,income=0,0,0
    while i<m and j<n:
        if W[i][0]+i<=m:
            income+=W[i][1]
            i+=1
            j+=1
        else:
            j+=1
    
    print(income)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
C = []
for i in range(n):
  a, b = map(int, input().split())
  C.append([a, b])
C.sort(reverse=True, key=lambda x:(x[1], x[0]))
ans = 0
for i in range(n):
  if m < C[i][0]: continue
  else: 
    ans += C[i][1]
    m -= i
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b])
Y=sorted(X,key=lambda x:(x[1],x[0]), reverse=True)
ans=0
d=0
for i in range(n):
    if d+Y[i][0]<=m:
        ans+=Y[i][1]
        d+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b])
Y=sorted(X,key=lambda x:(x[1],x[0]), reverse=True)

ans=0
d=0
for i in range(n):
    if d+Y[i][0]<=m:
        ans+=Y[i][1]
        d+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b])
Y=sorted(X,key=lambda x:(x[1]), reverse=True)

ans=0
d=0
for i in range(n):
    if d+Y[i][0]<=m:
        ans+=Y[i][1]
        d+=1
print(ans)

Submission status: Wrong Answer

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

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

work = []
heapq.heapify(work)
ans = 0

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Jobs = dict()
for _ in range(N):
  A, B = map(int, input().split())
  if B in Jobs:
    Jobs[B].append(A)
  else:
    Jobs[B] = [A]

# print(Jobs)
# key:報酬, val:[入金LT]

key_desc = sorted(Jobs, reverse=True)
# print(key_desc)
# 報酬大きい順にソート

from collections import deque
jobs_prior = deque()
for key in key_desc:
  val_desc = sorted(Jobs[key], reverse=True)
  for v in val_desc:
    jobs_prior.append([key, v])

# print(jobs_prior)
# 優先順に並べる、報酬大きく、入金LT長いものから順にやっていく

today = 0
pay = 0

while len(jobs_prior) > 0:
  if today > M: break
  lt = M - today
  job = jobs_prior.popleft()
  if job[1] <= lt:
    pay += job[0]
    today += 1

print(pay)

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  from  operator import itemgetter
  input=sys.stdin.readline
  n,m=map(int,input().split())
  works=[list(map(int,input().split())) for i in range(n)]
  
  works.sort(key=itemgetter(1,0),reverse=True)
  j,money=0,0
  for i in range(m):
    while j<n and works[j][0]>m-i:
      j+=1
    if j!=n:
      money+=works[j][1]
      j+=1
    else:
      break
  print(money)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((-v, u))
d = dd(list)
for x in a:
  v, u = x
  d[u].append(v)
dp = [0] * (M + 1)
ks = sorted(d.keys())
hp = []
k = 0
#print(ks)
for i in range(1, M + 1):
  j = bl(ks, i)
  #print(ks[j], i)
  if len(ks) > j:
    if ks[j] > i: continue
    for y in range(k, j + 1):
      k = ks[y]
      for z in d[k]:
        heapq.heappush(hp, z)
  #print(hp)
  dp[i] = -heapq.heappop(hp)
  k = j + 1
#print(dp)
print(sum(dp))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,m = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
b,a = zip(*sorted(zip(b,a)))
bit_booked = [False]*(m+1)
last_max = m
ans = 0
for i in range(n):
    if a[n-1-i] > last_max:pass
    else:
        print(a[n-1-i],bit_booked)
        bit_booked[a[n-1-i]] = True
        ans+= b[n-1-i]
        if a[n-1-i] == last_max:
            while True:
                last_max -= 1
                if bit_booked[last_max] == False:
                    break
print(bit_booked)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(reverse=True, key=itemgetter(1))

# N: 処理する区間の長さ
N0 = 2**M.bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(M+1):
    update(M-i, i+1)

ans = 0
for i in range(N):
    if L[i][0] > M:
        continue
    q = query(0, L[i][0]+1)
    if q > 0:
        update(L[i][0], q-1)
        update(0, M-i-1)
        ans += L[i][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    a[i][0]*=-1
a.sort()
a.sort(reverse=True, key=lambda x:x[1])
k=0
ans=0
# print(a)
for i in range(m):
    while k<n and -a[k][0]+i>m:
        k+=1
    if k<n:
        ans+=a[k][1]
        k+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(reverse=True, key=itemgetter(1))

# N: 処理する区間の長さ
N0 = 2**(M-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(M):
    update(M-1-i, i+1)

ans = 0
for i in range(N):
    if L[i][0] > M:
        continue
    q = query(0, L[i][0])
    if q > 0:
        update(L[i][0]-1, q-1)
        update(0, M-i-1)
        ans += L[i][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(reverse=True, key=itemgetter(1))
seg = [0]*(2**20-1)

def update(k, x):
    k += M-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[2*k+1], seg[2*k+2])
        
def query(p, q):
    p += M-1
    q += M-2
    res = 10**6
    while q-p > 1:
        if p&1 == 0:
            res = min(res, seg[p])
        if q&1 == 1:
            res = min(res, seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = min(res, seg[q])
    else:
        res = min(res, seg[p], seg[q])
    return res

for i in range(M):
    update(M-1-i, i+1)

ans = 0
for i in range(N):
    if L[i][0] > M:
        continue
    q = query(0, L[i][0])
    if q > 0:
        update(L[i][0]-1, q-1)
        update(0, M-i-1)
        ans += L[i][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(reverse=True, key=itemgetter(1))
seg = [0]*(2*M-1)

def update(k, x):
    k += M-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[2*k+1], seg[2*k+2])
        
def query(p, q):
    p += M-1
    q += M-2
    res = 10**6
    while q-p > 1:
        if p&1 == 0:
            res = min(res, seg[p])
        if q&1 == 1:
            res = min(res, seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = min(res, seg[q])
    else:
        res = min(res, seg[p], seg[q])
    return res

for i in range(M):
    update(M-1-i, i+1)

ans = 0
for i in range(N):
    if L[i][0] > M:
        continue
    q = query(0, L[i][0])
    if q > 0:
        update(L[i][0]-1, q-1)
        update(0, M-i-1)
        ans += L[i][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
for _ in range(N):
  u, v = map(int, input().split())
  a.append((u, v))
a.sort(key = lambda x: (-x[1], -x[0]))
res = 0
day = 0
for i in range(N):
  u, v = a[i]
  if day + u <= M:
    day += 1
    res += v
print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
L = [list(map(int,input().split())) for k in range(N)]
L = sorted(L, key = lambda x:(-x[1],-x[0]))
now = 0
ans = 0
for e in L:
    if e[0] + now <= M:
        ans += e[1]
        now += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

AB = sorted(AB, key=lambda x:x[0])
idx = 0
ans = 0

heap = []
heapq.heapify(heap)

for i in range(1,m+1):
    while idx < len(AB):
        if AB[idx][0] == i:
            heapq.heappush(heap, AB[idx][1]*-1)
            idx += 1
        else:
            break
    if len(heap) >= 1:
        ans += heapq.heappop(heap) * -1
    else:
        pass
    
    if idx == len(AB) -1:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b  = map(int, input().split())
    if b <= m:
        AB.append((a, b))
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = b
        counts[a - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b  = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
used = [False] * m
total = 0
score = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if used[i]:
            continue
        used[i] = True
        counts[a - 1] += 1
        total += 1
        score += b
        break
    if total == m:
        break
print(b)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [None] * n
maxa = 0
for i in range(n):
    AB[i] = tuple(map(int, input().split()))
    if AB[i][0] > maxa:
        maxa = AB[i][0]
AB.sort(key=lambda ab: -ab[1])
cands = [AB[i][1] for i in range(max(m - maxa, 0))]
counts = [0] * m
for i in range(max(m - maxa, 0), n):
    if AB[i][0] <= m and sum(counts[AB[i][0] - 1:]) <= m - AB[i][0]:
        cands.append(AB[i][1])
        counts[AB[i][0] - 1] += 1
        if len(cands) == m:
            break
print(sum(cands))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [None] * n
maxa = 0
for i in range(n):
    AB[i] = tuple(map(int, input().split()))
    if AB[i][0] > maxa:
        maxa = AB[i][0]
AB.sort(key=lambda ab: -ab[1])
cands = [b for _, b in AB[:m - maxa]]
AB = AB[m - maxa:]
counts = [0] * m
for a, b in AB[:maxa]:
    if a <= m and sum(counts[a - 1:]) <= m - a:
        cands.append(b)
        counts[a - 1] += 1
print(sum(cands[:m]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
cands = []
counts = [0] * m
for a, b in AB:
    if a <= m and counts[a - 1] <= m - a:
        cands.append(b)
        for i in range(a):
            counts[i] += 1
print(sum(cands[:m]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = []
for a, b in AB:
    if a <= m and counts[a - 1] < m - a + 1:
        cands.append(b)
        counts[a - 1] += 1
print(sum(cands[:m]))

Submission status: Wrong Answer

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

l = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for a, b in sorted(l, key=lambda x:(-x[1],-x[0])):
    if M<1:break
    if a<=M:
        ans += b
        M -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る←だめでした

# 解説AC
# 後ろから問題を見ていくと良いかも？
# 前から貪欲ではなぜ行けないのか？→残り日付が遠い中で最大の報酬 よりも 残り日付が近い中で最大の報酬を選んだほうが最適になる可能性があるから
# では後ろから貪欲は？→残り日付が近いなかで最大の報酬はその時点で最適な選択肢となることが確定できる。→OK
# だけどi日後までの候補に絞ってソートし直すと O(MNlogN)の計算量になる
# →priority queueで高速化
# つまり i 日後を考えるときに、それが可能となる候補をqueに追加 (最大logNがM回必要)
# その中で最大の報酬をもたらすものをpop (最大logNがM回必要)
# 日付のソートでNlogNかかる。
# この問題の計算量はO((M+N)logN)である


from heapq import heapify, heappop, heappush, heappushpop
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


N, M = read_ints()
AB = read_tuple(N)
AB.sort()

q = PriorityQueue([])
l = 0  # ABのindex
ans = 0

for i in range(1, M + 1):
    for j in range(l, N):
        a, b = AB[j]
        l = j
        if a > i:  # i日以内に支払われない # こういう書き方はbugの原因になるから控えよう
            break
        q.push(-b)  # pythonでは最小ヒープのため
    if q:  # qが空のときはしょうがないのでskip
        ans -= q.pop()

# # 前処理しておくと実装が楽という例
# from collections import defaultdict
# ilimb = defaultdict(lambda: [])
# for a, b in AB:
#     ilimb[a].append(b)

# for i in range(1, M + 1):
#     for b in ilimb[i]:
#         q.push(-b)  # pythonでは最小ヒープのため
#     if q:  # qが空のときはしょうがないのでskip
#         ans -= q.pop()

print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る←だめでした

# 解説AC
# 後ろから問題を見ていくと良いかも？
# 前から貪欲ではなぜ行けないのか？→残り日付が遠い中で最大の報酬 よりも 残り日付が近い中で最大の報酬を選んだほうが最適になる可能性があるから
# では後ろから貪欲は？→残り日付が近いなかで最大の報酬はその時点で最適な選択肢となることが確定できる。→OK
# だけどi日後までの候補に絞ってソートし直すと O(MNlogN)の計算量になる
# →priority queueで高速化
# つまり i 日後を考えるときに、それが可能となる候補をqueに追加 (最大logNがM回必要)
# その中で最大の報酬をもたらすものをpop (最大logNがM回必要)
# 日付のソートでNlogNかかる。
# この問題の計算量はO((M+N)logN)である


from heapq import heapify, heappop, heappush, heappushpop
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


N, M = read_ints()
AB = read_tuple(N)
AB.sort()

q = PriorityQueue([])
l = 0  # ABのindex
ans = 0

for i in range(1, M + 1):
    for j in range(l, N):
        a, b = AB[j]
        if a > i:  # i日以内に支払われない
            l = j
            break
        q.push(-b)  # pythonでは最小ヒープのため
    if q:  # qが空のときはしょうがないのでskip
        ans -= q.pop()


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A] += [-B]
print(dic, sorted(dic.keys()))

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        heap += dic[i + 1]
    heapq.heapify(heap)
    # print(heap)
    if heap:
        ans += -heapq.heappop(heap)

print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
# 全然わからん ソートしてgreedyに報酬高いやつから突っ込めるだけ突っ込んで見る


# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


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

ans = 0
left = M
for a, b in AB:
    if a <= left:
        ans += b
        left -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

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

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


result = 0
for i in range(1, M+1)[::-1]:
  if not queue:
    break

  b, a = heappop(queue)
  a = -a
  b = -b

  while queue and a > i:
    b, a = heappop(queue)
    a = -a
    b = -b

  if a > i:
    break

  result += b

print(result)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            heapq.heappush(candidates, -b)
        else:
            s = j
            break
    else:
        s = j
    if len(candidates) > 0:
        # print(candidates)
        ans += -1 * heapq.heappop(candidates)

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            heapq.heappush(candidates, -b)
        else:
            s = j
            break
    if len(candidates) > 0:
        ans += -1 * heapq.heappop(candidates)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32
import heapq

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    ab = [[-1*B[i], -1*A[i]] for i in range(N)]
    # ab = sorted(ab, key=lambda x:(x[0], -x[1]))
    heapq.heapify(ab)

    c = 0
    for i in range(M, 0, -1):
        if len(ab) > 0:
            tmp = []
            b, a = heapq.heappop(ab)
            while len(ab) > 0 and -a > i:
                b, a = heapq.heappop(ab)
            if -a <= i:
                # print(i, b, a)
                c += -b
            
        
    print(c)

    return



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
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
work = [[]]*M

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

max = 0
num = []
for i in range(M):
    num=sorted(num+work[i],reverse=True)
    if len(num)>0:
        max+=num[0]
        num=num[1:]
        if N-i < len(num):
            num = num[0:N-i]

print(max)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
AB = [None for i in range(10**5 + 1)]
RE = []

for i in range(N):
  a, b = map(int, input().split())
  if AB[a] == None:
    AB[a] = b
  else:
    if AB[a] > b:
      heappush(RE, (-b, a))
    else:
      heappush(RE, (-AB[a], a))
      AB[a] = b

ans = 0

for i in list(range(M+1))[::-1]:
  salary, m = 0, float("inf")
  while RE and m > i:
    (salary, m) = heappop(RE)
  else:
    if m > i:
      salary = 0
  salary *= -1
  
  if not AB[i] or salary > AB[i]:
    ans += salary
  else:
    ans += AB[i]
    heappush(RE, (-salary, m))

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i+1,AB))
    heapq.heapify(AB2)
    if not AB2:
        continue
    b,a = heapq.heappop(AB2)
    work[i-1] = -b
    AB.remove([b,a])
print(sum(work))

Submission status: Wrong Answer

Solution code:

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

T = []

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

T.sort(key=lambda x: (-x[1], -x[0]))

j = 0
ans = 0
for i in range(N):
  days, money = map(int, T[i])
  if j + days <= M:
    ans += money
    j += 1
  i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]
points.sort(key=lambda x: x[1])

point = 0
while m > 0:
    if not points:
        break
    t, p = points.pop()
    if t <= m:
        point += p
        m -= 1

print(point)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB = []
for _ in range(N):
  a,b = map(int,input().split())
  AB.append([b,a])
AB.sort(reverse=True)
ans = 0
for b,a in AB:
  if a<=M:
    ans += b
    M -= 1
  if M == 0:break
print(ans)

Submission status: Wrong Answer

Solution code:
n,dias = tuple(map(lambda x: int(x),input().split(" ")))
trabajos = []
for i in range(n):
    trabajo = tuple(map(lambda x: int(x),input().split(" ")))
    trabajos.append(trabajo)
trabajos.sort(key=lambda x: x[1],reverse=True)

while True:
    problema = False
    if len(trabajos) <= dias:
        trabajos_tomados = trabajos.copy()
    else:
        trabajos_tomados = trabajos[:dias].copy()
    trabajos_tomados.sort(key=lambda x: x[0],reverse=True)
    for i,j in enumerate(trabajos_tomados):
        if j[0] > dias-i:
            problema = True
            trabajos.remove(j)
            break
    if not problema:
        break
    
suma = 0
for i in trabajos_tomados:
    suma += i[1]
print(suma)

Submission status: Wrong Answer

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

for i in range(N):
    BA[i][1],BA[i][0] = map(int,input().split())

BA.sort(reverse=True)

ans=0
d=0
for i in range(N):
    if BA[i][1]<=M-d:
        ans+=BA[i][0]
        d+=1
    if d==M:
        break

print(ans)