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())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])+[[-1,-1]]
for i in range(n):l[i][0]-=1
w=[0]*(m+1)
i=0
while i<n:
    j=l[i][0]
    s=j
    while l[i][0]==j:
        while w[s]>=l[i][1]:s+=1
        if s<m:w[s]=l[i][1]
        i+=1
print(sum(w))

Submission status: Runtime Error

Solution code:
import heapq
N,M = map(int,input().split())
days = [[] for _ in range(M + 1)]
for n in range(N):
	a,b = map(int,input().split())
	if a > M:
		continue
	days[a].append(-b)

total_reward = 0
q = []
for day in range(M + 1):
	this_day = days[day]
	for reward in this_day:
		heapq.heappush(q,reward)
	if len(q):
		total_reward -= heapq.heappop(q)
print(total_reward

Submission status: Runtime Error

Solution code:
import heapq
N,M = map(int,input().split())
days = [[] for _ in range(M + 1)]
for n in range(N):
	a,b = map(int,input().split())
	days[a].append(-b)

total_reward = 0
q = []
for day in range(M + 1):
	this_day = days[day]
	for reward in this_day:
		heapq.heappush(q,reward)
	if len(q):
		total_reward -= heapq.heappop(q)
print(total_reward)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<long,long>> work;
    long a,b;
    rep(i,n){
        cin >> a >> b;
        work.push_back(make_pair(b,a));
    }
    sort(work.begin(),work.end(),greater<pair<long,long>>());
    int cnt=0;
    int cnt2 = 0;
    long ans = 0;
    while(cnt<m && cnt2<n){
        if(work[cnt2].second+cnt<=m){
            cnt++;
            ans+=work[cnt2].first;
        }
        cnt2++;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int,input().split())
joblist = {}
for i in range(n):
    a,b = map(int,input().split())
    if a in joblist:
        joblist[a].append(-1*b)
    else:
        joblist[a] = [-1*b]

kouho = []
 
ans =0
 
for i in range(1,m+1):
    if i in joblist:
        for j in joblist[i]:
            heapq.heappush(kouho,j)
    
    ans += heapq.heappop(kouho)
 
print(-1*ans)

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

C, D = [], []
for c, d in sorted(zip(A,B), key=lambda x: x[0], reverse=True):
    C.append(c)
    D.append(d)
    
del A, B
    
dfs(res, 0, [], C, D, 0, M)
print(sum(sorted(res, key=lambda x: sum(x))[-1])) if res else print(0)

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:
            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)
C, D = [], []
for c, d in sorted(zip(A,B), key=lambda x: x[0], reverse=True):
	C.append(c)
	D.append(d)
    
dfs(res, 0, [], C, D, 0, M)
if res:
  print(sum(sorted(res, key=lambda x: sum(x))[-1]))
else:
  print(0)

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:
            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)
A, B = sorted(zip(A,B), key=lambda x: x[0])
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:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import heapq

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    ABs[A].append(-B)
heapq.heapify(ABs[0])

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            heapq.heappush(ABs[0], b)
    if len(ABs[0]) > 0:
        As -= heapq.heappop(ABs[0])
print(As)

Submission status: Runtime Error

Solution code:
def update(i, x):
    i += 1
    while i < m + 1:
        bit[i] += x
        i += i & -i

def get_sum(i):
    i += 1
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

n, m = map(int, input().split())
bit = [0] * (m + 1)
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: (-x[1], -x[0]))
cnt = 0
ans = 0
for a, b in ab:
    if a <= m:
        a = m - a
        if get_sum(a) < a + 1:
            update(a, 1)
            cnt += 1
            ans += b
    print(a,b,bit,get_sum(a))
    if cnt == m: break
print(ans)

Submission status: Runtime Error

Solution code:
import sys,heapq
input=sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AB=[list(map(int,input().strip().split())) for _ in range(N)]
AB.sort()
n=0
sumB=0
q=[]
for m in range(1,M+1):
    maxB=0
    while n<N and AB[n][0]<=m:
        heapq.heappush(q,-AB[n][1])
        n+=1
    sumB+=heapq.heappop(q)
    if len(q)==0: break
    
print(-sumB)

Submission status: Runtime Error

