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 collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

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


def merge(a, b, m):
    # return sorted(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 ia < 0:
            res[j] = b[ib]
            ib -= 1
            continue
        if ib < 0:
            res[j] = a[ia]
            ia -= 1
            continue
        if a[ia] > b[ib]:
            res[j] = a[ia]
            ia -= 1
            # if ia < 0:
            #     return b[:m - j] + res[j:]
            # while True:
            #     j -= 1
            #     if j < 0:
            #         break
            #     res[j] = b[ib]
            #     ib -= 1
            # return res
        else:
            res[j] = b[ib]
            ib -= 1
            # if ib < 0:
            #     return a[:m - j] + res[j:]
            # while True:
            #     if j < 0:
            #         break
            #     res[j] = a[ia]
            #     ia -= 1
            # return res
    return res


# print(merge([1], [1, 2, 3], 3))
# print(merge([1], [1, 2, 3], 1))
# print(merge([1], [1, 2, 3], 5))


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

    qq = []
    # q = []

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) == 0:
            if len(qq) == 0:
                pass
            else:
                res += qq[-1].pop()
                if len(qq[-1]) == 0:
                    qq.pop()
        else:
            if len(qq) == 0:
                res += current.pop()
                if len(current) != 0:
                    qq = [current]
            else:
                if qq[-1][-1] > current[-1]:
                    res += qq[-1].pop()
                    if len(qq[-1]) == 0:
                        qq.pop()
                    qq.append(current)
                    qq.sort(key=lambda a: a[-1])
                else:
                    res += current.pop()
                    if len(current) != 0:
                        qq.append(current)
                        qq.sort(key=lambda a: a[-1])
        # 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 = merge(q, current, 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())
AB = [[0,0]]* N
for i in range(N):
    AB[i] = list(map(int,input().split()))


AB = sorted(AB,key= lambda x:x[1],reverse=True)
reward = 0
AB = sorted(AB[:M],reverse = True) + AB[M:]
while(1):
    if M == 0 or len(AB) == 0:
        break
    if AB[0][0] > M:
        AB.pop(0)
        AB = sorted(AB[:M],reverse = True) + AB[M:]
        continue
    else:
        reward += AB[0][1]
        AB.pop(0)
        M = M - 1

print(reward)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

A=[]
B=[]
for i in range(N):
	a, b = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7
	A.append([a,b])

B = sorted(A, key=lambda x:(-x[1],-x[0]))

X=[0]*(M+1)

p("A ",A)
p("B ",B)
p("X ",X)


l = 1
r = M+1
#for L in B:
#	d = L[0]
#	m = L[1]
#	
#	z=r
#	for i in range(l+d-1, r):
#		if X[i]==0:
#			l = min(l, i)
#			X[i]=m
#			z=r
#			break
#		
#		z=min(i,z)
#
#	r=min(z,r)
#			
#
#p("X ",X)

print( sum(X) )

Submission status: Wrong Answer

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

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

AB_list = sorted(AB_list)

schedule = [0]*(M+1)
day = 0
hold_joblist = [0]

#どう考えてもTLE
for i in range(N):
    if day < AB_list[i][0]:
        day = AB_list[i][0]
        if M < day:
            break
    if schedule[day] == 0:
        if hold_joblist[0] < AB_list[i][1]:
            schedule[day] = AB_list[i][1]
        else:
            schedule[day] = hold_joblist.pop(0)
            if hold_joblist[0] < AB_list[i][1]:
                hold_joblist.insert(0,AB_list[i][1])
            else:
                index = bisect.bisect_left(hold_joblist,AB_list[i][1])
                hold_joblist.insert(index,AB_list[i][1])
    elif schedule[day] < AB_list[i][1]:
        if hold_joblist[0] < schedule[day]:
            hold_joblist.insert(0,schedule[day])
        else:
            index = bisect.bisect_left(hold_joblist,schedule[day])
            hold_joblist.insert(index,schedule[day])
        schedule[day] = AB_list[i][1]
    else:
        if hold_joblist[0] < AB_list[i][1]:
                hold_joblist.insert(0,AB_list[i][1])
        else:
            index = bisect.bisect_left(hold_joblist,AB_list[i][1])
            hold_joblist.insert(index,AB_list[i][1])

