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:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    count = [0] * (M+1)
    Q = []
    for a, b in zip(A, B):
        lim = M-a+1
        if lim <= 0:
            continue
        if count[a] >= lim:
            continue
        count[a] += 1
        heapq.heappush(Q, -b)
    print(-sum(Q[:M]))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
# -*- coding: utf-8 -*-

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N, M = readInts()
  tasks = [tuple(readInts()) for _ in range(N)]
  tasks.sort(key=lambda x: (x[1], x[0]), reverse=True)

  ans = 0
  cur = 0
  for m in range(M, 0, -1):
    while cur < len(tasks) and tasks[cur][0] > m:
      cur += 1
    if cur >= len(tasks):
      break
    ans += tasks[cur][1]
    cur += 1
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = list(map(int, input().split()))
    ab = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (-x[1], -x[0]))
    now = 0
    earn = 0
    for days, value in ab:
        if now + days <= m:
            earn += value
            now += 1
        elif now == m:
            break
    return earn


if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
li = [tuple(map(int, input().split())) for i in range(N)]
ans = 0

li.sort(key=lambda x: x[0], reverse=True)
li.sort(key=lambda x: x[1], reverse=True)
# print(li)
for i in li:
    if i[0] <= M:
        ans += i[1]
        M -= 1
print(ans)

Submission status: Wrong Answer

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

cnt=0


i = 0
j = 0
while i <= m:
    if j == n:
        break
    a =AB[j][0]
    b =AB[j][1]
    j+=1
    if i + a <=m:
        cnt += b
        i+=1
    else:
        pass

print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]
works = sorted(works,key=lambda x: x[1])
works = works[::-1]

day = 0
income = 0
for i in range(N):
  if (day + works[i][0]) <= M:
    income += works[i][1]
    day += 1
  else:
    continue
    
print(income)

Submission status: Wrong Answer

Solution code:
N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn==M-ab[0]-i:
                break
            D[M-ab[0]-i]+=1
            if D[M-ab[0]-i]==1:
                pay+=ab[1]
                flag=False
                break
            else:
                i+=D[M-ab[0]-i]

        if flag:
            mn=M-ab[0]
            
print(pay)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,M = inputMap()
	ab = []
	cnt = {}
	for i in range(N):
		a,b = inputMap()
		if a in cnt:
			cnt[a] += 1
		else:
			cnt[a] = 1
		ab.append((a,b))

	aa = sorted(ab, key=lambda x:(-x[1],x[0]))
	#aa = sorted(ab, key=lambda x:(-x[0],-x[1]))

	ans = 0
	#print(aa)
	for i in range(M,0,-1):
		#print(i)
		for j, val in enumerate(aa):
			a,b = val
			#print("{} {}".format(a,i))
			if i >= a:
				if i == a:
					cnt[a] -= 1
					ans += b
					aa.pop(j)
					#print(aa)
					break
				else:
					tmp = cnt[a] - 1
					if tmp > 0:
						cnt[a] -= 1
						ans += b
						aa.pop(j)
						#print(aa)
						break
					else:
						continue

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = map(int, input().split())
    BA = sorted(list(map(int, input().split()))[::-1] for _ in range(n))[::-1]
    cnt = 0
    ans = 0
    for b, a in BA:
        if cnt == m:
            break
        if cnt + a > m:
            continue
        ans += b
        cnt += 1
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A_B = []
for i in range(N):
    A, B = map(int, input().split())
    if A > M:
        pass
    else:
        A_B.append((A,B))
# print(A_B)
if len(A_B) == 0:
    print(0)
else:
    # print(sorted(A_B, key=lambda x: x[1]))
    A_B = sorted(A_B, key=lambda x: x[0])
    A_B = sorted(A_B, key=lambda x: x[1])[::-1]
    # print(A_B)
    # lim = 0
    reward = 0
    cnt = M
    for t in A_B:
        if  cnt - t[0] >= 0:
            reward += t[1]
        cnt -= 1
            
    print(reward)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

Submission status: Wrong Answer

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

jobs = []
for i in range(N):
    jobs.append(list(map(int, input().split())))
    