Solution code:
import sys,heapq
input=sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AB=[list(map(int,input().strip().split())) for _ in range(N)]
AB.sort()
print(AB)
n=0
sumB=0
q=[]
for m in range(1,M+1):
    maxB=0
    while n<N and AB[n][0]<=m:
        heapq.heappush(q,-AB[n][1])
        n+=1
    sumB+=heapq.heappop(q)
    if len(q)==0: break
    
print(-sumB)

Submission status: Runtime Error

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

C = [[0,0] * x for x in range(N)] 
for i in range(N):
  C[i] = list(map(int, input().split()))
C.sort(key=lambda x: (x[1], x[0]), reverse=True)
B =[0 * x for x in range(N)]

def max_fee(d, Li):
#  print (d, Li)
  if d == 0:
    return 0
  else:    
    while len(Li) > 0:
      m = Li.pop(0)
      if m[0]<= d:
        break
    else:
      return 0
    return m[1] + max_fee(d - 1, Li)
print (max_fee(M, C))

Submission status: Runtime Error

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

C = [[0,0] * x for x in range(N)] 
for i in range(N):
  C[i] = list(map(int, input().split()))
C.sort(key=lambda x: (x[1], x[0]), reverse=True)
B =[0 * x for x in range(N)]

def max_fee(d, Li):
#  print (d, Li)
  if d == 0:
    return 0
  else:
    D = [x for x in range(len(Li)) if Li[x][0] <= d]
    if len(D) == 0:
      return 0
    else:
      m = Li.pop(0)
      return m[1] + max_fee(d - 1, Li)
print (max_fee(M, C))

Submission status: Runtime Error

Solution code:
from heapq import *
n, m = map(int, input().split())
pay = []
for _ in range(n):
    a, b = map(int, input().split())
    pay.append((a, b))
pay = sorted(pay, reverse=True)
print(pay)
q = []
ans = 0
for i in range(1, m+1):
    while pay and pay[-1][0] <= i:
        a, b = pay.pop()
        heappush(q, -b)
    print(q)
    if q:
        b = -heappop(q)
        ans += b
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst_f = [[] for i in range(m)]
#lst = sorted(lst, key=lambda x:x[0])
#lst = sorted(lst, key=lambda x:x[1], reverse=True)
cnt = 0
ans = 0
cntup = m
for a, b in lst:
  if a <= m:
    lst_f[a-1].append(b)
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
avb = [] 
for i in lst_f:
  for j in i:
    avb.append(-j)
  if avb != []:
    ans -= avb.pop(min(avb))
print(ans)

Submission status: Runtime Error

Solution code:
N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
days_limit = M

jobs = AB[:]
jobs_dict = {i: [] for i in range(M+1)}
for d, r in jobs:
    jobs_dict[d].append(r)
#print(jobs_dict)

import heapq
hq = []

ans = 0
for d in range(1, M+1):
    for r in jobs_dict[d]:
        heapq.heappush(hq,-r)
    if hq:
        ans += -1 * heapq.heappop(hq)
print(ans)

Submission status: Runtime Error

Solution code:
N, M  = map(int, input().split())
AB = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    AB[i] = (a, b)
days_limit = M

jobs = AB[:]
jobs_dict = {i: [] for i in range(M+1)}
for d, r in jobs:
    jobs_dict[d].append(r)
#print(jobs_dict)

import heapq
hq = []

ans = 0
for d in range(1, M+1):
    for r in jobs_dict[d]:
        heapq.heappush(hq,-r)
    ans += -1 * heapq.heappop(hq)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    _, m, ab = map(int, open(0).read().split())
    ab = zip(ab[0::2], ab[1::2])
    pay = 0
    day = 0
    for t in reversed(sorted(ab, key=lambda x: (x[1], x[0]))):
        a, b = t

        # 目標日以降
        if day > m:
            break
        # 報酬が受け取れない
        if a > m or day+a > m:
            continue

        pay += b
        day += 1

    print(pay)


if __name__ == "__main__":
    main()

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)]
su=0
for i in range(n):
  d,m=map(int,input().split())
  daylist[i]=d
  money[i]=m
moneyindex=sorted(range(len(money)),key=lambda k:money[k])
for j in range(min(day,n)):
  a=hima.count(1)
  if(a==day):
    break
  howlong=daylist[moneyindex[n-j-1]]
  when=day-howlong
  while((hima[when]==1)and(when>=0)):
    when-=1
  if(when>=0):
    hima[when]=1
    su+=money[moneyindex[n-j-1]]