for i in range(day+1,M+1):
    if hold_joblist:
        schedule[i] = hold_joblist.pop(0)
    else:
        break

print(sum(schedule))

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, earn = 0, 0
    while now != m:
        for days, value in ab:
            if now + days <= m:
                earn += value
                now += 1
    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
ans2 = 0

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

dp = [[0 for i in range(m+1)] for j in range(n+1)]

for i in range(n-1, -1, -1):
    for j in range(m+1):
        if j < a[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-1]+b[i])
print(dp[0][m])

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().split()]
AB_list = sorted([input().split() for _ in range(N)], key=lambda x: -1 * int(x[0]))
filtered_AB_list = []
cnt = 0
maxA = M
for AB in AB_list:
    if (int(AB[0]) > maxA): continue
    elif (int(AB[0]) <= maxA):
        maxA -= 1
        cnt += 1
sorted_AB_list = sorted(AB_list, key=lambda x: -1 * int(x[1]))
# print(sorted_AB_list)
ans = 0
for AB in sorted_AB_list[:cnt]:
    ans += int(AB[1])
print(ans)

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 M >= a:
			ab.append((a,b))

	aa = sorted(ab, key=lambda x:(-x[1],x[0]))
	aa_tmp = []
	aa_dict = {}
	cnt = 0

	ind = [j for j in range(M,0,-1)]

	for i,val in enumerate(aa):
		a,b = val
		if a in aa_dict:
			tmp = aa_dict[a]
			if tmp + 1 > ind[a-1]:
				continue
			aa_dict[a] += 1
			aa_tmp.append(val)

			if len(aa_tmp) == M:
				break
		else:
			aa_dict[a] = 1
			aa_tmp.append(val)

			if len(aa_tmp) == M:
				break

	ans = 0
	for i in aa_tmp:
		a,b = i
		ans += b
	print(ans)

'''
	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:
				cnt[a] -= 1
				ans += b
				aa.pop(j)
				#print(aa)
				break
			else:
				aa.pop(j)
				'''

	#print(ans)

if __name__ == "__main__":
	main()

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)

result = 0
index = 1
for j in range(len(info)):
    if info[j][0] <= index:
      #print(info[j], i)
      result += info[j][1]
      index += 1
    if index == M+1:
      break
print(result)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
ab = []
for i in range(N):
    A[i], B[i] = map(int, input().split())
    ab.append([A[i], B[i]])

ab.sort()
i = N
ans = 0
nums = []
while 1 <= i:
    if M <= -1:
        nums.sort()
        nums.reverse()
        if nums[-1] < ab[i-1][1]:
            nums.pop()
            nums.append(ab[i-1][1])
    if M >= 0:
        if ab[i-1][0] <= M:
            #ans += ab[i-1][1]
            nums.append(ab[i-1][1])
        else:
            while ab[i-1][0] > M:
                i -= 1
                if i - 1 < 0:
                    break
                #ans += ab[i-1][1]
                nums.append(ab[i-1][1])
    i -= 1
    M -= 1
# print(ab)
print(sum(nums))

Submission status: Wrong Answer

Solution code:
import sys

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

#tasks = [[] for i in range(11)]
tasks = [[] for i in range(10002)]
for n in range(N):
	A,B = map(int,input().split())
	tasks[B].append(A)
for t in tasks:
	t.sort(reverse=True)
#print(tasks,file=sys.stderr)

ans = 0
gain = len(tasks)-1
while 1<=gain:
	#print('gain={} trials={}  tasks:{}'.format(gain,M,tasks[gain]))
	for day in tasks[gain]:
		if day<=M:
			#print('\t get! {}'.format(day))
			ans += gain
			M -= 1
	gain -= 1
print(ans)

Submission status: Wrong Answer

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


AB = sorted(AB,key= lambda x:x[1],reverse=True)
reward = 0
AB = sorted(AB[:M],reverse = True) + AB[M:]
while(1):
    if M == 0 or len(AB) == 0:
        break
    if AB[0][0] > M:
        AB.pop(0)
        continue
    else:
        reward += AB[0][1]
        AB.pop(0)
        M = M - 1