jobs = sorted(jobs, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
for day in range(N):
    if len(jobs) == 0:
        break

    if day + jobs[0][0] <= M:
        ans += jobs[0][1]
        jobs.pop(0)
    else:
        while len(jobs):
            if day + jobs[0][0] <= M:
                ans += jobs[0][1]
                jobs.pop(0)
                break
            else:
                jobs.pop(0)
print(ans)

Submission status: Wrong Answer

Solution code:
N, m = map(int, input().split())  # N件のアルバイト, M日後までの報酬
m += 1
arubaito = [list(map(int, input().split())) for _ in range(N)]  # A日後に, B円報酬がもらえる。

arubaito = sorted(arubaito, key=lambda x: (x[1], x[0]), reverse=True)  # 報酬順にソート

ans = 0
for i in range(len(arubaito)):
    if m == arubaito[i][0]:
        continue
    if m >= arubaito[i][0]:
        ans += arubaito[i][1]
        m -= 1  # 日雇いアルバイトしたなら日付を進める

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(zz) for zz in input().split()]

L = [[0] for _ in range(M)]
ans = []
for _ in range(N):
    a,b = [int(zz) for zz in input().split()]
    if a > M:
        continue
    if len(L[a-1]) > M-a and min(L[a-1]) > b:
        continue
    else:
        L[a-1].remove(min(L[a-1]))

    L[a-1].append(b)
    ans.append(b)

for i in range(M):
    L[i].sort(reverse=True)

ans.sort(reverse=True)

p = min(len(ans),M)
print(sum(ans[:p]))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
q = list()
for _ in range(N):
    A, B = map(int, input().split())
    deadline = M - A
    reward_inv = -B
    if deadline >= 0:
        heappush(q, (reward_inv, deadline))

ans = 0
for day in range(M + 1):
    if len(q) == 0:
        print(ans)
        exit(0)
    reward_inv, deadline = heappop(q)
    while deadline < day:
        if len(q) == 0:
            print(ans)
            exit(0)
        reward_inv, deadline = heappop(q)
    ans += - reward_inv

print(ans)

Submission status: Wrong Answer

Solution code:
n,m= map(int, input().split())
t=[]
for _ in range(n):
    a, b = map(int, input().split())
    t.append((a,b))
    
t=sorted(t,key=lambda x: x[1],reverse=True)
for i in range(n-1):
  if t[i][0]<t[i+1][0] and t[i][1]==t[i+1][1]:
    tmp=t[i]
    t[i]=t[i+1]
    t[i+1]=tmp
limit=m
score=0

for _ in range(n):
  if len(t)>1:
    if t[0][0]<=limit:
        score+=t[0][1]
        del t[0]
        limit-=1
    else:
        del t[0]
  else:
    break
    
print(score)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(N)]
info = sorted(info, key=lambda x:(-x[1], x[0]))
#print(info[:M])

result = 0
j = 1
for i in info:
  if i[0] <= j:
    result += i[1]
    j += 1
  if j > M:
    break
    
print(result)

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))
ans = 0
sAB = sorted(AB, key=lambda x: (x[1], x[0]), reverse=True)
for a, b in sAB:
    if M >= a:
        ans += b
        M -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split(' '))
    w = [list(map(int,input().split(' '))) for i in range(n)]
    w = sorted(w, key=lambda x: x[0])
    w = sorted(w,key=lambda x:x[1],reverse=True)
    res = [0 for i in range(m+1)]
    ans = 0
    for i in range(min(n,m)):
        a,b=w[i]
        k = a
        while m-k >=0:
            if not res[m-k]:
                res[m-k] = 1
                break
            else:
                k +=1
        if m-k >=0:
            ans += b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        if len(a) == 0:
            return b
        if len(b) == 0:
            return a
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
                    return res
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
                    return res
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            # q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()

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]))

c = M
ans = 0

for k in range(N):
    if L[k][0] <= M:
        ans += L[k][1]
        c -= 1
        M -= 1
    if c == 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
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[0]), reverse=True)
lst.sort(key=lambda x:(x[1]), reverse=True)

ans = 0
ind = 0
for i in range(1, m+1):
    if ind >= n:
        break
    tugi = True
    while tugi:
        if lst[ind][0] <= m - i + 1:
            ans += lst[ind][1]
            ind += 1
            tugi = False
        else:
            ind += 1
        if ind >= n:
            tugi = False

print(ans)

Submission status: Wrong Answer

Solution code:
# 2019 8/10
# ABC137 D Summer Vacation

info = []
reword = 0
day = 0

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

for i in range(N):
    A, B = map(int, input().split())
    info.append([B, A])

info.sort(reverse=True)

for i in range(N):
    # if day > M:
    #     break

    if info[i][1] + day <= M:
        reword += info[i][0]
        day += 1