print(su)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop

na = lambda: map(int, sys.stdin.readline().split())

n, m = na()
ab = [list(na()) for _ in range(n)]

ans = 0
h = []
for day in range(1, m+1):
  d = 0
  for i in range(len(ab)):
    if ab[i-d][0] <= day:
      heappush(h, -ab.pop(i-d)[1])
      d += 1
  ans += -heappop(h)

print(ans)

Submission status: Runtime Error

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

q = [[] for _ in range(M)]
for a, b in ls:
    if a <= M:
        q[M-a].append(b*-1)

# print(q)

from heapq import heappop

pool = []
answer = 0
for x in reversed(q):
    pool.extend(sorted(x))
    m = heappop(pool)*-1
    answer += m
    

print(answer)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def p_e():
    N, M, P = map(int, input().split())
    abc = [tuple(map(int, input().split())) for _ in range(M)]
    li = defaultdict(list)

    for i in range(M):
        li[abc[i][0]].append((abc[i][1], -(abc[i][2] - P)))

    li_ans = defaultdict()
    li_ans[1] = 0
    li_top = [1]
    lt = []
    bf_n = -1
    while li_top and li_top != lt:
        lt = li_top.copy()
        li_top = []
        if N in li_ans.keys():
            bf_n = li_ans[N]

        for i in lt:
            for e in li[i]:
                if not e[0] in li_ans.keys():
                    li_ans[e[0]] = e[1] + li_ans[i]
                    li_top.append(e[0])
                else:
                    if li_ans[e[0]] > e[1] + li_ans[i]:
                        li_ans[e[0]] = e[1] + li_ans[i]
                        li_top.append(e[0])

    if li_top == lt and bf_n != li_ans[N]:
        print(-1)
    else:
        print(max(0, -li_ans[N]))


if __name__ == '__main__':
    p_e()

Submission status: Runtime Error

Solution code:
def p_e():
    N, M, P = map(int, input().split())
    abc = [tuple(map(int, input().split())) for _ in range(M)]
    li = defaultdict(list)

    for i in range(M):
        li[abc[i][0]].append((abc[i][1], -(abc[i][2] - P)))

    li_ans = defaultdict()
    li_ans[1] = 0
    li_top = [1]
    lt = []
    bf_n = -1
    while li_top and li_top != lt:
        lt = li_top.copy()
        li_top = []
        if N in li_ans.keys():
            bf_n = li_ans[N]

        for i in lt:
            for e in li[i]:
                if not e[0] in li_ans.keys():
                    li_ans[e[0]] = e[1] + li_ans[i]
                    li_top.append(e[0])
                else:
                    if li_ans[e[0]] > e[1] + li_ans[i]:
                        li_ans[e[0]] = e[1] + li_ans[i]
                        li_top.append(e[0])

    if li_top == lt and bf_n != li_ans[N]:
        print(-1)
    else:
        print(max(0, -li_ans[N]))


if __name__ == '__main__':
    p_e()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(n)]
lst = sorted(lst, key=lambda x:x[0], reverse=True)
lst = sorted(lst, key=lambda x:x[1], reverse=True)
#print(lst)
cnt = 0
for i in range(m):
  lst = [j for j in lst if j[0]<=m-i]
  #print(filter(lambda y:y<=m-i, map(lambda x:x[0], lst)))
  #lst2 = list(filter(lambda y:y[1]<=m-i, lst))
  #print(lst_f)
  if lst != []:
    #print(lst)
    cnt += lst[0][1]
    remove(lst[0])
  else:
    break
print(cnt)

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)]
su=0
for i in range(n):
  d,m=map(int,input().split())
  daylist[i]=d
  money[i]=m
moneyindex=sorted(range(len(money)),key=lambda k:money[k])
for j in range(n):
  a=hima.count(1)
  if(a==day):
    break
  howlong=daylist[moneyindex[n-j-1]]
  when=day-howlong
  while((hima[when]==1)and(when>=0)):
    when-=1
  if(when!=-1):
    hima[when]=1
    su+=money[moneyindex[n-j-1]]
