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: Runtime Error

Solution code:

N,M = map(int,input().split())
#k,x = map(int,input().split())

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

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

scadule = [0]*M

m=len(BA)

while i < m:
    work = BA[i]
    i+=1
    try:
        day = scadule[work[0]-1:].index(0)
        scadule[day+work[0]-1] = work[1]
    except:
        BA = BA[:i+1]+[x for x in BA[i+1:] if x[0] >= work[0]]
        m=len(BA)
        continue

ans=sum(scadule)

print(str(ans))

Submission status: Runtime Error

Solution code:
n,m = [int(s) for s in input().split()]
j = []
for i in range(n):
    ai,bi = [int(s) for s in input().split()]
    j.append([ai,bi])

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

r = 0
fl = []
for i in range(m):
    for x in range(m):
        if j[x][0] <= i+1 and x not in fl:
            r += j[x][1]
            fl.append(x)
            break

print(r)

Submission status: Runtime Error

Solution code:
a,b=map(int, input().split())
e = [(int(i) for i in input().split()) for i in range(a)] 
e.sort(reverse=True)

count = 0

for i in range(a):
    if e[i][0] <= b:
        b -= 1
        count += e[i][1]
        
print(count)

Submission status: Runtime Error

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

ans = 0

for i in range(M):
    if i == 0:
        j = 0
    while box[j][0] > M - i:
        j += 1
        if j >= N-1:
            break
    else:
        ans += box[j][1]
        j += 1
        if j >= N-1:
            break

print(ans)

Submission status: Runtime Error

Solution code:
N,M = [int(i) for i in input().split()]
AB = []
for n in range(N):
    temp = [int(i) for i in input().split()]
    if temp[0] <= M:
        AB.append(temp)
from collections import deque
#works = sorted(AB,key=lambda x:(-x[1],x[0],))
works = deque(works)
work_schedule = [0]*M
for w in range(len(works)):
    work = works.popleft()
    if work[0] > M:
        pass
    else:
        cnt = 0
        while True:
            if (work[0]-1+cnt) >= M:
                break
            elif work_schedule[work[0]-1+cnt]  == 0:
                work_schedule[work[0]-1+cnt] = work[1]
                break
            else:
                cnt+=1
print(sum(work_schedule))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
work_list = [list(map(int, input().split())) for i in range(n)]
work_list.sort()
ans = 0
max_f, max_f2 = 0, 0
p = 0
p_max, p_max2 = -1, -1
flg = False
for i in range(1, m+1):
  while p<len(work_list) and work_list[p][0]<=i:
    if max_f<work_list[p][1]:
      p_max, p_max2 = p, p_max
      max_f, max_f2 = work_list[p][1], max_f
      flg = True
    elif max_f2<work_list[p][1]:
      p_max2 = p
      max_f2 = work_list[p][1]
    p += 1
  if flg:
    p -= 1
    ans += max_f
    if p_max>=0:
      _ = work_list.pop(p_max)
    max_f = max_f2
    if p_max2>=p_max:
      p_max = p_max2-1
    else:
      p_max = p_max2
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

AB.sort(reverse = True, key = lambda x:x[1])
ans = 0
for i in range(1, M + 1):
  for j in range(len(AB)):
    if AB[j][0] <= i:
      ans += AB.pop(j)[1]
      break
    if AB[j][0] > M:
      AB.pop(j)

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
l=[list(map(int,input().split())) for i in range(N)]
l_1=sorted(l,key=lambda l:l[1],reverse=True)
l_2=[0]*(M+N)
d=0
for i in range(N):
    if d+l_1[i][0]<=M:
        l_2[d+l_1[i][0]]+=l_1[i][1]
        del l_1[i]
        d+=1
    else:
        break
l_3=sorted(l_1, key=lambda l_1:(l_1[0],-l_1[1]))
for i in range(N):
    if d+l_3[i][0]<=M:
        l_2[d+l_1[i][0]]+=l_3[i][1]
        d+=1
    else:
        break 
print(sum(l_2))

Submission status: Runtime Error

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

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

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

scadule = [0]*M

while i < len(BA):
    work = BA[i]
    try:
        day = scadule[work[0]-1:].index(0)
        scadule[day+work[0]-1] = work[1]
    except:
        BA = BA[:i+1]+[x for x in BA[i+1:] if x[0] >= work[0]]
        continue

ans=sum(scadule)

print(str(ans))

Submission status: Runtime Error

Solution code:
n,day=map(int,input().split())
daylist=[0 for i in range(n)]
money=[0 for i in range(n)]
hima=[0 for i in range(day)]
sum=0
for i in range(n):
  d,m=map(int,input().split())
  daylist[i]=d
  money[i]=m
