Problem:


Score : 400 points

Problem Statement

There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

Find the maximum total reward that you can earn no later than M days from today.

You can already start working today.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i \leq 10^5

1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the maximum total reward that you can earn no later than M days from today.

Sample Input 1

3 4
4 3
4 1
2 2

Sample Output 1

5

You can earn the total reward of 5 by taking the jobs as follows:

Take and complete the first job today. You will earn the reward of 3 after four days from today.

Take and complete the third job tomorrow. You will earn the reward of 2 after two days from tomorrow, that is, after three days from today.

Sample Input 2

5 3
1 2
1 3
1 4
2 1
2 3

Sample Output 2

10

Sample Input 3

1 1
2 1

Sample Output 3

0



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Wrong Answer

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

works = []
ans = 0
for i in range(n):
    day, money = map(int,input().split())

    if i+day <= m:
        ans += money
    i += 1
print(ans)

Submission status: Wrong Answer

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

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

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

for x in ba:
  x.sort(reverse=True)

cnt = m
ans = 0

for i in range(10000, -1, -1):
  if ba != []:
    for e in ba[i]:
      if cnt != 0 and e <= cnt:
        ans += i
        cnt -= 1
  if cnt == 0:
    break

print(ans)

Submission status: Wrong Answer

Solution code:

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import heapq
AB.sort()
heap = []
heapq.heapify(heap)
ans = 0
i = 0
day = 1
while i < N and day <= M:
    while i < N and AB[i][0] <= day:
        heapq.heappush(heap,-AB[i][1])
        i += 1
    day += 1
    if not(heap):continue
    ans -= heapq.heappop(heap)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = []
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
l.sort(reverse=True,key= lambda x:x[0])
l.sort(reverse=True,key= lambda x:x[1])

da = 0
mon = 0
for i in range(n):
    a,b = l[i]

    if da + a <= m:
        mon += b
        da += 1
    else:
        continue
print(mon)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
 
import heapq
import collections
 
a_all = []
for i in range(n):
    a_all.append(ab[i][0])
 
key_all = list(set(a_all))
key_all.sort()
 
d = dict()
for k in key_all:
    d[k] = []
 
ans = 0
l = []
import bisect
 
for i in range(1, m+1):
    if i in key_all:
        for v in d[i]:
            bisect.insort(l, v)
 
    # print(l)
 
    if l != []:
        ans += l[-1]
        l.pop()
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = []
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
l.sort(reverse=True,key= lambda x:x[0])
l.sort(reverse=True,key= lambda x:x[1])

da = 0
mon = 0
for i in range(n):
    a,b = l[i]

    if da + a <= m:
        mon += b
    else:
        continue
    da += 1
print(mon)

Submission status: Wrong Answer

Solution code:
import bisect

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        bisect.insort_right(wa, task[j][1])
        j += 1
    print(wa)
    if wa:
        ans += wa[-1]
        del (wa[-1])

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = 0
day = 0
li = []

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

lis = sorted(li, key=lambda item: (item[1], item[0]), reverse=True)
#print(lis)
for i in range(n):
	a, b = lis[i]
	if a + day <= m:
		count += b
		day += 1
print(count)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())

AB = [[int(i) for i in input().split()] for i in range(N)]

ans = 0
for i in range(M):
    h = 0
    hp = 0
    f = False
    for a_b in AB:
        b = 0
        if i + a_b[0] <= M:
            if h <= a_b[1] and b < a_b[0]:
                h = a_b[1]
                hp = a_b
                b = a_b[0]
                f = True
        else:
            AB.remove(a_b)
    if f:
        AB.remove(hp)
        ans += h

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

lists = [[] for _ in range(10**5 + 1)]
availables = deque()
for A, B in ABs:
    bisect.insort(lists[A], B)