print(su)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(n)]
d.sort(key = lambda x:x[0])
d.sort(key = lambda x:x[1],reverse=True)

from heapq import heappush, heappop
hq = []
for i,ab in enumerate(d):
    heappush(hq,(i,ab))

cur_dat = 1
ret = 0
while cur_dat <= m:
    val = heappop(hq)[1]
    if val[0] <= cur_dat:
        ret+=val[1]
    else:
        heappush(hq,val)
    cur_dat+=1
print(ret)

Submission status: Runtime Error

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

q = [[0] for _ in range(M)]
for a, b in ls:
    q[M-a].append(b)

pool = []
answer = 0
for x in reversed(q):
    m = max(x+pool)
    answer += m
    pool += x
    pool.remove(m)
    

print(answer)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
W = {}
for _ in range(N):
  a,b = map(int, input().split())
  if a in W:
    W[a].append(b)
  else:
    W[a] = [b]

ans = 0
for i in range(1, M+1):
  for j in range(1, i):
    if j in W.keys():
      ans += max(W[j])
      W[j].remove(max(W[j]))
print(ans)

Submission status: Runtime Error

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

q = [[1e-10] for _ in range(M)]
for a, b in ls:
    q[M-a].append(b)

print(sum(int(max(x)) for x in q))

Submission status: Runtime Error

Solution code:
n=int(input())
l=[['0']*10 for _ in range(n)]
for i in range(n):
        a=str(input())
        for j in range(10):
                l[i][j]=a[j]
        l[i].sort()
l.sort()

c=0
d=[]
for j in range(n-1):
        if l[j]==l[j+1] and j==n-2:
                c+=2
                d.append(c)
        elif l[j]==l[j+1]:
                c+=1
        else:
                c+=1
                d.append(c)
                c=0
aa=0
for k in range(len(d)):
        aa+=d[k]*(d[k]-1)//2
print(aa)

Submission status: Runtime Error

Solution code:
from heapq import merge


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

last_day_to_reward = {}

for i in range(N):
    a, b = map(int, input().split(' '))
    last_day = max(0, M - a + 1)
    if last_day not in last_day_to_reward:
        last_day_to_reward[last_day] = []
    last_day_to_reward[last_day].append(b)

for k in last_day_to_reward:
    last_day_to_reward[k].sort()

ans = 0
candidate = []
for i in reversed(range(1, M+1)):
    if i in last_day_to_reward:
        candidate = list(merge(candidate, last_day_to_reward[i]))

    r = candidate[-1]
    ans += r

    candidate = candidate[:-1]

print(ans)

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int, input().split(" ")))


import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

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


res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    i=k
    while True:
        if i>=len(ab):
            k=10**8
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)

    tmp=heapq.heappop(koho)
    #print(tmp)
    res+=(-tmp)
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))

#print(do)
'''
3 6
4 5
4 3
6 4

'''

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int, input().split(" ")))

import numpy as np

import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

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


res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    i=k
    while True:
        if i>=len(ab):
            k=10**8
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)

    tmp=heapq.heappop(koho)
    #print(tmp)
    res+=(-tmp)
    nowdate-=1
    if nowdate<0:
        break
    

print(int(res))

#print(do)
'''
3 6
4 5
4 3
6 4

'''

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*9*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

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

exm = 0
for i in range(1, m+1):
    _bmax = max([_b for _a, _b in zip(a, b) if _a <= i])
    _bidx = b.index(_bmax)
    exm += _bmax
    a.pop(_bidx)
    b.pop(_bidx)

print(exm)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(n):
    _a, _b = map(int, input().split())
    a += _a
    b += _b

exm = 0
for i in range(1, m+1):
    _bmax = max([_b for _a, _b in zip(a, b) if _a <= i])
    _bidx = b.index(_bmax)
    exm += _bmax
    a.pop(_bidx)
    b.pop(_bidx)

print(exm)

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]
v=[[]for _ in q]
z=0
for a,b in t:
	if a<=M:v[a-1]+=[b]
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(n):
    _a, _b = map(int, input().split())
    a += _a
    b += _b

exm = 0
for i in range(1, m+1):
    print(a, b)
    _bmax = max([_b for _a, _b in zip(a, b) if _a <= i])
    _bidx = b.index(_bmax)
    exm += _bmax
    print(_bmax, _bidx)
    a.pop(_bidx)
    b.pop(_bidx)