for j in range(n):
  which=money.index(max(money))
  howlong=daylist[which]
  when=day-howlong
  while((hima[when]==1)and(when>=0)):
    when-=1
  if(when!=-1):
    hima[when]=1
    sum+=max(money)
    money[which]=0
print(sum)

Submission status: Runtime Error

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

for i in range(len(AB)):
  if AB[i][0] > M:
    AB.pop(i)

AB.sort(reverse = True, key = lambda x:x[1])
ans = 0
for i in range(1, M + 1):
  for j in range(len(AB)):
    if AB[j][0] <= i:
      ans += AB.pop(j)[1]
      break

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ab = [[] for i in range(1,m+1)]
for i in range(n):
    a,b = map(int,input().split())
    ab[a].append(b)
ab = {i:sorted(ab[i],reverse=True) for i in ab}
print(ab)
ans = 0
for i in range(m)[::-1]:
    rem = m - i
    #print("rem=",rem,"ab[rem]=",ab[rem])
    mx = 0
    fl = -1
    for j in range(1,m-i+1):
        #print("j=",j)
        if ab[j] and mx < ab[j][0]:
            mx = ab[j][0]
            fl = j
            #print("fl=",fl)
    ans += mx
    if fl > 0: del ab[fl][0]
    #print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

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

work = [list(map(int,input().split())) for _ in range(N)]

wq = deque(sorted(work))

paytree = deque([])

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        bisect.insort_right(paytree,wq.popleft()[1])
    if len(paytree) > 0:
        ans += paytree.pop()

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
work_list = [list(map(int, input().split())) for i in range(n)]
work_list.sort()
ans = 0
max_f, max_f2 = 0, 0
p = 0
p_max, p_max2 = -1, -1
flg = False
for i in range(1, m+1):
  while p<len(work_list) and work_list[p][0]<=i:
    if max_f<work_list[p][1]:
      p_max, p_max2 = p, p_max
      max_f, max_f2 = work_list[p][1], max_f
      flg = True
    elif max_f2<work_list[p][1]:
      p_max2 = p
      max_f2 = work_list[p][1]
    p += 1
  if flg:
    p -= 1
    ans += max_f
    if p_max>=0:
      _ = work_list.pop(p_max)
    max_f = max_f2
    if p_max2>p_max:
      p_max = p_max2-1
    else:
      p_max = p_max2
print(ans)

Submission status: Runtime Error

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

for i in range(N):
  if AB[i][0] > M:
    AB.pop(i)

AB.sort(reverse = True, key = lambda x:x[1])
ans = 0
for i in range(1, M + 1):
  for j in range(len(AB)):
    if AB[j][0] <= i:
      ans += AB.pop(j)[1]
      break

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dp = [[0 for i in range(M+1)] for j in range(N+1)]
l = [0 for i in range(N)]
for i in range(N):
    A,B = map(int, input().split())
    l[i] = [-A, -B]
l.sort()
tmp = 1
for n in range(1, N+1):
    for m in range(tmp):
        if -l[n-1][0]  + m <= M:
            dp[n][m] = max(dp[n][m], dp[n-1][m-1] - l[n-1][1])
            tmp += 1
        dp[n][m-1] = max(dp[n][m-1], dp[n-1][m-1])
print(max(dp[N]))

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
n, m = map(int, input().split())

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

jobs = np.array(sorted(baito, key=lambda x: x[0]))
day = jobs[:, 0]
pay = jobs[:, 1]

kane = 0
for i in range(1, m+1):
    pos = bisect.bisect_right(day, i)
    if pos == 0:
        continue
    ind = pay[:pos].argmax()
    kane += pay[ind]
    pay[ind] = 0


print(kane)

Submission status: Runtime Error

Solution code:


 
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
 
ab.sort()
ab.append([1000000,0])
 
t = 0
x = []
ans = 0

bi = bisect.bisect_left
xi = x.insert
xp = x.pop

for i in range(1,m+1):
    while True:
        if ab[t][0] > i:
            break
        index = bi(x, ab[t][1])
        xi(index, ab[t][1])
        t += 1
    
    if len(x) != 0:
        ans += xp(len(x) - 1)
 
print(ans)

Submission status: Runtime Error

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

result = 0

ls = []

ls_ap = ls.append

for i in range(N):
    tmp = list(map(int, input().split()))
    ls_ap(tmp)
    if tmp[0] > M:
        del ls[i]