print(reward)

Submission status: Wrong Answer

Solution code:
import numpy as np
[N,M] = list(map(int,input().split()))

A = []
B = []
d = [[] for i in range(10**4)]
for i in range(N):
    [An,Bn] = list(map(int,input().split()))
    d[Bn-1].append(An)
for i in range(10**4):
    d[i].sort()

output = 0

t = M
now = len(d)-1
flag = 0

while flag ==0:
    if len(d[now])==0:
        now += -1
    elif len(d[now])>0:
        if d[now][-1]<=t:
            output += now+1
            t += -1
            d[now].pop()
        elif d[now][-1]>t:
            d[now].pop()
    if (now<0)or(t<=0):
        flag = 1

print(output)

Submission status: Wrong Answer

Solution code:
import collections
N,M=map(int,input().split())
A,B=[],[]
#hi_re=collections.defaultdict(list)
for i in range(N):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
#    hi_re[a].append(b)

used=set()

def search_best(hi):
    best=0
    best_i=-1
    for i in range(N):
        if i not in used:
            if A[i] <= hi:
                if best < B[i]:
                    best=B[i]
                    best_i=i
    
    if best_i >= 0:
        return best, best_i
    else:
        return 0, -1

dp=[0]*(M+1)
res=list()

for i in range(1,M+1):
#    res.extend(hi_re[i])
#    print(res)
    """
    if len(res) != 0:
        m = max(res)
        dp[i]=dp[i-1]+m
        res.remove(m)
    else:
        dp[i]=dp[i-1]
    """

    best,best_i = search_best(i)
    print(str(i)+' '+str(best))
    if best < 0:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1] + best
        used.add(best_i)


print(dp[M])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, insort
import sys
input = sys.stdin.readline

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

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

s = []
ret = 0
for a, b in AB :
    # print(a, b, s)
    # print(a, M - a + 1, len(s) - bisect_left(s, a))
    l = bisect_left(s, a)
    if M - a + 1 > len(s) - bisect_left(s, a) :
        insort(s, a)
        ret += b
        # print('add', b)
        if len(s) == M :
            break
        
print(ret)

Submission status: Wrong Answer

Solution code:
def f(a, n, m):
    sum = 0
    cnt = 0
    for i in range(len(a)):
        if (cnt + a[i][0] <= m):
            sum += a[i][1]
            cnt += 1
        if (cnt == m + 1):
            break
    return sum


n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    if (x <= m): a.append((x, y))
b = sorted(sorted(a, key=lambda x: x[0], reverse=True), key=lambda x: x[1], reverse=True)
c = sorted(sorted(a, key=lambda x: x[1], reverse=True), key=lambda x: x[0], reverse=True)
d = sorted(sorted(a, key=lambda x: x[0]), key=lambda x: x[1] )
e = sorted(sorted(a, key=lambda x: x[1]), key=lambda x: x[0])
ans = max(f(b, n, m), f(c, n, m), f(d, n, m), f(e, n, m))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int,input().split())

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

work = np.array(work)
sorted_work = work[np.argsort(work[:,1])[::-1]]

def wa(index):
    r = 0
    for i in range(index+1):
        r += avail[i]
    return r


avail = np.array([0 for i in range(M)])
ans = 0
for i in range(M):
    if i < N:
        index = M-sorted_work[i][0]
        if wa(index) <= index:
            ans += sorted_work[i][1]
            avail[index] += 1
            
print(ans)

Submission status: Wrong Answer

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

    # C = [[int(i) for i in input().split()] for i in range(N)]
    C = defaultdict(list)

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

        if A <= M:
            C[A].append(B)
    cnt = M
    ans = 0
    while cnt > 0:
        tmp = 0
        tmp_k = 0
        tmp_v = 0
        for k,v in list(C.items()):
            if k <= cnt:
                if v:
                    v_max = max(v)
                    if v_max and tmp <= v_max:
                        tmp = v_max
                        tmp_k = k
        if tmp_k:
            tmp_v = C.pop(tmp_k)
            tmp_v.remove(tmp)
            for j in tmp_v:
                C[tmp_k].append(j)
        ans += tmp
        cnt -= 1
    
    print(ans)

    
  
