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:
from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for _ in range(N):
  a, b = map(int, input().split())
  AB[a].append(b) # 消化日数に対しての価値
  
#heapq.heapify(a)  # listを優先度付きキューに

q = []
ans = 0
for B in AB:
  for b in B: # 日数：価値
    heappush(q, -b) # 最大値のため、マイナスをかける
  if q:
    ans -= heappop(q) # マイナスの値を戻す
print(ans)

Submission status: Runtime Error

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

def aa(sh, idx, M, x, ans):
  if idx >= M:
    return sh, ans, x
  elif sh[idx] == 0:
    sh[idx] = idx+1
    sh[x["d"]] = idx+1
    ans += x["m"]
    return sh, ans, x
  else:
    zz = idx
    sh, ans, x = aa(sh, sh[idx], M, x, ans)
    sh[zz] = sh[x["d"]]
    return sh, ans, x
  
sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  sh, ans, x = aa(sh, idx, M, x, ans)
print(ans)

Submission status: Runtime Error

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

def aa(sh, idx, M, x, ans):
  if idx >= M:
    return sh, ans, x
  elif sh[idx] == 0:
    sh[idx] = idx+1
    sh[x["d"]] = idx+1
    ans += x["m"]
    return sh, ans, x
  else:
    sh, ans, x = aa(sh, sh[idx], M, x, ans)
    sh[idx] = sh[x["d"]]
    return sh, ans, x
  
sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  sh, ans, x = aa(sh, idx, M, x, ans)
print(ans)

Submission status: Runtime Error

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

def aa(sh, idx, M, x, ans):
  if idx >= M:
    return sh, ans, x
  elif sh[idx] == 0:
    sh[idx] = idx+1
    sh[x["d"]] = idx+1
    ans += x["m"]
    return sh, ans, x
  else:
    sh, ans, x = aa(sh, sh[idx], M, x, ans)
    sh[idx] = sh[x["d"]]
    idx = sh[idx]
    return sh, ans, x
  
sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  sh, ans, x = aa(sh, idx, M, x, ans)
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
from collections import defaultdict

N, M = map(int, input().split())
arbeits = defaultdict(list)
for _ in range(N):
    a, b = map(int, input().split())
    arbeits[a].append(b)
heap = []
ans = 0
for i in range(1, M+1):
    for b in arbeits[i]:
        heappush(heap, -b)
    ans += - heappop(heap)
print(ans)

Submission status: Runtime Error

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

flg = False
n, m = map(int, input().split())
jobs = [[] for i in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a > m and flg == False:
        jobs[m - a].append(b)
    else:
        flg = True
        jobs[m - a].append(b)

if flg == False:
    print(0)
    exit(0)

q = []
heapq.heapify(q)
ans = 0
for i in reversed(range(m)):
    for b in jobs[i]:
        heapq.heappush(q, -b)
    if len(q) != 0:
        ans += heapq.heappop(q) * -1

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n, m = map(int, input().split(' '))
income = []
for i in range(10**5):
  income.append([])
ans = 0

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

# print(n, m)
# print(income)

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

# print(sorted_income)

heap = []
for i in range(1, m+1):
  values = income[i]
  for j in range(len(values)):
    _heappush_max(heap, values[j])
  
  if len(heap) < 1:
    continue
  
  max_value = _heappop_max(heap)
  if max_value:
    ans += max_value
  # print(ans)
  

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
v=0
for i in range(n):
  d=input()
  y="".join(sorted(d))
  a.append(y)
for j in range(n-1):
  for k in range(j+1,n):
    if a[j]==a[k]:
      v+=1

print(v)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m,T,ans;
struct node{
  long long time;
  long long award;
}a[100001];
int cmp(node x,node y){
  if(x.award!=y.award)	
  return x.award>y.award;
  else return x.time>y.time; 
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i].time>>a[i].award;
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++)
  {
    if(T+a[i].time<=m)
    {
      ans+=a[i].award;
      T++;
    }
  }
  cout<<ans;
  return 0;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,T,ans;
struct node{
  int time;
  int award;
}a[100001];
int cmp(node x,node y){
  if(x.award!=y.award)	
  return x.award>y.award;
  else return x.time>y.time; 
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i].time>>a[i].award;
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++)
  {
    if(T+a[i].time<=m)
    {
      ans+=a[i].award;
      T++;
    }
  }
  cout<<ans;
  return 0;
}

Submission status: Runtime Error

Solution code:
N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(-b)
    