if not len(ls) == 0:

    ls.sort(reverse = True, key = lambda x:x[0])
    
    ls.sort(reverse = True, key = lambda x:x[1])
    
    log_max = 0
    log_max_m = 0
    sum_day_max = int(M * (M + 1) / 2)
    
    for i in range(M):
        if log_max_m + ls[0][0] < sum_day_max:
            log_max_m += ls[0][0]
            log_max += ls[0][1]
            del ls[0]
        else:
            for j in range(1, len(ls)):
                if log_max_m + ls[j][0] < sum_day_max:
                    log_max_m += ls[j][0]
                    log_max += ls[j][1]
                    del ls[j]
                    break
else:
    log_max = 0
print(log_max)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
e = [[int(i) for i in input().split()] for i in range(n)] 
se = sorted(e,key=lambda l:l[1],reverse=True)
sse = sorted(se,key=lambda l:l[0])
print(sse)
ans = 0
for day in range(m):
  max = 0
  for i in range(len(sse)):
    if sse[i][1]>sse[max][1]:
      max = i
    if sse[i][0] > day+1:
      break
  ans+=sse[max][1]
  del sse[max]
print(ans)

Submission status: Runtime Error

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()
        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()
                    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: Runtime Error

Solution code:
N,M = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(N)]
maxval = 0
for i in arr:
        if i[0] > maxval:
                maxval = i[0]
tmp= [[0 for i in range(1)] for j in range(maxval + 2)]

for i in arr:
        tmp[i[0]].append(i[1])

ans = 0
tmpmax = 0
tgt = 0
for remday in range(1, M + 1):
        for idx,val in enumerate(tmp):
                if idx == 0:
                        continue
                if idx <= remday:
                        if max(val) > tmpmax:
                                tmpmax = max(val)
                                tgt = idx
                else:
                        ans += tmpmax
                        tmpmax = 0
                        del tmp[tgt][-1]
                        break
        else:
                ans += tmpmax
                tmpmax = 0
                del tmp[tgt][-1]
                break

print(ans)

Submission status: Runtime Error

Solution code:
n,limit=[int(i) for i in input().split()]
baitolist=[[int(i) for i in input().split()] for j in range(n)]
baitodict={}
for i in range(1,limit+1):
    baitodict[str(i)]=[]
for baito in baitolist:
    if int(day)<=limit:
        day=str(baito[0])
        money=baito[1]
        baitodict[day].append(money)
        baitodict[day].sort()
# print(baitodict)

sumnum=0
for i in range(1,limit+1):
    maxindex=""
    maxmoney=0
    for j in range(1,i+1):
        if baitodict[str(j)]!=[]:
            a=baitodict[str(j)][-1]
            if maxmoney<a:
                maxmoney=a
                maxindex=str(j)
    if maxindex!="":
        baitodict[maxindex].pop()
    sumnum+=maxmoney
#     print(sumnum)
print(sumnum)

Submission status: Runtime Error

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],reverse=True)
ans =0
cnt = 0
i = 0
daylist = [i+1 for i in range(M)]
while i<N:
    d = AB[i][0]
    if d > M:continue
    if daylist[d] > 0 and cnt < M:
        daylist[d] = daylist[d]-1
        ans += AB[i][1]
        cnt += 1
    i += 1
print(ans)

Submission status: Runtime Error

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

def total_money(bs, m, m_max):
    m = min(m, m_max)
    if m == 1:
        mx = 0
        for i in reversed(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    max_tmp  = 0
    for i in reversed(range(m)):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            if tmp > max_tmp:
                max_tmp = tmp
                bs[i] = bs[i][1:]
                subtotal = total_money(bs, m-1, i+1)
                if tmp+subtotal > mx:
                    mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
n, m = map(int, input().split())

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

jobs = np.array(sorted(baito, key=lambda x: x[0]))
day = jobs[:, 0]
pay = jobs[:, 1]

kane = 0
for i in range(1, m+1):
    pos = bisect.bisect_right(day, i)
    if pos == 0:
        continue
    ind = pay[:pos].argmax()
    kane += pay[ind]
    pay[ind] = 0


print(kane)

Submission status: Runtime Error

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]
	
	
	for i in range(l+d-1, r):
		if X[i]==0:
			l = min(l, i)
			X[i]=m
			break
		
	else:
		r = (l+d-1)+1


			

p("X ",X)

print( sum(X) )

Submission status: Runtime Error

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,reverse=True)
ans = 0
for i in range(N):
  for j in range(N):
    if i+job_list[j][0] <= M:
      tmp = max(job_list,key=itemgetter(1))
      if job_list[j] == tmp or (job_list[j][0]!=tmp[0] and job_list[j][1]>=tmp[1] and i+tmp[0]>M):
        ans += job_list[j][1]
        job_list.remove(job_list[j])
        break