ans = 0
for i in range(1, M + 1):
    tmp = []
    while lists[i] or availables:
        if not lists[i]:
            tmp.extend(reversed(availables))
            break
        elif not availables:
            tmp.extend(reversed(lists[i]))
            break
        if availables[-1] < lists[i][-1]:
            tmp.append(availables.pop())
        else:
            tmp.append(lists[i].pop())
    availables = tmp
    availables.reverse()
    if availables:
        ans += availables.pop()

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        [a, b] = [int(number) for number in input().split()]
        #money_par_day = b / a
        part_times.append([b, a])
        #part_times.sort(reverse=True)
    part_times = sorted(part_times, key = lambda x: (x[0], x[1]), reverse=True)
    money = 0
    day = 0

    #while day <= M:

    for part_time in part_times:
        [b,a] = part_time
        if a + day <= M:
            day += 1
            money += b
        else:
            continue
    print(money)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

works = []
for i in range(n):
    works.append(list(map(int,input().split())))
works = sorted(works, key=lambda x:(x[1],x[0]),reverse=True)

ans = 0
i = 0
for day,money in works:
    if i+day <= m:
        ans += money
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
pay = []
for _ in range(n):
    a, b = map(int, input().split())
    pay.append((b, a))
pay = sorted(pay, reverse=True)
days = 0
ans = 0
for i in range(n):
    if days + pay[i][1] <= m:
        days += 1
        ans += pay[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


def main():
    n, m = map(int, input().split())
    jobs = [list(map(int, input().split())) for _ in range(n)]

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

    # ary = [0]*m
    # ary = [i for i in range(m, 0, -1)]
    ary = [1]*m
    ans = 0
    md = m
    # for i in range(m-1, -1, -1):
    #     ary[i] = m-i if m-i < md else md
    #     md -= m-i
    #     if md <= 0:
    #         break

    # print(ary)
    for job in jobs:
        if job[0] > m:
            continue
        if ary[job[0]-1] > 0:
            ans += job[1]
            ary[job[0]-1] -= 1
        else:
            for i in range(job[0]-1, m):
                if ary[i] > 0:
                    ans += job[1]
                    ary[i] -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = []
p = 0
for i in range(1, m+1):
  while p<len(work_list) and work_list[p][0]<=i:
    if max_f:
      max_f.append(max(max_f[-1], work_list[p][1]))
    else:
      max_f.append(work_list[p][1])
    p += 1
  if max_f:
    ans += max_f[-1]
    _ = max_f.pop(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = []
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
l.sort(reverse=True,key= lambda x:x[0])
l.sort(reverse=True,key= lambda x:x[1])
print(l)
da = 0
mon = 0
for i in range(n):
    a,b = l[i]

    if da + a <= m:
        mon += b
        da += 1
    else:
        continue
print(mon)

Submission status: Wrong Answer

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

an = []

for _ in range(n):
    a, b = map(int, input().split())
    an.append((a,b))
#an.sort( key = lambda v:v[0]*-1)
#an.sort( key = lambda v:v[1]*-1)
an.sort( key = lambda v: (v[1]*-1, v[0]*-1))
#print('--')
#print(an)
d = 1
ans = 0
while d <= m:
    print("D is {}".format(d))
    for i, job in enumerate(an):
        if job[0] <= d:
            #print("d is {}".format(d))
            ans += job[1]
            #print("do {} {}".format(job[0], job[1]))
            del an[i]
            print(an)
            break
    d += 1

print(ans)

Submission status: Wrong Answer

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

q = []
heapq.heapify(q)
for i in range(N):
    a,b = map(int, input().split())
    heapq.heappush(q,(a,-b))

# dayが小さい方から順番に取っていく(同じdayなら+1して値に埋めていく)
rewards = []
prev = 0
cnt = 0
cnt_all = 0
while q:
    a,b = heapq.heappop(q)
    b *= -1
    if prev == a:
        cnt += 1
    else:
        cnt = 0

    if a + cnt - 1 >= len(rewards):
        if a+cnt-1 < M:
            rewards.append(b)
    else:
        if rewards[a+cnt-1] <= b:
            rewards = rewards[:a+cnt-1] + [b] + rewards[a+cnt-1:]
    prev = a
    # print(rewards)

print(sum(rewards[:M]))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
work = [list(map(int, input().split())) for i in range(n)]
#from operator import itemgetter
#work = sorted(work,key=itemgetter(1),reverse=True)
count = 0
for i in range(1,m+1):
  for j in range(len(work)):
    hit = 0
    if work[j][0] <= i and work[j][1] >= hit:
      hit = work[j][1]
  count += hit
print(count)

Submission status: Wrong Answer

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

A = [0]*N
B = [0]*N

for n in range(N):
  B[n],A[n] = map(int,input().split())
  
CA = A
CB = B
CN = N

#F = [True]*N
sr = 0
for m in range(M):
  cr = 0
#  ci = -1
  CN = 0
  for n in range(CN):
    if CB[n] <= m+1  and cr<CA[n]:
      #ci = n
      cr = A[n]
    else:
      CA[CN] = A[n]
      CB[CN] = B[n]
      CN += 1
    sr += cr
#  if ci!=-1:
#    sr += cr
#    F[ci] = False
print(sr)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: -x[0])
ab.sort(key = lambda x: -x[1])
f = [0] * M
cnt, ans = 0, 0
bit = BIT(M+1)
for a, b in ab:
    if M-a >= 0 and bit.sum(M-a+1) - bit.sum(1) <= M-a:
        ans += b
        cnt += 1
        if cnt == M:
            break
        bit.add(M-a+1, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = list(map(int,input().split()))
x=[]
for u in range(n):
    x.append(list(map(int,input().split())))
x.sort(key = lambda x:x[1], reverse = True)
q = [-1]*(m)
ans = 0
print(x)
for i in x:
    if(i[0]>m):
        continue
    else:
        y = m-i[0]

        for o in range(y,-1,-1):
            if(q[o]==-1):
                q[o]=0
                ans+=i[1]
                break

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    temp = list(map(int, input().split()))
    AB.append(temp)
AB = sorted(AB, reverse=True)
AB = sorted(AB, reverse=True, key=lambda x: x[1])

# print(AB)

Day = 0
ans = 0

for i in AB:
    if i[0] + Day <= M:
        ans += i[1]
        Day +=1
    if Day == M:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
q=0
for i in range(n):
    p=[int(j) for j in input().split()]
    q=max(q,p[0])
    ab.append(p)
from operator import itemgetter
 
ab.sort(key=itemgetter(1))
ab.reverse()
ab.sort(key=itemgetter(0))
l=[]
import bisect
ans=0
for i in range(1,m+1):
    while True:
        if ab==[]:
            break
        if ab[0][0]<=i:
            insert_index = bisect.bisect_left(l,ab[0][0])  #2
            l.insert(insert_index,ab[0][0])
            del ab[0]
        else:
            break
    if l!=[]:
        ans+=l[-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    if j<N:
        t = task[j]
    while j < N and t[0] == i + 1:
        bisect.insort_right(wa, t[1])
        j += 1
    if wa:
        ans += wa[-1]
        del (wa[-1])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
info = np.asarray([list(map(int, input().split())) for i in range(N)])
#info = sorted(info, key=lambda x:(-x[1], x[0]))
#print(info[:M])

result = 0
for i in range(M, -1, -1):
  try:
  	max_index = np.argmax(info[info.T[0]<=i].T[1])
  	result += info[max_index][1]
  	info[max_index][0] = M+1
  except:
    pass
print(result)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
# AB = [ab for ab in AB if ab[0] <= M]
AB.sort(key=lambda ab: (-ab[1], -ab[0]))

cost_to_day = {}
cost_list = []
for a, b in AB:
    if cost_to_day.get(b) is None:
        cost_to_day[b] = [a]
        cost_list.append(b)
    else:
        cost_to_day[b].append(a)


ans = 0
i = 0
for d in range(1, M+1):
    for cost in cost_list:
        for day in cost_to_day[cost]:
            if day > M - d + 1:
                cost_to_day[cost].remove(day)
            elif day == M - d + 1:
                cost_to_day[cost].remove(day)
                ans += cost

                break
            else:
                break
        else:
            cost_list.remove(cost)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        [a, b] = [int(number) for number in input().split()]
        #money_par_day = b / a
        part_times.append([b, a])
        #part_times.sort(reverse=True)
    part_times = sorted(part_times, key = lambda x: (x[0], x[1]))
    money = 0
    day = 0

    #while day <= M:

    for part_time in part_times:
        [b,a] = part_time
        if a + day <= M:
            day += a
            money += b
        else:
            continue
    print(money)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for k in D :
    D[k] = sorted(D[k], reverse=True)

A = []
for k in D :
    for i in range(min(len(D[k]), M-k+1)) :
        A.append(D[k][i])
A = sorted(A,reverse=True)
ans = sum(A[:M+1])
print(ans)

Submission status: Wrong Answer

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

works = []
for _ in range(N):
    works.append(tuple(map(int, input().split())))

works.sort(key=lambda x: (x[0], -x[1]))
print(works)

selected = [(0, 0)] * M

for i in range(M):
    for work in works:
        if work[0] + i > M+1:
            if selected[i] in works:
                works.remove(selected[i])
            break
        if work[1] > selected[i][1]:
            selected[i] = work
    else:
        if selected[i] in works:
            works.remove(selected[i])

print(sum(s[1] for s in selected))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Lis = [None]*N
reward = 0
for i in range(N):
    Lis[i] = list(map(int,input().split()))
Lis  = sorted(Lis, key = lambda x: x[0], reverse = True)
Lis = sorted(Lis, key = lambda x: x[1], reverse = True)
for k in range(N):
    if M - Lis[k][0] <= 0:
        continue
    else:
        reward += Lis[k][1]
        M -= 1
print(reward)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())
AB.sort(key=lambda x: x[0])
perr(AB)
#  AB_dict = {}
#  for ab in AB:
#      if ab[0] not in AB_dict.keys():
#          AB_dict[ab[0]] = [ab[1]]
#      else:
#          AB_dict[ab[0]].append(ab[1])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()
#  perr(AB_dict)

tmp = []
day = 1
ans = 0
for ab in AB:
    if ab[0] > day:
        tmp.sort()
        if len(tmp) == 0:
            continue
        ans += tmp.pop()
        day += 1
        continue
    else:
        tmp.append(ab[1])
print(ans)
#  ans = 0
#  tmp = []
#  crr = 0
#  for i in range(1, M+1):
#      if crr < N:
#          if AB[crr][0] == i:
#              while True:
#                  if crr == N:
#                      break
#                  if AB[crr][0] != i:
#                      break
#                  tmp.append(AB[crr][1])
#                  crr += 1

#      perr('tmp')
#      perr(tmp)
#      if len(tmp) == 0:
#          continue

#      max_v = max(tmp)
#      ans += max_v
#      tmp.remove(max_v)
#      #  tmp.sort()
#      #  ans+=tmp.pop()

#  """
#  貪欲か？
#  日が長くて報酬の高いものから選んでいく
#  そうすると
#  10 1
#  9 10
#  みたいなときに10 1のほうから選んでしまうからだめ
#  残り日数を意識
#  残ってる中で最も報酬の高いものから？
#  2 10
#  1 11
#  のパターンで、先に1をやってしまうためだめ
#  2 10
#  1 11
#  1 15
#  のパターンで、1 1をやるのが正解
#  """

#  #  ans = 0
#  #  tmp = []
#  #  for i in range(1, M+1):
#  #      # 残りi日
#  #      if i in AB_dict.keys():
#  #          tmp += AB_dict[i]
#  #      perr('tmp')
#  #      perr(tmp)
#  #      if len(tmp) == 0:
#  #          continue
#  #      tmp.sort()
#  #      #  max_v = max(tmp)
#  #      #  ans += max_v
#  #      ans += tmp.pop()
#  print(ans)

Submission status: Wrong Answer

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

anls = [[-1]*n]*m
anls[0][0] = 0
ans = 0
als = []
bls = []

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

for i in range(m):
    for j in range(n):
        if anls[i][j] >= 0:
            if i + als[j] <= m-1:
                anls[j][i + als[j]] += bls[j]
                if ans < anls[j][i + als[j]]:
                    ans = anls[j][i + als[j]]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
arr1 = sorted(arr, key=lambda x: (x[1],x[0]), reverse=True)
arr2 = sorted(arr, key=lambda x: x[0], reverse=True)
sums = 0
sums1 = 0
j = 0
for i in range(n):
  a = arr1[i][0]
  if i+a <= m:
    sums +=arr1[i][1]
  else:
    continue
for i in range(n):
  b = arr2[i][0]
  if i+b <= m:
    sums1 += arr2[i][1]
  i -= 1
print(max(sums,sums1))

Submission status: Wrong Answer

Solution code:
def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        [a, b] = [int(number) for number in input().split()]
        #money_par_day = b / a
        part_times.append([b, a])
        #part_times.sort(reverse=True)
    part_times = sorted(part_times, key = lambda x: (x[0], x[1]))
    print(part_times)
    money = 0
    day = 0

    #while day <= M:

    for part_time in part_times:
        [b,a] = part_time
        if a + day <= M:
            day += a
            money += b
        else:
            continue
    print(money)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
jobs = []
for i in range(n):
    jobs.append(tuple(map(int, input().split())))
jobs.sort(key=lambda x:(x[0], x[1]), reverse=True)
count = 0
for i in range(m+1):
    while len(jobs) > 0:
        job = jobs.pop(0)
        if i + job[0] <= m:
            count += job[1]
            break
print(count)

Submission status: Wrong Answer

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

for i in range(1, N+1):
  for j in range(1,M+1):
    if j >= A[i-1]:
      dp[i][j] = max(dp[i-A[i-1]][j]+B[i-1],dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[N][M])

Submission status: Wrong Answer

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

ans = 0
i = 0
for day,money in works:
    if i+day <= m:
        ans += money
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# 2019/08/10

import sys

input=sys.stdin.readline

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

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

dp=[0]*(m+1)
pre=s[0][0]
i=0

for k,v in s:
    j=0
    if k==pre:
        i+=1
    else:i=k
    if k>m:break
    if dp[i]<v:dp[i]=v
    else:
        while j+i<m  and dp[i+j]>=v:
            j+=1
        if dp[i+j]<v:
            dp[i+j]=v
    
print(sum(dp))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ansl = [0]*(m)
anslmax = [0]*(m)
for i in range(0,n):
    a,b=map(int,input().split())
    for j in range(m-a,-1,-1):
        if ansl[j]<b:
            ansl[0:j] = ansl[1:j+1]
            ansl[j]=b
            break
print(sum(ansl))

Submission status: Wrong Answer

Solution code:
n, m  = map(int, input().split())
red = []
blue = []
for _ in range(n):
    a, b = map(int, input().split())
    red.append([a, b])
for i in range(m):
    c, d = [i, 0]
    blue.append([c, d])
blue.sort()
red.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b in blue:
    for i, r in enumerate(red):
        if (r[0] < b[0]) & (r[1] < b[1]):
            ans += 1
            red.pop(i)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split()))[::-1] for _ in range(N)]
    logging.info("Hello!")

    sorted_A_B = sorted(A_B, reverse=True)
    logging.info(sorted_A_B)


    total = 0
    for i in range(N):
        if i >= M:
            break
        
        if sorted_A_B[i][1] + i <= M and sorted_A_B[i][0] != -1:
            total += sorted_A_B[i][0]
            sorted_A_B[i][0] = -1


    print(total)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