main()

Submission status: Wrong Answer

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

li =[]
for i in range(n):
    num = input().split()
    tup = [int(num[0]),int(num[1])]
    li.append(tup)
    
li_sort = sorted(li, key = lambda x: (-x[0], -x[1]))

ans = [0 for i in range(m)]
ans_memo = m
date = li_sort[0][0]

for i in range(n):
    if (li_sort[i][0] > m):
        continue
    
    if (li_sort[i][0] > ans_memo):
        continue
    
    else:
        if ans[0] == 0:    
            ans[0] = li_sort[i][1]
            if li_sort[i-1][0] == li_sort[i][0]:
                ans_memo -= 1
            else:
                ans_memo = m
        else:
            ans.sort()
            if ans[0] <= li_sort[i][0]:
                ans[0] = li_sort[i][1]
            ans_memo -= 1
            

            
print(sum(ans))   

"""
3 4
4 3
4 1
2 2
"""

Submission status: Wrong Answer

Solution code:
import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    a_list_1 = a_list_1[:k + 1]
    a_list_2 = a_list_2[:k + 1]
    if k >= 0:
        l = len(a_list_2) - list(reversed(a_list_2)).index(max(a_list_2)) - 1
        if l < len(a_list_2):
            if a_list_1[l] <= m - i:
                ans += a_list_2[l]
                del a_list_1[l], a_list_2[l]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
ba = [None] * n
for i in range(n):
    a, b = map(int, input().split())
    ba[i] = [b, a]
ba.sort(reverse=True)
li = [[i] for i in range(m)]
ans = 0
for i in range(n):
    b, a = ba[i]
    if m - a < 0 or li[m - a][0] == -1:
        continue
    if m - a > 0:
        t = li[m - a][0] - 1
        li[m - a] = li[t] if t > -1 else [-1]
        if li[m - a][0] > -1:
            ans += b
    else:
        li[m - a] = [-1]
        ans += b
print(ans)

Submission status: Wrong Answer

Solution code:
a=[]
n,m=map(int,input().split())
for i in range(n):
	x,y=map(int,input().split())
	a.append([x,y])
a.sort(key=lambda x:(-x[1],-x[0]))
ans=0
k=1
b=m
e=1
for i in range(n):
	if a[i][0]<=b-k+1:
		ans+=a[i][1]
		e+=1
		k=(max(k+1,e))	
print(ans)

Submission status: Wrong Answer

Solution code:

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    mix_list = [[a, b] for a, b in zip(A, B)]
    #mix_list = sorted(mix_list, key = lambda x: x[0])
    A = [a for a, b in mix_list]
    B = [b for a, b in mix_list]
    dp = [[0 for i in range(N)] for j in range(M)]
    for i in range(M):
        if A[0] <= (i+1):
            dp[i][0] = B[0]
    for j in range(1, N):
        if A[j] <= 1:
            dp[0][j] = max(B[j], dp[i][j-1])
    for i in range(1, M):
        for j in range(1, N):
            if A[j] <= (i+1):
                dp[i][j] = max(B[j]+dp[i-1][j-1], dp[i][j-1])
            else:
                dp[i][j] = dp[i][j-1]
    print(dp[M-1][N-1])
    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:
import sys
from collections import Counter
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A.sort(key=lambda x:x[0])
A.sort(key=lambda x:x[1], reverse=True)
check = []
counter = 0
ans = 0
for i in range(M,0,-1):
    check.append(i)

for i in range(N):
    try:
        if check[A[i][0]-1] > 0:
            ans += A[i][1]
            check[A[i][0]-1] -= 1
            counter += 1
    except:
        continue
    if counter == M:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

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

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

idx = 0
available = []
ans = 0
for d in range(1, M + 1):
    # print("d:{}, idx:{}".format(d, idx))
    while idx < N and AB[idx][0] <= d:
        available.append(AB[idx])
        if idx < N - 1 and AB[idx + 1][0] <= d:
            idx += 1
        else:
            break

    available = sorted(available, key=lambda x: x[1])
    if len(available) != 0:
        ans += available[-1][1]
        del available[-1]
        idx += 1

        # available[len(available)-1] = None

    # print(available[len(available) - 1])