print(exm)

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]*(a<=M)
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):
	if M<t[2*i]:v[t[2*i]-1]+=[t[2*i+1]]
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):M<t[2*i]or v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=q[0]and heappop(q)
print(z)

Submission status: Runtime Error

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+1)]
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
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)

Submission status: Runtime Error

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

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

#print(nm)
#print(ab)

ab.sort(reverse=True)

#print(ab)

dp = [[-1]*nm[1] for i in range(nm[0])]

#print(dp)

def rec(i, j):

    #print("i =", i, "j =", j)
    
    if i != nm[0] and j != nm[1]:
        if dp[i][j] != -1:
            #print("i=", i, "j=", j, "dp=", dp[i][j])
            return dp[i][j]
    
    if i == nm[0]:
        res = 0
    
    elif j < ab[i][0]:
        #print("ab = ", ab[i])
        res = rec(i+1, j)

    else :

        r1=rec(i+1, j)
        r2=rec(i+1, j-1) + ab[i][1]

        #print("i=", i, "j=", j, "\nr1 =", r1, "\nr2 =", r2)

        res = max(r1, r2)

    if i != nm[0] and j != nm[1]:
        dp[i][j] = res

    #print("res =", res)

    return res

salary = rec(0, nm[1])

print(salary)

Submission status: Runtime Error