def add(q_,add_):
    for i in range(len(add_)):
        heapq.heappush(q_,add_[i])

def kouho(A,B,m):
    kouho_list = []
    for i in range(len(B)):
        if(A[i]==m):
            kouho_list.append(B[i])
    return kouho_list

q = []
heapq.heapify(q)
sum_money = 0

for m in range(1,M+1):
    kouho_list = kouho(A,B,m)
    add(q,kouho_list)
    #print(q)
    if(len(q)>0):
        sum_money += -heapq.heappop(q)
print(sum_money)

Submission status: Runtime Error

Solution code:
#f:やったことのある仕事=1そうでない=0
N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(b)
    
def dp(m,f):
    if(m==0):
        return 0
    else:
        max_ = 0
        for i in range(len(A)):
            if(f[i] == 0 and A[i]<=m):
                f_co = f.copy()
                f_co[i] = 1
                max_ = max([max_,dp(m-1,f_co)+B[i]])
        
        return max_
    
print(dp(M,f_start))

Submission status: Runtime Error

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

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        AB[A].append(-B)

ans = 0
hq = [0] * N
heapq.heapify(hq)
for i in range(1, M+1):
    for j in AB[i]:
        heapq.heappush(hq, j)
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Runtime Error

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

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        AB[A].append(-B)

ans = 0
hq = [0] * N
heapq.heapify(hq)
for i in range(1, M+1):
    for j in AB[i]:
        heapq.heappush(hq, j)
    ans += heapq.heappop(hq)

print(-ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lis = [[] for _ in range(10)]
for _ in range(n):
    a,b = map(int,input().split())
    lis[a-1].append(b)
ans = 0
li = []
for i in range(m):
    li += lis[i]
    li.sort(reverse=True)
    try:
        p = li.pop(0)
        ans += p
    except:
        continue
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
memo = [0] * M
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    memo[a] = max(b, memo[a])
ans = sum(memo)
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(key=lambda x: x[1], reverse=True)
memo = [0] * min(N, M)
ans = 0
for a, b in AB:
    Ma = max(M - a + 1, 0)
    for i in range(Ma, 0, -1):
        if memo[i - 1] == 0:
            memo[i - 1] = 1
            ans += b
            break
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(key=lambda x: x[1], reverse=True)
memo = [0] * N
ans = 0
for a, b in AB:
    Ma = M - a + 1
    if 0 in memo[:Ma]:
        i = bisect.bisect_right(memo[:Ma], 0) - 1
        memo[i] = 1
        ans += b
print(ans)

Submission status: Runtime Error

Solution code:
import heapq

n,m = map(int,input().split())
lb = [[] for _ in range(10**5)]
for _ in range(n):
    a,b = map(int,input().split())
    lb[a].append(b)
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb[i]:
        heapq.heappush(q,b * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n): 
    a,b=map(int,input().split())
    l.append([a,b])
    #b afer a days 
#l=[]
l=[l[i] for i in range(n) if l[i][0]<=m]
l.sort(key=lambda x:[-x[1],-x[0]])
#print(l)
sm=0 
day=0 
#print(l)
for i in range(n): 
    #print(day,l[i][0],l[i][1])
    if day+l[i][0]<=m: 
        sm+=l[i][1]
        #print(i,sm)
        day+=1 
    else: 
        pass 
print(sm)

Submission status: Runtime Error

Solution code:
import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
for rest_days in range(1, M+1):
    tmp += income[rest_days]
    heapq.heapify(tmp)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)v

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l.append([a,b])
n=len(l)
l.sort()
p=0
t=l[0][0]
for i in range(n):
  if l[i][0]!=t:
    p+=l[i-1][1]
    t=l[i][0]
print(p)

Submission status: Runtime Error

Solution code:
from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if m == 1:
        print(jobs[1])
        exit()

    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)

Submission status: Runtime Error

Solution code:
from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if m == 1:
        print(jobs[0][1])
        exit()
        
    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)

Submission status: Runtime Error

Solution code:
for x in range(0,M+1):
    indexes = [i for i, m in enumerate(A) if m<=x]
    if len(indexes)!=0:
        for y in range(len(indexes)):
            if max<B[indexes[y]]:
                max=B[indexes[y]]
                s=indexes[y]
        del A[s]
        del B[s]
        count=count+max
        max=0
print(count)

Submission status: Runtime Error

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

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

st = list(np.argsort(B))
st.reverse()

day = [0]*(M+1)
cnt = 0

