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:
import heapq
n,m=map(int, input().split())
lst = []
for i in range(n):
  a,b=map(int, input().split())
  lst.append((-b,a))
lst = sorted(lst, key=lambda x:x[1])

now_idx = 0
queue = []
sum_ = 0
for i in range(1,m+1):
  for j in range(now_idx, n):
    if lst[j][1] <= i:
      heapq.heappush(queue, lst[j])
    else:
      now_idx = j
      break
  if len(queue)>0:
    sum_ -= heapq.heappop(queue)[0]
print(sum_)

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    job =[[] for _ in range(m)]
    for i in range(n):
        a,b=map(int,input().split())
        if a-1 < m:
            job[a-1].append(-b) # b:asc, -b:desc
    
    res = 0
    q = []
    from heapq import heappop, heappush
    for i in range(m):
        for j in job[i]:
            heappush(q, j)
        if len(q) < 0:
            res += heappop(q) * -1 # -r -> r
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int,input().split())
B = [set() for _ in range(m)]
for i in range(n):
    a,b = map(int,input().split())
    if 1 <= a <= m:
        B[a-1].add(b)
task = []
heapq.heapify(task)
ans = 0
for i in range(m):
    for t in B[i]:
        heapq.heappush(task,-t)
    if task:
        ans += heapq.heappop(task)
print(-ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((-b,a))

from heapq import heapify, heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(1))

s = []
heapify(s)
ans = 0
if chk == []:
  print(0)
  exit()
  
cnt = 1
for i in chk:
  #print(i,cnt)
  a,b = i
  if b == cnt:
    heappush(s,i)
  if b > cnt:
    if s != []:
      r,t = heappop(s)
      if t <= cnt:
        ans -= r
      else:
        heappush(s,(r,t))
    heappush(s,i)
    cnt += 1
  #print(ans,s,cnt)
for i in range(m-cnt+1):
  if s != []:
    r,t = heappop(s)
    ans -= r
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((-b,a))

from heapq import heapify, heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(1))

s = []
heapify(s)
ans = 0
if chk == []:
  print(0)
  exit()
  
cnt = chk[0][1]
for i in chk:
  a,b = i
  if b == cnt:
    heappush(s,i)
  if b > cnt:
    r,t = heappop(s)
    ans -= r
    heappush(s,i)
    cnt = b
    
r,t = heappop(s)
ans -= r    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))
    
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)
chk = sorted(chk,key=itemgetter(1),reverse=True)
from collections import Counter
c = Counter()
s = 0
ss = m*(m+1)//2
ans = 0
for nn,i in enumerate(chk):
  if s == m:
    break
  a,b = i
  if c[a] <= m-a and ss >= a:
    ans += b
    c.update({a:1})
    s += 1
    ss -= a
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))
    
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)
chk = sorted(chk,key=itemgetter(1),reverse=True)
from collections import Counter
c = Counter()
s = 0
ss = m
ans = 0
for nn,i in enumerate(chk):
  if s == m:
    break
  a,b = i
  if c[a] <= m-a and ss >= a:
    ans += b
    c.update({a:1})
    s += 1
    ss -= a
    ss += m-1-nn
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N, M = map(int,input().split())
    l = []
    dup = [[] for _ in range(10**5+1)]
    for _ in range(N):
        A,B = map(int,input().split())
        l.append((B,A))
        bisect.insort(dup[B],A)

    l = sorted(l,reverse=True)

    ans = 0
    i = 0
    b, a = l.pop(0)
    for i in range(M+1):
        # print((b,a))
        # print(dup[b])
        if i + a <= M:
            ans += b
        if len(dup[b]) == 1:
            if len(l) > 0:
                b,a = l.pop(0)


        elif len(dup[b]) > 0: # if >= 2
            _a = dup[b].pop(-1)
            if a == _a:
                _a = dup[b].pop(-1)

            a = _a
            l.remove((b,a))

        else:
            if len(l) > 0:
                # print("p",l)
                b,a = l.pop(0)


    # print(l)
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
N, M = [int(s) for s in input().split()]
rewards = list(filter(lambda x: x[0] <= M
                , sorted([[int(s) for s in input().split()] for _ in range(N)])))

import heapq
a = []
heapq.heapify(a)

cnt = 1
sums = 0
for r in rewards:
    if r[0] == cnt:
        heapq.heappush(a, -1 * r[1])
        continue
    else:
        if a:
            sums += -1 * heapq.heappop(a)
        cnt += 1
        if r[0] == cnt:
            heapq.heappush(a, -1 * r[1])

while cnt <= M:
    if a:
        sums += -1 * heapq.heappop(a)
    cnt += 1

print(sums)

Submission status: Wrong Answer