Solution code:
from collections import*
from heapq import*
n,m,*t=map(int,open(0).read().split())
d=defaultdict(list)
for a,b in zip(t[::2],t[1::2]):d[a].append(b)
q=[]
for i in sorted(d.keys())[::-1]:
    for b in sorted(d[i])[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        else:
            if q[0]<b:heappushpop(q,b)
print(sum(q))

Submission status: Runtime Error

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

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

#print(nm)
#print(ab)

ab.sort(reverse=True)

#print(ab)

dp = [[-1]*nm[1] for i in range(nm[0])]

#print(dp)

def rec(i, j):

    #print("i =", i, "j =", j)
    
    if i != nm[0] and j != nm[1]:
        if dp[i][j] != -1:
            #print("i=", i, "j=", j, "dp=", dp[i][j])
            return dp[i][j]
    
    if i == nm[0]:
        res = 0
    
    elif j < ab[i][0]:
        #print("ab = ", ab[i])
        res = rec(i+1, j)

    else :

        r1=rec(i+1, j)
        r2=rec(i+1, j-1) + ab[i][1]

        #print("i=", i, "j=", j, "\nr1 =", r1, "\nr2 =", r2)

        res = max(r1, r2)

    if i != nm[0] and j != nm[1]:
        dp[i][j] = res

    #print("res =", res)

    return res

salary = rec(0, nm[1])

#print(salary)

Submission status: Runtime Error

Solution code:
#input = raw_input
import numpy as np

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

out = 0

#not_done = [True for _ in range(M)]

#counts = [0 for _ in range(M)]
cumsum_counts = np.zeros(M, dtype=int)

all_sum = 0

ue_end_i = M-1
for A, B in pairs:
    ue_start_i = M-A+1
    if ue_start_i <= ue_end_i:
        ue_limit = ue_end_i - ue_start_i + 1
        #ue_sum = sum(counts[ue_start_i:])
        ue_sum = cumsum_counts[ue_start_i]
        hamidashi = max(ue_sum - ue_limit, 0)
    else:
        # ue_start_i == M
        hamidashi = 0
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi # 0 ~ M-A
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni

    if aki >= 1:
        out += B
        #counts[M-A] += 1
        cumsum_counts[M-A:] += 1
        all_sum += 1

print(out)

Submission status: Runtime Error

Solution code:
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()
            break

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a > M or b < max_sort_list[len(max_sort_list)-1]:
        continue
    if a in each_days_map.keys():
        a_len = len(each_days_map[a])
        if b > each_days_map[a][a_len-1]:
            for idx in range(a_len):
                if b > each_days_map[a][idx]:
                    each_days_map[a].insert(idx,b)
                    if a_len > (M - a + 1):
                        removed_num = each_days_map[a][a_len-1]
                        each_days_map[a].pop()
                        max_sort_list.remove(removed_num)
                    insert_max_sort(b)
                    break
        else:
            if M > a_len and (M - a + 1) > a_len:
                each_days_map[a].append(b)
                insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

Submission status: Runtime Error

Solution code:
#input = raw_input
import numpy as np

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
cumsum_counts = np.zeros(0, dtype=int)

all_sum = 0

ue_end_i = M-1
for A, B in pairs:
    if A > M:
        continue
    ue_start_i = M-A+1
    if ue_start_i <= ue_end_i:
        ue_limit = ue_end_i - ue_start_i + 1
        #ue_sum = sum(counts[ue_start_i:])
        ue_sum = cumsum(ue_start_i)
        hamidashi = max(ue_sum - ue_limit, 0)
    else:
        # ue_start_i == M
        ue_sum = 0
        hamidashi = 0
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi # 0 ~ M-A
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni

    if aki >= 1:
        out += B
        #counts[M-A] += 1
        cumsum_counts[M-A:] += 1
        all_sum += 1

print(out)

Submission status: Runtime Error

Solution code:
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()
            break

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    insert_flag = True
    if a > M or b < max_sort_list[len(max_sort_list)-1]:
        continue
    if a in each_days_map.keys():
        a_len = len(each_days_map[a])
        for idx in range(a_len):
            if b > each_days_map[a][idx]:
                each_days_map[a].insert(idx,b)
                if a_len > (M - a + 1):
                    removed_num = each_days_map[a][a_len-1]
                    each_days_map[a].pop()
                    max_sort_list.remove(removed_num)
                insert_max_sort(b)
                insert_flag = False
                break
        if insert_flag and M > a_len and (M - a + 1) > a_len:
            each_days_map[a].append(b)
            insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

Submission status: Runtime Error

Solution code:
from heapq import*
n,m,*t=map(int,open(0).read().split())
k=max(t)
d=[[]for _ in range(k+1)]
for a,b in zip(t[::2],t[1::2]):d[a]+=b,
q=[]
for i,b in enumerate(d[::-1]):
    i=k-i
    for b in sorted(b)[::-1][:m-i+1]:
        if len(q)<=m-i:heappush(q,b)
        else:
            if q[0]<b:heappushpop(q,b)
print(sum(q))

Submission status: Runtime Error

Solution code:
a=int(input())
b=[sorted(input()) for j in range(a)]
c=[[0for i in range(26)] for j in range(a)]
for i in range(a):
  for j in range(10):
    c[i][ord(b[i][j])-97]+=1
sum=0
d=1
c.sort()
for i in range(a-1):
  if c[i]==c[i+1]:
    d+=1
  else:
    sum+=d*(d-1)//2
    d=1
  if i==a-2:
    sum+=d*(d-1)//2
    
print(sum)

Submission status: Runtime Error

Solution code:
a=int(input())
b=[sorted(input()) for j in range(a)]
c=[[0for i in range(26)] for j in range(a)]
for i in range(a):
  for j in range(10):
    c[i][ord(b[i][j])-97]+=1
sum=0
d=1
c.sort()
print(c)
for i in range(a-1):
  if c[i]==c[i+1]:
    d+=1
  else:
    sum+=d*(d-1)//2
    d=1
  if i==a-2:
    sum+=d*(d-1)//2
    
print(sum)

Submission status: Runtime Error

Solution code:
import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
ABS = sorted(AB, key=lambda x: -x[1])
ABSS = sorted(ABS, key=lambda x: x[0])
# print(ABS)
# print(ABSS)

heap = []
ans = 0
chkpos = 0

for i in range(1, M+1):
  while ABSS[chkpos][0] <= i:
    heapq.heappush(heap, -1 * ABSS[chkpos][1])
    chkpos += 1
    if chkpos >= N -1:
      break
#  print(heap)
  if len(heap) > 0:
    ans -= heapq.heappop(heap)
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
x=[]
an=0
for i in range(M+1):
    x.insert(i,[])
for i in range(N):
    a,b=map(int,input().split())
    if a<=M:
        x[a].append(b)
y=[]
while n in <=M+1:
    y+=x[n]
    try:
        n=y.count(max(y))
        an+=n*max(y)
        for z in range(n)
            y.remove(max(y))
        n+=1
    except:
        continue
print(an)