box=[list(map(int,input().split())) for i in range(n)]
day={}
day_ans={i:0 for i in range(1,m+1)}

for i in box:
    if i[0] in day:
        day[i[0]] +=[i[1]]
    else:
        day[i[0]]=[i[1]]

for x,y in day.items():
    max_point=max(y)
    day_ans[x]=max_point
    day[x].remove(max_point)

while 1:
    for x,y in day.items():
        try:
            max_point=max(y)
            for i in range(x,m+1):
                if day_ans[i]==0:
                    day_ans[i]=max_point
                    day[x].remove(max_point)
                    continue
        except:continue
    break
count=0
for x,y in day_ans.items():
    count +=y
print(count)

Submission status: Wrong Answer

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

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

L = sorted(L, key=itemgetter(1), reverse=True)

total = 0
for l in L:
  if(M == 0):
    break
  if(l[0] <= M + 1):
    total += l[1]
    M -= 1

print(total)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  l+=[[a,b]]
l.sort(reverse=1,key=lambda x:x[1])
#l.sort(reverse=0,key=lambda x:x[0])

a=[0 for i in range(m)]
ans=0
for i in range(min(n,m)):
  for j in range(l[i][0]-1,m):
    if a[j]<l[i][1]:
      a[j]=l[i][1]
      break