for i in range(N):
    if A[st[i]] > M:
        continue
    for j in range(M-A[st[i]],M+1):
        tmpday[j] += 1
    flag = True
    for j in range(M+1):
        if tmpday[j] > j+1:
            flag = False
    print(tmpday)
    if flag:
        cnt += B[st[i]]
        day = tmpday

print(cnt)

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
for i in range(n):
  a[i] = (int(x) for x in input().split())
  b[i] = (int(x) for x in input().split())	
c = []
d = []
s = []
m = []
k = 0
for i in range(n):
  if b[i] <= m:
    d[i].append(a[i])
    c[i].append(b[i])
for i in range(100):
  for j in range(n)
  	if k <= m:
      s[i] = d[i][j] + s[i]
      k += c[i]
      
print(max(s))

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
for i in range(n):
  a[i] = (int(x) for x in input().split())
  b[i] = (int(x) for x in input().split())	
c = []
d = []
s = []
m = []
for i in range(n):
  if b[i] <= m:
    d[i].append(a[i])
    c[i].append(b[i])
for i in range(n):
  for j in range(n)
  	if s <= m:
      s[i] = a[i][j] + s[i]
      
print(max(s))

Submission status: Runtime Error

Solution code:
import numpy as np
import math

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

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

st = list(np.argsort(B))
st.reverse()

day = [0]*M
cnt = 0

for i in range(N):
    tmpday= day[:]
    tmpday[M-A[st[i]]] += 1
    flag = True
    for j in range(M):
        if sum(day[:j+1]) > j:
            flag = False
    if flag:
        cnt += B[st[i]]
        day[M-A[st[i]]] += 1

print(cnt)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
NM = []
count_N = 0
for i in range(N):
  tmp = []
  A_,B_ = map(int,input().split())
  if A_ <= M:
    tmp.append(B_)
    tmp.append(A_)
    NM.append(tmp)

NM.sort(reverse=True)
#print(NM)

count = 0
for i in range(M):
  NM_len = len(NM)
  if NM_len == 0:
    break;
  for num in range(NM_len):
    if NM[num][1] > M-i:
      del NM[num]
  NM_len = len(NM)

  if NM_len == 0:
    break;

  for j in range(NM_len):
    if NM[j][1] <= M-i:
      count += NM[j][0]
      del NM[j]
      break;

print(count)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
NM = []
count_N = 0
for i in range(N):
  tmp = []
  A_,B_ = map(int,input().split())
  if A_ <= M:
    tmp.append(B_)
    tmp.append(A_)
    NM.append(tmp)

NM.sort(reverse=True)
#print(NM)

count = 0
for i in range(M):
  NM_len = len(NM)
  for num in range(NM_len):
    if NM[num][1] > M-i:
      del NM[num]
  NM_len = len(NM)

  for j in range(NM_len):
    if NM[j][1] <= M-i:
      count += NM[j][0]
      del NM[j]
      break;

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print(max(a + b, a - b, a * b))
    return