print(reword)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
job_list = [[int(x) for x in input().split()] for i in range(N)]
job_list = sorted(job_list,key=itemgetter(1))
ans = 0
for i in range(N):
  if i+job_list[N-1-i][0] <= M:
    ans += job_list[N-1-i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
ab = [input().split() for i in range(n)]
ab.sort(key=lambda x:x[1], reverse=True)

dic = {}
for i in range(m):
  dic[i+1] = True

ans = 0
for a, b in ab:
  a = int(a)
  b = int(b)
  tmpa = a
  while(True):
    if tmpa in dic:
      if dic[tmpa]==True:
        dic[tmpa] = False
        ans += b
        break
      else:
        tmpa += 1
    else:
      break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split(' '))
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split(' '))))
ab = sorted(ab, key=lambda x: (-x[1], -x[0]))

ans = 0
while m > 0:
    if ab[0][0] <= m:
        ans += ab[0][1]
        ab.pop(0)
    else:
        break
    m -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
# 2019 8/10
# ABC137 D Summer Vacation

info = []
reword = 0
day = 0

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

for i in range(N):
    A, B = map(int, input().split())
    info.append([B, A])

info.sort(reverse=True)

for i in range(N):
    if day > M:
        break

    if info[i][1] + day <= M:
        reword += info[i][0]
        day += 1


print(reword)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
f = []
for _ in range(n):
    x, y = list(map(int, input().split()))
    f.append({'a':x, 'b':y})
    
f = sorted(f, key = lambda i: (-i['b'], -i['a'])) 
# print(f)
day = 0
ans = 0
for x in f:
    if x['a'] <= m - day:
        ans += x['b']
        day += 1
    if day > m:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,M = map(int,input().split())
D = [[] for i in range(M)]
for i in range(N):
    A,B = map(int,input().split())
    if A <= M:
        D[A-1].append(B)
print(D)
count = 0
Tax = []
for i in range(M):
    for j in D[i]:
        bisect.insort_left(Tax,j)
    if not Tax:
        continue
    count += Tax.pop()
print(count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
li = []
count = 0
for i in range(N):
    l = list(map(int,input().split()))
    li.append(l)
li.sort(key = itemgetter(1,0),reverse = True)
for i in range(N):
    if li[i][0] <= M:
        count += li[i][1]
        M -= 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
bite = []
ans = 0
for _ in range(n):
    bite.append([int(x) for x in input().split()])
bite = sorted(bite, key=lambda x:x[0], reverse=True)
bite = sorted(bite, key=lambda x:x[1], reverse=True)
cnt = 0
for l in bite:
    if m - cnt < 1:
        break
    if l[0] <= m - cnt:
        ans += l[1]
        cnt += 1
print(ans)

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]))
c = 0
ans = 0

for k in range(N):
    if L[k][0] <= M:
        ans += L[k][1]
        c += 1
        M -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

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

ans = 0
days = 0

for i in ab:
  if i[0] + days > m:
    pass
  else:
    ans += i[1]
    days += 1
  if days == m:
    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())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
cnt = -1
pool = []
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      pool.append(ab[here][1])
      here += 1
    else:
      break
  pool.sort()
  try:
    ans += pool[cnt]
    cnt -= 1
  except:
    pass
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])
    d = collections.defaultdict(list)
    # print(n, m)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        # print(ai, bi)
        d[bi].append(ai)

    # print(d)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    ans = 0
    j = 0
    i = 0
    for k in range(m):
        bound = m-k
        is_found = False
        while i < len(rewards):
            bi = rewards[i]
            while j < len(d[bi]):
                if d[bi][j] <= bound:
                    ans += bi
                    j += 1
                    is_found = True
                    break
                else:
                    j += 1
            if j == len(d[bi]):
                i += 1
                j = 0
            if is_found:
                break
    return ans

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
cost_rewards = dict()
for _ in range(n):
    a, b = get_numbers()
    if a not in cost_rewards:
        cost_rewards[a] = [b]
    else:
        cost_rewards[a].append(b)

for key, val in cost_rewards.items():
    cost_rewards[key] = sorted(val, reverse=True)

ans = 0
for i in range(m, 0, -1):
    max_reward = 0
    cost_of_max_reward = 0
    for cost, rewards in sorted(cost_rewards.items(), key=lambda x: -x[0]):
        if cost > i:
            continue

        val = rewards[0]
        if val > max_reward:
            cost_of_max_reward = cost
            max_reward = val
    if cost_of_max_reward > 0:
        ans += max_reward
        cost_rewards[cost_of_max_reward].pop(0)
        if len(cost_rewards[cost_of_max_reward]) == 0:
            del cost_rewards[cost_of_max_reward]