print(ans)

Submission status: Runtime Error

Solution code:
N, M= map(int, input().split())
B=[]
for i in range(N):
    B.append([None]*2)
    l=input().split()
    B[i][0]=int(l[1])
    B[i][1]=int(l[0])
B.sort(reverse=True)
h=[0]*(M+1)
a=0
d=M+1
for i in range(N):
    for j in range(B[i][1],d):
        if h[j]==0:
            h[j]=1
            a+=B[i][0]
            break
    else:
        d=B[i][1]
print(a)

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
N,M = map(int,input().split(' '))
AB = [[] for i in [0]*(M+1)]
for i in [0]*N:
	a,b = map(int,input().split(' '))
	if a <= M:
		AB[a].append(b)

ans = 0
cand = deque([])
for i in range(1,M+1):
	for b in AB[i]:
		bisect.insort(cand,b)
	if not len(cand) == 0:
		ans += cand.pop()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
a = sys.stdin.readlines()

n = int(a[0])
ans = 0
now = 2

for i in range(1,n+1,1):
    for j in range(now,n+1,1):
        if sorted(a[i]) == sorted(a[j]):
            ans += 1
    now += 1

print(ans)

Submission status: Runtime Error

Solution code:
n ,m = map(int,input().split())
a = [list(map(int, input().split())) for i in range(n)]
a = sorted(a)
che = []
ans = 0
for i in range(1,m+1):
    count = 0
    for k in range(len(a)):
        k -= count
        if a[k][0] <= i:
            che.append(a.pop(k)[1])
            count += 1
        else:
            break;
    if len(che) > 0:
        ans += che.pop(max(che))
print(ans)

Submission status: Runtime Error

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])
        j+=1
    if m>=int(ab_s[j][0]) and j>0 int(ab_s[j][0])!=int(ab_s[j-1][0]):
        ct+=int(ab_s[j][1])
        j+=1
    elif m>=int(ab_s[j][0]) and j>0 int(ab_s[j][0])==int(ab_s[j-1][0]):
        if int(ab_s[j][0])+i<=m:
            ct+=int(ab_s[j][1])
            j+=1
        else:j+=1
    else:break
print(ct)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
 
#define sorted(vector) sort(vector.begin(),vector.end())
#define vmin(vector) *min_element(vector.begin(),vector.end())
#define vmax(vector) *max_element(vector.begin(),vector.end())
#define vsum(vector) accumulate(vector.begin(),vector.end(),0)
#define append(a) push_back(a)
#define int(a) stoi(a)
#define str(a) to_string(a)
#define bisect_left(vector,a) lower_bound(vector.begin(),vector.end(),a)
#define bisect_right(vector,a) upper_bound(vector.begin(),vector.end(),a)

using namespace std;
long floatinf=-10000000;



