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:
import heapq
N, M =map(int, input().split())
A = [[] for i in range(10**5+1)]

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

work_cand = []
sum = 0

for i in range(M+1):
    add_jobs = A[i]
    if len(add_jobs) != 0:
        for j in add_jobs:
            heapq.heappush(work_cand, j)
    if len(work_cand) == 0:
        continue
    sum += heapq.heappop(work_cand)
ans = -(sum)
print(ans)

Submission status: Runtime Error

Solution code:
N, M =map(int, input().split())
A = [[] for i in range(10**5+1)]

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

work_cand = []
sum = 0

for i in range(M+1):
    add_jobs = A[i]
    if len(add_jobs) != 0:
        for j in add_jobs:
            heapq.heappush(work_cand, j)
    sum += heapq.heappop(work_cand)
ans = -(sum)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
li = list(map(int,input().split()))
N = li[0]
days = li[1]
job_list = []
for i in range(N):
    li = list(map(int,input().split()))
    job_list.append(li) 
job_list = sorted(job_list, key=lambda x:x[0])
money = 0
for day in range(days):
    if len(job_list) == 0:
         break  
    rest_day = days - day
    while (job_list[-1][0] > rest_day):
        job = job_list.pop()
    max_j = np.argmax(np.array(job_list[::-1])[:,1])
    max_job = job_list.pop(-(max_j+1))
    money += max_job[1]
print(money)

Submission status: Runtime Error

Solution code:
n,d=map(int,input().split())
a={}
for i in range(n):
  td,tp=map(int,input().split())
  if a.get(td)==None:
    a[td]=[tp]
  else:
    a[td].append(tp)
r=0
for i in range(d):
  for k in list(a.keys()):
    if i+k>d:
      del a[k]
  m=max(max(kl) for kl in a.values())
  r+=m
  if not a:
    break
  for j in sorted(list(a.keys()), reverse=True):
    if m in a[j]:
      a[j].remove(m)
      break
print(r)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
ab=[]
for _ in range(n):
    tmpa, tmpb=map(int, input().split())
    ab.append((tmpa,tmpb))
ab.sort(reverse=True)
import heapq
h = []
ans = 0
for i in range(1, m+1):
    print(h)
    while ab and ab[-1][0] == i:
        heapq.heappush(h,ab.pop()[1]*(-1))
    if h:
        ans -= heapq.heappop(h)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
dct = defaultdict(int)

for i in range(N):
  s = input()
  sorted_s = "".join(sorted(s))
  dct[sorted_s] += 1

ans = 0
for k, v in dct.items():
  ans += v*(v-1)//2

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq

N, M = list(map(int, input().split()))
possiblyValidJobs = {}
for line in sys.stdin:
    A, B = map(int, line.split())
    if A > M:
        continue

    if A in possiblyValidJobs:
        possiblyValidJobs[A] += 1
    else:
        possiblyValidJobs[A] = 1

validJobsOnThisDay = []
ans = 0
for daysBeforeDeadline in range(1, M + 1):
    if daysBeforeDeadline in possiblyValidJobs:
        for wage in possiblyValidJobs[daysBeforeDeadline]:
            heapq.heappush(validJobsOnThisDay, -wage)
    if validJobsOnThisDay:
        ans += -heapq.heappop(validJobsOnThisDay)
print(ans)