print(ans)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: -x[0])
ab.sort(key = lambda x: -x[1])
q, cnt, ans = [], 0, 0
for i, (a, b) in enumerate(ab):
    if cnt == M:
        break
    if a+i <= M:
        ans += b
        cnt += 1
        heappush(q, [-a-i, a, i])
    else:
        tmp = []
        while len(q):
            p, _a, j = heappop(q)
            if _a+i <= M and a+j <= M:
                ans += b
                cnt += 1
                break
            else:
                tmp.append([p, _a, j])
        q.extend(tmp)
        heapify(q)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

info=[]
for i in range(n):
  info.append(list(map(int,input().split())))

order=sorted(info,key=lambda x:x[1])
sum=0
for i in range(n):
  for j in range(n-i):
    if m-i-order[-j-1][0]>=0:
      sum+=order[-j-1][1]
      order.pop(-j-1)
      break
    


print(sum)

Submission status: Wrong Answer

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

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort(key = lambda x: x[0],reverse = True)
ab.sort(key = lambda x: x[0]+x[1],reverse = True)

count = 0
ans = 0
while m >= 0 and count < n:
    a,b = ab[count][0],ab[count][1]
    if m >= a:
        ans += b
        m -= 1
    count += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = list(map(int, input().split()))
    ab = sorted(list(list(map(int, input().split())) for _ in range(n)), key=lambda x: (-x[1], -x[0]))
    now = 0
    earn = 0
    for days, value in ab:
        if now + days <= m:
            earn += value
            now += 1
        else:
            now += 1
            continue
        if now >= m:
            break
    return earn


if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
f = []
for _ in range(n):
    x, y = list(map(int, input().split()))
    f.append({'a':x, 'b':y})
    
f = sorted(f, key = lambda i: (-i['b'], -i['a'])) 
# print(f)
day = 1
ans = 0
for x in f:
    if x['a'] <= m - day:
        ans += x['b']
        day += 1
    if day > m:
        break

print(ans)

Submission status: Wrong Answer

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

d = defaultdict(list)

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

works = []
for k, v in d.items():
    d[k] = sorted(d[k], reverse=True)
    if M-k+1 >= 1:
        works.extend(d[k][:M-k+1])

works = sorted(works, reverse=True)

print(sum(works[:M]))

Submission status: Wrong Answer

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):
    cur = M - i
    val, idx = sti.get_val(0, cur+1)
    if val == -INF:
        break
    ans += val
    if len(days[idx]):
        days[idx].pop(-1)
        if len(days[idx]):
            sti.update(idx, days[idx][-1])
        else:
            sti.update(idx, -INF)
print(ans)

Submission status: Wrong Answer

Solution code:
# 2019 8/10
# ABC137 D Summer Vacation

info = []
reword = 0
day = 0

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

for i in range(N):
    A, B = map(int, input().split())
    info.append([B, A])

info.sort(reverse=True)
print(info)

for i in range(N):
    if day >= M:
        break

    if info[i][1] + day <= M:
        reword += info[i][0]
        day += 1


print(reword)

Submission status: Wrong Answer

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

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

now = 0
ret = 0
for i in range(N):
    if now + re[i][0] <= M:
        ret += re[i][1]
        now += 1
    if now >= M:
        break

print(ret)

Submission status: Wrong Answer

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


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    Q = defaultdict(list)
    for a, b in zip(A, B):
        heapq.heappush(Q[a], -b)
    res = 0
    q = []
    for i in range(1, M+1):
        r = min(len(Q[i]), M-i+1)
        q = list(heapq.merge(q, Q[i][:r]))
        if len(q) == 0:
            continue
        v = heapq.heappop(q)
        res -= v
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())

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


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

AB = sorted(AB, key=lambda x: x[1])
AB = AB[::-1]

ans = 0
flag = False
for i in range(M+1, 0, -1):
    c = 0
    # print('c = ' + str(c) + ' ans' + str(ans))
    while True:
        _l = len(AB)
        # print('    {0} {1}'.format(AB, ans))
        if c > _l-1:
            flag = True
            break
        if AB[c][0] < i:
            ans += AB[c][1]
            AB.pop(0)
            break
        else:
            pass
        AB.pop(0)
        c += 1


print(ans)