#B
def B():
    k, x = LI()
    ans = []
    for i in range(x - k + 1, x + k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    n = II()
    d = defaultdict(int)
    for _ in range(n):
        s = S()
        s.sort()
        d[tuple(s)] += 1
    ans = 0
    for i in d.values():
        ans += i * (i - 1) // 2
    print(ans)
    return

# D
# 解説AC
# 後方から見ていくのはわかったけど。。。
# i日前に選べるバイトの中から一番報酬が大きいを選んでいく
def D():
    n, m = LI()
    q = []
    d = defaultdict(list)
    ans = 0
    for _ in range(n):
        a, b = LI()
        d[a].append(b)
    for i in range(m):
        for di in d[i+1]:
            heappush(q, di)
        ans += heappop(q)
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
import numpy
import heapq
import math

N,M = list(map(int, input().split()))
data = [[]for _ in range(M)]
for _ in range(N):
    A,B = list(map(int, input().split()))
    if (A - 1) <= M:
        data[A-1].append(-B)

rew = 0
heap=[]
for i in range(M):
    for rewo in data[i]:
        heapq.heappush(heap,rewo)
    if len(heap) > 0:
        r = heapq.heappop(heap)
        rew += -r

print(rew)

Submission status: Runtime Error

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

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

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

days_left = [1] * (m + 2)
ans = 0
for a, b in ab:
    i = a
    while days_left[i] == 0:
        i += 1
    if i == m + 1:
        continue
    days_left[i] = 0
    ans += b

print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
c=[[] for i in range(pow(10,5))]
for i in range(n):
    a,b=map(int,input().split())
    c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

Submission status: Runtime Error

Solution code:
import heapq

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


d_AB = {a:[] for a,b in AB}
for a,b in AB:
    d_AB[a].append(-b)

H = [0]
money = 0
for i in range(1,M+1):
    if i in d_AB.keys():
        H += d_AB[i]
    #else:
        #H += [0]
    #print(H)
    heapq.heapify(H)
    money += heapq.heappop(H)

print(-money)

Submission status: Runtime Error

Solution code:
import sys
import heapq


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


def main():
    N, M = map(int, input().split())

    w = [[] for _ in range(10 ** 5)]
    for _ in range(N):
        a, b = map(int, input().split())
        w[a].append(b)

    ans = 0
    hq = []
    for i in range(1, M+1):
        for x in w[i]:
            heapq.heappush(hq, -x)

        if not hq:
            continue

        ans += -heapq.heappop(hq)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq
n,m=map(int,input().split())
dic=defaultdict(list)
for i in range(n):
    a,b=map(int,input().split())
    dic[a]+=(-b)
    
li=[]
ans=0

for i in range(1,m+1):
    if dic[i]:
        for j in dic[i]:
            heapq.heappush(li,j)
    if li:
        ans+=heapq.heappop(li)
print(-ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
ab=[[0,0] for _ in range(N)]
a=[]
b=[]
for i in range(N):
  ab[i]=list(map(int,input().split()))
  ai,bi=ab[i][0],ab[i][1]
  a.append(ai)
  b.append(bi)

def Count(List):
  d={}
  ans=0
  for i in range(len(List)):
    if List[i] not in d:
      d[List[i]]=1
      ans+=1
    else:
      d[List[i]]+=1
  d=sorted(d.items(),reverse=True)
  return d

def count(List):
  l=[]
  ans=0
  for i in range(len(List)):
    if List[i] not in l:
      l.append(List[i])
      ans+=1
    else:
      pass
  return ans

def Sort(a,b,l=[],l2=[],i=0):
  if a==[]:
    return l+l2
  max_a=max(a)
  index=a.index(max_a)
  l.append(max_a)
  l2.insert(i,b[index])
  i+=1
  a.remove(max_a)
  b.remove(b[index])
  return Sort(a,b,l,l2,i)
    
tmp_l=Sort(a,b,l=[],l2=[],i=0)
new_a,new_b=tmp_l[0:N],tmp_l[N:2*N]
 
tmp_b=[]
d=Count(new_a)
start=0
for Tuple in d:
  val=Tuple[1]
  tmp_b+=sorted(new_b[start:start+val],reverse=True)
  start+=val
new_b=tmp_b
  
def DP(new_a,new_b,M,ans=0):
  if new_a==[] or M==0 or new_a[-1]>M:
    return ans
  elif new_a[0]<=M :
    val1=new_b[0]
    if count(new_a)>=2:
      num=0
      while new_a[num]==new_a[0] :
        num+=1
      val2=new_b[num]
      if val1>=val2:
        ans+=val1
        new_a.pop(0)
        new_b.pop(0)
      else:
        ans+=val2
        new_a.pop(num)
        new_b.pop(num)
      return DP(new_a,new_b,M-1,ans)
    else:
      ans+=new_b[0]
      new_a.pop(0)
      new_b.pop(0)
      return DP(new_a,new_b,M-1,ans)
  elif new_a[0]>M:
    while new_a[0]>M:
      new_a.pop(0)
      new_b.pop(0)
    return DP(new_a,new_b,M,ans)
    
print(DP(new_a,new_b,M,ans=0))

Submission status: Runtime Error

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An.sort()
          ans+=An.pop(len(An)) 
print(ans)

Submission status: Runtime Error

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An = An.sort()
          ans+=An.pop(len(An)) 
print(ans)

Submission status: Runtime Error

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An = An.sort()
          ans += pop(len(An))
print(ans)

Submission status: Runtime Error

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          ans+=An.pop(An.index(max(An))) 
print(ans)

Submission status: Runtime Error

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      Ar[x for x < A].append[B]
for i in range(M):
      ans += max(Ar[i])
print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    jobs = [[] for _ in range(10000)]
    v = 0
    for i in range(N):
        a,b = [int(n) for n in input().split()]
        if a <= M:
            jobs[b].append((a,b))
            v = max(v,b)
    jobs = jobs[:v+1]
    # 時間でソート(昇順)
    for i in range(v):
        jobs[i] = sorted(jobs[i])

    # debug(jobs, "(期限、価値) in [価値]")
    ans = 0
    jobs_k = len(jobs)-1

    for i in range(jobs_k,-1,-1):
        while(len(jobs[i]) != 0 and jobs[i][-1][0] <= M):
            ans+=jobs[i][-1][1]
            M-=1
            jobs[i].pop()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N,M = [int(n) for n in input().split()]
    jobs = [[] for _ in range(10000)]
    v = 0
    for i in range(N):
        a,b = [int(n) for n in input().split()]
        if a <= M:
            jobs[b].append((a,b))
            v = max(v,b)
    jobs = jobs[:v+1]
    # 時間でソート(昇順)
    for i in range(v):
        jobs[i] = sorted(jobs[i])

    # debug(jobs, "(期限、価値) in [価値]")
    ans = 0
    jobs_k = len(jobs)-1

    while(M>0 or jobs_k != 0):
        for i in range(jobs_k,-1,-1):
            if len(jobs[i]) == 0:
                jobs.pop()
                if len(jobs)==0:
                    M = 0
                    break
                continue
            if jobs[i][-1][0] > M:
                jobs[i].pop()
            else:
                ans += jobs[i][-1][1]
                jobs[i].pop()
                M -= 1
                break
        jobs_k = max(len(jobs)-1,0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ansList = []
newList = []
jobList = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    jobList[A-1].append(B)

for j in range(M):
    newList = newList + jobList[j]
    newList.sort()
    try:
        ansList.append(newList.pop())
    except IndexError:
        ansList.append(0)
print(sum(ansList))

Submission status: Runtime Error

Solution code:
import heapq

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

for i in range(N):
    a,b = list(map(int,input().split()))
    A[a-1].append(-b)
    
ans = 0
cand = []

for i in range(M):
    
    for j in A[i]:
        cand.append(j)
        
    if cand:
        heapq.heapify(cand)
        ans -= heapq.heappop(cand)
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
from operator import itemgetter
import numpy as np

N, M = [int(x) for x in input().split()]
A = {}
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    if x  not in A:
       A[x] = []
    A[x].append(y)

for key in A:
    A[key].sort()


total = 0
for x in range(1, M + 1):
    max = 0
    max_index = -1
    for k, v in sorted(A.items()):
        if k > x:
            break
        if v[-1] > max:
            max = v[-1]
            max_index = k
    if max_index != -1:
        total += A[max_index].pop()
        if len(A[max_index]) == 0:
            A[max_index].append(-1)


print(total)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
val =[[]for _ in range(m+1)]
for _ in range(n):
	a,b=map(int,input().split())
	val[a].append(b)
mval = [0]*(m+1)
for i in range(1,m+1):
	val[i].sort(reverse=True)
	mval[i] = val[i][0] if val[i] else 0
ans = 0
for dayleft in range(1,m+1):
	cidx = mval.index(max(mval[1:dayleft+1]))
	if cidx == 0:
		continue
	ans += mval[cidx]
	del val[cidx][0]
	mval[cidx] = 0 if val[cidx]==[] else val[cidx][0]

print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp

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

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if len(h)>0:
    ans -= hp.heappop(h)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp

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

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if h!=None:
	ans -= hp.heappop(h)
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp

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

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if h!=None:
	  ans -= hp.heappop(h)
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hp

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

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  ans -= hp.heappop(h)
  
print(ans)

Submission status: Runtime Error

Solution code:
import heapq as hq

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

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  ans -= hp.heappop(h)
  
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)

for i in reversed(range(m)):
	for j in range(count,len(a)):
		count += 1
		if a[j] + i == m:
			l.append(b[j])
		else:
			break
	print(l)
	if len(l) != 0:
		ans += max(l)
		index = b.index(max(l))
		#a.pop(index)
		#b.pop(index)
		l.pop(l.index(max(l)))
	print(a)
	print(b)
	#l.clear()

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

def solve():
    N, M = map(int , input().split())
    arbeit_A_B = list(list(map(int , input().split())) for _ in range(N))
    arbeit_A_B = sorted(arbeit_A_B, key=lambda x: (x[0], -x[1]))
    # print(arbeit_A_B)
    day = 1
    result = 0
    index_arbeit = 0
    heap_q = []
    while day <= M:
        while index_arbeit < N:
            A,B = arbeit_A_B[index_arbeit]
            if A <= day:
                heappush(heap_q, (-1)*B)
            else: break
            index_arbeit += 1
            
        result -= heappop(heap_q)
        day += 1
            
    print(result)
    
solve()