print(ans)
pass

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
ab = []
for i in range(N):
    A[i], B[i] = map(int, input().split())
    ab.append([A[i], B[i]])

ab.sort()
i = N
ans = 0
nums = []
while 1 <= i:
    if M <= 0:
        nums.sort()
        nums.reverse()
        if nums[-1] < ab[i-1][1]:
            nums.pop()
            nums.append(ab[i-1][1])
    if M >= 1:
        if ab[i-1][0] <= M:
            #ans += ab[i-1][1]
            nums.append(ab[i-1][1])
        else:
            while ab[i-1][0] > M:
                i -= 1
                if i - 1 < 0:
                    break
                #ans += ab[i-1][1]
                nums.append(ab[i-1][1])
    i -= 1
    M -= 1
# print(ab)
print(sum(nums))

Submission status: Wrong Answer

Solution code:
import heapq
from copy import deepcopy
N, M = map(int, input().split())
seed = []
heapq.heapify(seed)

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

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

count = 0
for i, a in enumerate(A):
    if len(a) == 0:
        continue
    num = heapq.heappop(A[i])
    count += num
    if i < M-1:
        A[i+1] += A[i]

print(-count)

Submission status: Wrong Answer

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

AB.sort(key=lambda x:-x[1])
cnt = 0
a, b = AB[0]
AB = AB[1:]
pre = a
day=0
if a > M:
  print(0)
  exit()
cnt += b
while True:
  pre, a = max(AB, key = lambda x: x[0] != pre)
  AB.pop(AB.index([pre, a]))
  if pre+day > M:
    break
  cnt += a
  day += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
[N,M] = list(map(int,input().split()))

A = []
B = []
d = [[] for i in range(10**5)]
for i in range(N):
    [An,Bn] = list(map(int,input().split()))
    d[Bn-1].append(An)
for i in range(10**5):
    d[i].sort()

output = 0

t = M
now = len(d)-1
flag = 0

while flag ==0:
    if len(d[now])==0:
        now += -1
    elif len(d[now])>0:
        if d[now][-1]<=t:
            output += now+1
            t += -1
            d[now].pop()
        elif d[now][-1]>t:
            d[now].pop()
    if (now<0)or(t<=0):
        flag = 1

print(output)

Submission status: Wrong Answer

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

li =[]
for i in range(n):
    num = input().split()
    tup = [int(num[0]),int(num[1])]
    li.append(tup)
    
li_sort = sorted(li, key = lambda x: (-x[0], -x[1]))

ans = [0 for i in range(m)]
ans_memo = m
date = li_sort[0][0]

for i in range(n):
    if (li_sort[i][0] > m):
        continue
    
    if (li_sort[i][0] > ans_memo):
        continue
    
    else:
        if ans[0] == 0:    
            ans[0] = li_sort[i][1]
            if li_sort[i-1][0] == li_sort[i][0]:
                ans_memo -= 1
            else:
                ans_memo = m
        else:
            ans.sort()
            if ans[0] <= li_sort[i][0]:
                ans[0] = li_sort[i][1]
            ans_memo -= 1
            

            
print(ans)   

"""
3 4
4 3
4 1
2 2
"""

Submission status: Wrong Answer

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