int main(void){
    map<long,vector<long>> defaultdict;
    long n,m,p;
    long tmp1,tmp2,tmp3;
    cin>>n,m,p;
    
    for(int i=0  ;i<m  ;i++){
        cin>>tmp1>>tmp2>>tmp3;
        defaultdict[tmp1]={tmp2,tmp3};
    }
    vector<long> BELLMANFORD(long point, long d, long p);{
        vector<long long> cost=vector<long long>(n+1,-floatinf);
    }
    for(int i=0  ;i<n-1  ;i++){
        for(int j=0  ;j<n-1  ;j++){
            
        }
    }

Submission status: Runtime Error

Solution code:
def dfs(res, depth, path, A, B, time, M):
    res.append(path)
    for i in range(depth, len(A)):
        if time + A[i] <= M+1:
            dfs(res, i+1, path + [B[i]], A, B, time + 1, M)

N, M = map(int, input().split())
A, B = [], []
res = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dfs(res, 0, [], A, B, 0, M)
if res:
  print(sum(sorted(res, key=lambda x: sum(x))[-1]))
else:
  print(0)

Submission status: Runtime Error

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

a_b_list = []


for i in range(N):
    a, b = list(map(int, input().split()))
    if a <= M:
        a_b_list.append((a, b))

if len(a_b_list) == 0:
    print(0)
    sys.exit()


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

total_value = 0
memo_list = []
memo_index = len(sort_a_b_list) + 1000
for day in range(M, 0, -1):
    max_value = 0
    length = len(sort_a_b_list)
    j = 0
    memo_index = len(sort_a_b_list) + 1000
    while j <= length - 1:
        a_b = sort_a_b_list[j]
        if a_b[0] <= day:
            if max_value < a_b[1]:
                max_value = a_b[1]
                memo_index = j
        # if a_b[0] == day:
        #    memo_list.append(j)
        j += 1

    # memo_list.append(memo_index)
    # sort_a_b_list = [value for index, value in enumerate(sort_a_b_list) if index not in memo_list]
    if memo_index != len(sort_a_b_list) + 1000:
        sort_a_b_list.pop(memo_index)
    memo_list = []
    total_value += max_value

print(total_value)

Submission status: Runtime Error

Solution code:
n,d = list(map(int, input().split(" ")))

ws = []
for _ in range(n):
    l,r = list(map(int, input().split(" ")))
    if l <= d:
        ws.append((l,r))

wn = len(ws)

got = 0
chosen = []
for i in range(d):
    j = d-i
    candi_k = 0
    candi_r = 0
    candi_t = 0
    for k,(t,r) in enumerate(wn):
        if  t <= j and candi_t <= t and candi_r <= r and not k in chosen:
            candi_k = k
            candi_r = r
            candi_t = t
    chosen.append(candi_k)
    got += candi_r

print(got)

Submission status: Runtime Error

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

AB.sort()
B = [[] for _ in range(M + 2)]
i = 1
j = 0
while i <= M:
  while j < N or AB[j][0] <= i:
    B[i].append(AB[j][1])
    j += 1
  B[i] = B[i - 1].copy()
  i += 1

ans = 0
for i in range(1, M + 1):
  if len(B[i]) > 0:
    m = max(B[i])
    ans += m
    for j in range(i, M + 1):
      if len(B[j]) > 0:
        B[j].remove(m)

print(ans)

Submission status: Runtime Error

Solution code:

    n, m = map(int, input().split())
    a = []
    b = []
    ans = 0

    for _ in range(n):
        s = list(map(int, input().split()))
        a.append(s[0])
        b.append(s[1])

    lv = [a[i] * b[i] for i in range(len(a))]
    li = sorted(zip(lv, a, b), reverse=True)

    for i in range(m):
        for _ in range(len(li)):
            lab = li.pop(0)
            if lab[1] <= m - i:
                ans += lab[2]
                break

    print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n)]
abab = sorted(sorted(abab, key=itemgetter(0), reverse=True), key=itemgetter(1), reverse=True)

gyara = [0 for _ in range(m+1)]

def index(a) :
    if a > m:
        return m+1 
    if gyara[a] :
        return index(a+1)
    else :
        return a

for a, b in abab :
    i = index(a)
    if i <= m :
        gyara[i] = b

print(sum(gyara))

Submission status: Runtime Error

Solution code:
from math import factorial

n = int(input())
s = []
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    s.append(sin)

ss = set(s)
count = 0
for u in ss:
    al = s.count(u)
    count += factorial(u) / factorial(2) / factorial(u - 2))
print(count)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
# AB_s = [list(map(int,input().split())) for _ in range(N)]
dicts = {i:[] for i in range(1,M+1)}
for _ in range(N):
    A,B = map(int,input().split())
    if A in dicts:
        dicts[A].append(B)
answer = 0
wages = []
for i in range(1,M+1):
    wages.extend(dicts[i])
    if wages:
        wages.sort()
        if len(wages) > M-i:
            wages[M-i:] = []
        answer += wages.pop()
print(answer)
# AB_s = sorted(AB_s, key=lambda x:-x[0])
# print(AB_s)

Submission status: Runtime Error

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

w = [[] for _ in range(10001)]

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

money = 0
l = []
for i in range(m):
  l += w[i]
  if len(l) == 0:
    continue

  x = max(l)
  l.remove(x)
  money += x

print(money)

Submission status: Runtime Error

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

def total_money(bs, m):
    if m == 1:
        mx = 0
        for i in reversed(range(m)):
            if len(bs[i]) > 0:
                if bs[i][0] > mx:
                    mx = bs[i][0]
        return mx

    mx = 0
    max_tmp  = 0
    for i in reversed(range(m)):
        if len(bs[i]) > 0:
            tmp = bs[i][0]
            if tmp > max_tmp:
                max_tmp = tmp
                bs[i] = bs[i][1:]
                subtotal = total_money(bs, m-1)
                if tmp+subtotal > mx:
                    mx = tmp+subtotal
            bs[i].insert(0, tmp)
    return mx


def solve(N, M, A, B):
    # 下準備
    bs = [[]] * M
    for a,b in zip(A, B):
        if a <= M:
            bs[a-1] = sorted(bs[a-1] + [b], reverse=True)

    return total_money(bs, M)


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)