Solution code:
#137D
def main():
    import sys
    import heapq as h
    from collections import defaultdict
    N, M = map(int, sys.stdin.readline().split())
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    #print(L)
    D = defaultdict(list)
    for i in range(N):
        D[L[i][0]-1].append(-L[i][1])
    
    #print(D)
    ans = 0
    tmp=[]
    h.heapify(tmp)
    for d in range(M):
        for b in D[d]:
            h.heappush(tmp, b)
        #print(tmp)
        ans += h.heappop(tmp)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x:(-x[1], -x[0]))
day = 0
pay = 0
for i in range(N):
  if day + ab[i][0] <= M:
    pay += ab[i][1]
    day += 1

print(pay)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(N)]
    D = sorted(D, key=lambda x: x[0], reverse=True)
    D = sorted(D, key=lambda x: x[1], reverse=True)
    now = 0
    check = 0
    answer = 0
    while now < M and check < N:
        if now + D[check][0] <= M:
            answer += D[check][1]
            check += 1
            now += 1
        else:
            check += 1
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A = n * [0]
B = n * [0]
for i in range(n):
    A[i], B[i] = map(int, input().split())

M = m * [0]
cnt = 0
for i in range(n):
    if A[i] <= m:
        cnt += max(B)
        b = max(B)
        B.remove(b)
        m -= 1
    else:
        pass
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m=f()
lt=[tuple(map(int,input().split())) for _ in range(n)]
lt.sort(key=lambda k:(k[1],k[0]))
s=0
while lt and m:
  a,b=lt.pop()
  if a<=m: s+=b; m-=1
print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input=sys.stdin.readline

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

ablist=[]
for i in range(N):
  A,B=map(int,input().split())
  ablist.append((B,-A))
ablist.sort()
  
answer=0
for i in reversed(range(M)):
  ablist_sub=[]
  while ablist:
    b,ma=ablist.pop()
    a=-ma
    if i+a<=M:
      answer+=b
      #print(i,a,b)
      break
    else:
      ablist_sub.append((b,ma))
      
  for ab in ablist_sub:
    ablist.append(ab)
    
print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
data = [list(map(int,input().split())) for i in range(N)]

A = []
for i in range(N):
    A.append((data[i][0],data[i][1]))

from operator import itemgetter

A = sorted(A,key = itemgetter(1))

ans = 0
r = M
for i in range(N-1,-1,-1):
    if A[i][0] <= r:
        ans += A[i][1]
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB = sorted(AB, reverse = True)

ans = 0
day = M

for i in range(N):
  if AB[i][0] <= day:
    ans += AB[i][1]
    day -= 1
  else:
    continue
  if day == 0:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
# D - Summer Vacation

# 価値、日数で降順ソートして上から取ってく

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

w = sorted(w, key=lambda x: (x[1], x[0]), reverse=True)

ans = 0
for w1 in w:
    if m >= w1[0]:
        ans += w1[1] 
    else:
        continue
    m -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
# D - Summer Vacation

# 価値、日数で降順ソートして上から取ってく

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

w = sorted(w, key=lambda x: (x[1], x[0]), reverse=True)

ans = 0
for w1 in w:
    if m >= w1[0]:
        ans += w1[1] 
    else:
        break
    m -= 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
ab = [list(map(int, readline().split())) for _ in range(n)]
ab.sort(key=lambda x: (-x[1], -x[0]))
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:
import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)
data.sort(key=lambda x:x[1], reverse=True)

N0 = 2 ** M.bit_length()
seg = [0] * (2*N0)

def seg_set(i,x):
    i = i + N0- 1
    seg[i] = x
    while i > 0:
        i = (i-1) // 2
        seg[i] = max(seg[i*2+1],seg[i*2+2])

def seg_query(i):
    i = i + N0 - 1
    ret = 0
    while i > 0:
        ret = max(ret,seg[i])
        i = (i-2) // 2
    return ret

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

for a,b in data:
    if a <= M:
        i = seg_query(M-a+1)
        if i >= 0:
            dp[i] = b
            seg_set(i,0)
print(sum(dp))

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
data = [LI() for _ in range(N)]
dp = [0] * (M+1)
data.sort(key=lambda x:x[1], reverse=True)

N0 = 2 ** M.bit_length()
seg = [0] * (2*N0)

def seg_set(i,x):
    i = i + N0- 1
    seg[i] = x
    while i > 0:
        i = (i-1) // 2
        seg[i] = max(seg[i*2+1],seg[i*2+2])

def seg_query(i):
    i = i + N0 - 1
    ret = 0
    while i > 0:
        ret = max(ret,seg[i])
        i = (i-2) // 2
    return ret

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

for a,b in data:
    if a <= M:
        i = seg_query(M-a+1)
        if i > 0:
            dp[i] = b
            seg_set(i,0)
print(sum(dp))

Submission status: Wrong Answer