print(sum(list(map(lambda x:x[1],ab_s))[0:m]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
job = []
for i in range(n):
    a, b = map(int, input().split())
    if n >= m:
        job.append([b, a])
    else:
        job.append([a, b])
list.sort(job, reverse=True)

a = 0
if n >= m:
    d = 0
    for j in job:
        if d + j[1] <= m:
            a = a + j[0]
        d = d + 1
else:
    d = 0
    for j in job:
        if d + j[0] <= m:
            a = a + j[1]
        d = d + 1
print(a)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

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

#####

line = sorted(ori_line, key=itemgetter(0, 1), reverse=True)

# print(line)

res=m   #残り日数
c=0
flag=True
while res>0 and line!=[]:
    if line[0][0] <= res:
        c+=line[0][1]
        flag=True   #働いて1日消費
        line.pop(0)
    else:
        line.pop(0)
        flag=False   #働かない
    if flag:
        res-=1
    # print(line,res,c)

#####

line = sorted(ori_line, key=itemgetter(1, 0), reverse=True)

# print(line)

res=m   #残り日数
d=0
flag=True
while res>0 and line!=[]:
    if line[0][0] <= res:
        d+=line[0][1]
        flag=True   #働いて1日消費
        line.pop(0)
    else:
        line.pop(0)
        flag=False   #働かない
    if flag:
        res-=1
    # print(line,res,d)
    
print(max(c,d))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(str,input().split())) for l in range(n)]
ab_s=sorted(ab,key=lambda x:x[1],reverse=True)
ct=0
j=0
for i in range(int(m)):
    if j>=n:break
    if m>=int(ab_s[j][0]) and j==0:
        ct+=int(ab_s[j][1])
        #print(ct,ab_s[j],0)
        j+=1
    if m>=int(ab_s[j][0]) and j>0 and int(ab_s[j][0])!=int(ab_s[j-1][0]):
        ct+=int(ab_s[j][1])
        #print(ct,ab_s[j],1)
        j+=1
    if m>=int(ab_s[j][0]) and j>0 and int(ab_s[j][0])==int(ab_s[j-1][0]):
        if int(ab_s[j][0])+i+1<=m:
            ct+=int(ab_s[j][1])
            j+=1
        else:j+=1
    else:break
print(ct)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def main():
    n,m = map(int,input().split())
    dc = defaultdict(list)

    for _ in range(n):
        a,b = map(int,input().split())
        dc[a].append(b)
    for i in dc.keys():
        dc[i].append(0)
    for i in dc.keys():
        dc[i] = sorted(dc[i])
    ls = sorted(dc.items())
    ls_lenth = len(ls)
    now = 1
    ans = 0
    i = 0
    j = 0
    while now <= m:
        j = i 
        now_max = 0
        if ls[i][0]> now:
            now += 1
        else:
            while 1:
                if j == ls_lenth:
                    break
                if ls[j][0]>now:
                    break
                if now_max<ls[j][1][-1]:
                    now_max = ls[j][1].pop()
                j+=1
            ans += now_max
            now_max = 0
            now +=1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def sol():
    n,m=map(int,input().split())
    d=[]
    ans=[0]*(m+1)
    t=0
    x,y=1,m
    for i in range(n):
        a,b=map(int,input().split())
        d.append((b,-a))
    d.sort(reverse=True)
    for bb,aa in d:
        aa*=-1
        if max(x,aa)==y:
            ans[y]=1
            t+=bb
            y-=1
        else:
            for j in range(max(x,aa),y+1):
                if ans[j]==0:
                    ans[j]=1
                    t+=bb
                    if j==x: x+=1
                    if j==y: y-=1
                    break

    print(t)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def f(a, n, m):
    sum = 0
    cnt = 0
    for i in range(len(a)):
        if (cnt + a[i][0] <= m):
            sum += a[i][1]
            cnt += 1
        if (cnt == m + 1):
            break
    return sum


n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    if (x <= m): a.append((x, y))
b = sorted(sorted(a, key=lambda x: x[0], reverse=True), key=lambda x: x[1], reverse=True)
c = sorted(sorted(a, key=lambda x: x[1], reverse=True), key=lambda x: x[0], reverse=True)
d = sorted(sorted(a, key=lambda x: x[0]), key=lambda x: x[1], reverse=True)
e = sorted(sorted(a, key=lambda x: x[1], reverse=True), key=lambda x: x[0])
ans = max(f(b, n, m), f(c, n, m), f(d, n, m), f(e, n, m))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int,input().split())
days=np.zeros(N).astype('int8')
prices=np.zeros(N).astype('int8')
for i in range(N):
    a,b = map(int,input().split())
    days[i]=a
    prices[i]=b

ans = 0
for i in range(1,M+1):
    temp = prices.copy()
    temp[days>i] = 0
    if temp.sum()>1:
        pos = np.argmax(temp)
        ans+=prices[pos]
        prices[pos]=0
        
print(ans)