#print(a)
print(sum(a))

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_val: 区間[l, r)の値とindex(同値があった場合は一番右)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        # 1段目(最下段)の初期化
        for i in range(n2):
            self.index[i+n2] = i
        # 2段目以降の初期化
        for i in range(n2-1, -1, -1):
            # 全部右の子の値に更新
            self.index[i] = self.index[i*2+1]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[right]:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            else:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            i >>= 1
 
    def get_val(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        return self._get_val(a, b, 1, 0, self.n2)
 
    def _get_val(self, a, b, k, l, r):
        """
        [a, b)の値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での最小値。共通区間を持たない場合は初期値
        """
        # 範囲外なら初期値
        if r <= a or b <= l:
            return (self.init, -1)
        # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return (self.tree[k], self.index[k])
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        left = self._get_val(a, b, k << 1, l, m)
        right = self._get_val(a, b, (k << 1) + 1, m, r)
        if self.func(left[0], right[0]) == right[0]:
            return right
        else:
            return left

N, M = MAP()
days = [[] for i in range(10**5+1)]
for i in range(N):
    a, b = MAP()
    days[a].append(b)

sti = SegTreeIndex(10**5+1, max, -INF)
for i in range(10**5+1):
    days[i].sort()
    if len(days[i]):
        sti.update(i, days[i][-1])

ans = 0
for i in range(M):
    val, idx = sti.get_val(0, M-i+1)
    if val == -INF:
        break
    ans += val
    days[idx].pop(-1)
    if len(days[idx]):
        sti.update(idx, days[idx][-1])
    else:
        sti.update(idx, -INF)
print(ans)

Submission status: Wrong Answer

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

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

print(sum(nums))

Submission status: Wrong Answer

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=sorted(AB, key=lambda x: (x[1],x[0]))
BA=[x for x in BA[::-1]]

scadule = [0]*M

m=len(BA)
i=0
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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: -x[0])
ab.sort(key = lambda x: -x[1])
f = [0] * M
cnt, ans = 0, 0
bit = BIT(M+1)
for a, b in ab:
    if M-a >= 0 and bit.sum(M-a+1) <= M-a:
        ans += b
        cnt += 1
        if cnt == M:
            break
        bit.add(M-a+1, 1)
print(ans)