Solution code:
def main():
	ip = input().split(" ")
	N = int(ip[0])
	M = int(ip[1])

	job = []

	for i in range(N):
		ip = input().split(" ")
		a = int(ip[0])
		b = int(ip[1])
		job.append([a,b])

	def keyFunc(j):
		return j[1]

	job = sorted(job, key=keyFunc, reverse=True)

	profit = 0

	for i in job:
		if i[0] <= M:
			profit += i[1]
			M -= 1
		if M == 0:
			break

	print(profit)

main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[0]*n
l1=[0]*n
day=0
K=0
for i in range(n):
    a,b=map(int,input().split())
    l[i]=a
    l1[i]=b
l2=sorted(l1,reverse=True)
for j in l2:
    if l[l1.index(j)]<=m-day:
        K+=j
    day+=1
print(K)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A_B = [[int(i) for i in input().split()] for _ in range(N)]
A_B.sort(reverse=True)
A_B.sort(key=lambda x: x[1], reverse=True)

ans = 0
cnt = M

for i in range(N):
    if 0 <= cnt:
        if A_B[i][0] <= cnt:
            ans += A_B[i][1]
            cnt -= 1
    else:
        break


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
part = []
for i in range(n):
    part.append(list(map(int, input().split())))
part.sort(reverse=True)
part.sort(reverse=True, key=lambda x: x[1])

que = deque()
for i in part:
    que.append(i)

ans = 0
for day in range(1, n + 1):
    while que:
        work = que.popleft()
        if day + work[0] <= m + 1:
            ans += work[1]
            break
    if not que:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
part = []
for i in range(n):
    part.append(list(map(int, input().split())))
part.sort(reverse=True)
part.sort(reverse=True, key=lambda x: x[1])
print(part)

que = deque()
for i in part:
    que.append(i)

ans = 0
for day in range(1, n + 1):
    while que:
        work = que.popleft()
        if day + work[0] <= m + 1:
            ans += work[1]
            break
    if not que:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template

N,M = inputlist()
li = []
for i in range(N):
    A,B = inputlist()
    B *= -1
    li.append([A,B])
ans = 0
from heapq import *
li.sort()
k = []
heapify(k)
flag = 0
for i in range(1,M+1):
    if flag == N:
        for t in range(M+1-i):
            ans -= heappop(k)
            print(ans)
            exit()
    while li[flag][0] <= i:
        heappush(k,li[flag][1])
        flag = flag + 1
        if flag == N:
            break
    if len(k)>=1:
        ans -= heappop(k)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
lst = []
for i in range(n):
	a, b = [int(j) for j in input().split()]
	lst.append((a, b))
lst = sorted(lst, key = lambda x: x[1], reverse=True)
nn = n if n < m else m

selected = []
while (len(selected) == 0):
	ok = [()] * nn
	tmp_selected = lst[:nn]
	tmp_selected = sorted(tmp_selected, reverse=True)
	judge = True
	for i in range(nn):
		if tmp_selected[i][0] <= m - i:
			ok[i] = tmp_selected[i]
		else:
			judge = False
	if judge:
		selected = ok
	if nn < n:
		nn += 1
	else:
		selected = ok
print (sum([i[1] if i else 0 for i in selected]))

Submission status: Wrong Answer

Solution code:
N, M = [int(s) for s in input().split(' ')]
BAs = []
for n in range(N):
    A, B = [int(s) for s in input().split(' ')]
    BAs.append((B, A))
BAs.sort(reverse=True)
i = 0
ret = 0
for d in range(0, M):
    m = M - d
    while i < N:
        B, A = BAs[i]
        if A <= m:
            ret += B
            i += 1
            break
        i += 1
print(ret)

Submission status: Wrong Answer

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

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

tasks = []
for i in range(n):
    ta, tb = map(int, input().split())
    tasks.append([ta, tb])
tasks.sort(key=lambda x:x[0], reverse = True)
tasks.sort(key=lambda x:x[1], reverse = True)
#print(tasks)

ans = 0
for i in range(m+1): #i日目にどのtaskを受け取るか
    #print("---------------")
    #print("現在のtasks: ", tasks)
    idx = 0
    isTaken = False

    #もしtasksが空なら終わり
    if len(tasks) == 0:
        break

    while(idx < len(tasks)):
        if tasks[idx][0] <= (m-i):
            temp = tasks.pop(idx)
            #print("temp:", temp, "がpopされました。idx: ", idx)
            isTaken = True
            break
        else:
            idx += 1
    if isTaken:
        ans += temp[1] #Bの値を加算
        #print("現在のans: ", ans)
        pass
    else:
        break
print(ans)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
work = [0]*n

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

work.sort(reverse=True)

ans = 0
key = 0
for i in range(m):
  while key < n-1 and work[key][1] + i > m:
    key += 1
    if key == n-1:
      break
  if key == n-1:
    if work[key][1] + i <= m:
      ans += work[key][0]
    break
  ans += work[key][0]
  key += 1

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
from collections import deque


def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)


def solve(N, M, A):
    A = sorted(A, key=lambda x: x[1], reverse=True)

    sch = list(range(M))

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        id = koenai_saidai_x_index(sch, day)
        #print(sch)
        #print(nouki, money, id)
        if id is False:
            continue
        sch.pop(id)
        ret += money

    return ret


#####################################################ライブラリ集ここから

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)

def solve(N, M, A):
    A = sorted(A, key=lambda x:x[1], reverse=True)

    sch = [False] * M

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        do = True
        while True:
            print(day)
            if sch[day]:
                day -= 1
            else:
                break
            if day == -1:
                do = False
                break
        if not do:
            continue

        sch[day] = True
        ret += money

        #print(nouki, money)

    return ret




#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)

def solve(N, M, A):
    A = sorted(A, key=lambda x:x[1], reverse=True)

    sch = [False] * M

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        do = True
        while True:
            print(day)
            if sch[day]:
                day -= 1
            else:
                break
            if day == -1:
                do = False
                break
        if not do:
            continue

        sch[day] = True
        ret += money

        print(nouki, money)

    return ret




#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)

def solve(N, M, A):
    A = sorted(A, key=lambda x:x[1], reverse=True)

    sch = list(range(M))

    ret = 0
    for nouki, money in A:
        day_latest = M - nouki
        if day_latest < 0:
            continue

        #print(sch)
        day = searchsorted(sch, day_latest, "right")

        if day != 0:
            sch.pop(day-1)
            ret += money
        #print(nouki, money)

    return ret




#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return 0

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
for _ in range(N):
  Ai,Bi = map(int,input().split())
  A.append([Ai,Bi])
A.sort(key=lambda x: x[0],reverse=True)  
k = A[N-1][0]
A.sort(key=lambda x: x[1],reverse=True)

sum_pay = 0
checked = [1]*N
j=0
for i in range(M-k+1):
  while A[j][0] > M-i or checked[j] == 0:
    if j == N-1:
      break  
    j += 1
  if A[j][0] <= M-i:
    sum_pay += A[j][1]
    checked[j] = 0
    j = 0
print(sum_pay)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
for _ in range(N):
  Ai,Bi = map(int,input().split())
  A.append([Ai,Bi])
A.sort(key=lambda x: x[0],reverse=True)  
A.sort(key=lambda x: x[1],reverse=True)

sum_pay = 0
checked = [1]*N
j=0
for i in range(N):
  while A[j][0] > M-i or checked[j] == 0:
    j += 1
    if j == N:
      break
  if j == N:
    break     
      
  sum_pay += A[j][1]
  checked[j] = 0

print(sum_pay)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
for _ in range(N):
  Ai,Bi = map(int,input().split())
  A.append([Ai,Bi])
A.sort(key=lambda x: x[0],reverse=True)  
A.sort(key=lambda x: x[1],reverse=True)

sum_pay = 0
checked = [1]*N
j=0
for i in range(M):
  while A[j][0] > M-i or checked[j] == 0:
    j += 1
    if j == N:
      break
  if j == N:
    break     
      
  sum_pay += A[j][1]
  checked[j] = 0

print(sum_pay)

Submission status: Wrong Answer

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

ans=0
t=1
for i in l:
    a=i[1]
    b=i[0]
#    print(a,b,t+a-1)
    if t+a-1>m:
        continue
    else:
 #       print(a,b,end=' entered')
        ans+=b
        t+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


# 普通のグラフ


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

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

    ab.sort(key=itemgetter(0))
    a = [ab[i][0] for i in range(n)]
    b = [ab[i][1] for i in range(n)]

    ans = 0

    for day in range(1, m + 1):
        idx = bisect.bisect_right(a, day)
        if idx > 0:
            temp = max(b[:idx])
            ans += temp
            b[idx-1] = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush,heapify
n,m=map(int,input().split())
work=[set() for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m: work[a].add(b)

ans=0
q=[]
for i in range(1,m+1):
    for x in work[i]:
        heappush(q,-x)
    if q!=[]: ans+=heappop(q)
print(-ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
work=[set() for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m: work[a].add(b)

ans=0
q=[]
for i in range(1,m+1):
    for x in work[i]:
        heappush(q,-x)
    if q!=[]: ans+=heappop(q)
print(-ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
n,m=map(int,input().split())
work=[set() for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m: work[a].add(b)

ans=0
q=[]
for i in range(1,m+1):
    for x in work[i]:
        heappush(q,-x)
    if q: ans+=heappop(q)
print(-ans)

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 = []
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)
        else:
            idx = i
            break

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


print(ans)