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:
def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
    _AB = AB
    _AB = sorted(_AB, key=lambda x: x[1], reverse=True)
    #print(_AB)
    ans = 0
    dayidx = 0
    for i in range(M):
        while dayidx < len(_AB):
            day, point = _AB[dayidx]
            if day <= M-i:
                #rint(day, point)
                ans += point
                dayidx += 1
                break
            dayidx += 1
        if dayidx >= len(_AB):
            break
    print(ans)        


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
    _AB = AB
    for i in range(N):
        if AB[i][0] < M+1:
            _AB = AB[i:]
            break
    _AB = sorted(_AB, key=lambda x: x[1], reverse=True)
    #print(_AB)
    ans = 0
    dayidx = 0
    for i in range(M):
        while dayidx < len(_AB):
            day, point = _AB[dayidx]
            if day <= M-i:
                #rint(day, point)
                ans += point
                dayidx += 1
                break
            dayidx += 1
        if dayidx >= len(_AB):
            break
    print(ans)        


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
    _AB = AB
    for i in range(N):
        if AB[i][0] >= M+1:
            _AB = AB[:i]
            break
    _AB = sorted(_AB, key=lambda x: x[1], reverse=True)
    #print(_AB)
    ans = 0
    dayidx = 0
    for i in range(M):
        while dayidx < len(_AB):
            day, point = _AB[dayidx]
            if day <= M-i:
                #print(day, point)
                ans += point
                dayidx += 1
                break
            dayidx += 1
        if dayidx >= len(_AB):
            break
    print(ans)        


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

N, M = map(int,input().split())
work = [set() for _ in range(10**5+1)]
ava = []
ans = 0

for i in range(N):
    A, B = map(int,input().split())
    work[A].add(-B)

for i in range(1, M+1):
    if len(work[i]) > 0:
        for j in work[i]:
            heappush(ava, j)
    if len(ava) > 0:
        ans -= heappop(ava)
print(ans)

Submission status: Wrong Answer

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

X.sort(key=lambda x: (-x[1], -x[0]))
ans = 0
t = 0
for i in range(N):
    if t + X[i][0] <= M:
        ans += X[i][1]
    t += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
for i in range(N):
  tmp = list(map(int, input().split()))
  eff = [tmp[1]/tmp[0]]
  AB.append(eff+tmp)
AB.sort(reverse=True)
#print(AB)

left_data = M-1
i = 0
r = 0
while left_data > 0:
  if AB[i][1] <= left_data:
    r += AB[i][2]
    left_data -= 1
  else:
    i += 1
    if i == N:
      break
print(r)

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(n):
  ab=[int(x) for x in input().rstrip().split()]
  l.append(ab)

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

now_time=0
ans=0
for a,b in l:
  if (now_time+a)<=m:
    ans+=b
  now_time+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()
AB = []
for _ in range(N):
    a, b = mapint()
    AB.append((b, a))
AB.sort(reverse=True)

ans = 0

cnt = 0
for b, a in AB:
    if cnt>M-a:
        continue
    ans += b
    cnt += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()
AB = []
for _ in range(N):
    a, b = mapint()
    AB.append((a, -b))
AB.sort()

days = [0]*(M+1)
for a, b in AB:
    a -= 1
    if a>M:
        continue
    if days[a]==0:
        days[a] = b
    else:
        idx = bisect_right(days[a:], b)
        if a+idx>M:
            continue
        days[a+idx] = b

print(-sum(days[::-1][1:]))

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import bisect

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    ab_s.sort(key=lambda xx: [-xx[1], -xx[0]])
    # ab_s.sort(key=lambda xx: -xx[1])

    work_date = min(n, m)
    choise_ab_s = ab_s[0:work_date]
    no_choise_ab_s = ab_s[work_date:]

    choise_ab_s.sort(key=lambda xx: -xx[0])

    date = 0
    ans = 0
    for choise_ab in choise_ab_s:

        if choise_ab[0] + date <= m:
            ans += choise_ab[1]
            date += 1
        else:
            if len(no_choise_ab_s) == 0:
                continue
            for cnt, no_choise_ab in enumerate(no_choise_ab_s):
                if no_choise_ab[0] + date <= m:
                    ans += no_choise_ab[1]
                    date += 1
                    break
            no_choise_ab_s = no_choise_ab_s[cnt + 1:]

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_original_1(self):
        test_input = """3 4
4 210
4 150
3 150"""
        output = """360"""
        self.assertIO(test_input, output)

    def test_original_2(self):
        test_input = """2 1
1 10
1 20
"""
        output = """20"""
        self.assertIO(test_input, output)

    def test_original_3(self):
        test_input = """1 2
1 10
"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_original_4(self):
        test_input = """5 3
4 50
4 50
3 10
3 10
1 10
"""
        output = """20"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import bisect

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    ab_s.sort(key=lambda xx: -xx[1])

    work_date = min(n, m)
    choise_ab_s = ab_s[0:work_date]
    no_choise_ab_s = ab_s[work_date:]

    choise_ab_s.sort(key=lambda xx: -xx[0])

    date = 0
    ans = 0
    for choise_ab in choise_ab_s:

        if choise_ab[0] + date <= m:
            ans += choise_ab[1]
            date += 1
        else:
            if len(no_choise_ab_s) == 0:
                continue
            for cnt, no_choise_ab in enumerate(no_choise_ab_s):
                if no_choise_ab[0] + date <= m:
                    ans += no_choise_ab[1]
                    date += 1
                    break
            no_choise_ab = no_choise_ab[cnt+1:]

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_original_1(self):
        test_input = """3 4
4 210
4 150
3 150"""
        output = """360"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行1項目 n = int(input())
    #   1行2項目 x, y = map(int, input().split())
    #   1行N項目 x = list(map(int, input().split()))
    #   N行1項目 x = [int(input()) for i in range(n)]
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    #   1行1項目(1文字ずつリストに入れる場合) x = list(input())
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    ab_s.sort(key=lambda xx: [-xx[1], -xx[0]])

    now_data = 0
    ans = 0
    for ab in ab_s:
        if ab[0] + now_data <= m:
            ans += ab[1]
            now_data += 1

    print(ans)



# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_original_1(self):
        test_input = """3 4
4 210
4 150
3 150"""
        output = """360"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行1項目 n = int(input())
    #   1行2項目 x, y = map(int, input().split())
    #   1行N項目 x = list(map(int, input().split()))
    #   N行1項目 x = [int(input()) for i in range(n)]
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    #   1行1項目(1文字ずつリストに入れる場合) x = list(input())
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(n)]

    ab_s.sort(key=lambda xx: [-xx[1], -xx[0]])

    now_data = 0
    ans = 0
    for ab in ab_s:
        if ab[0] + now_data <= m:
            ans = ab[1]
            now_data += 1

    print(ans)



# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 4
4 3
4 1
2 2"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 3
1 2
1 3
1 4
2 1
2 3"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """1 1
2 1"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
N,M = map(int,input().split())
A = [[] for _ in range(M+1)]
#HQ = []
for i in range(N):
  a,b = map(int,input().split())
  if a < M:
    A[a].append(b)
#print(A)
ans = 0
L = []
for day in range(1,M+1):
  for t in A[day]:
    heappush(L,-t)
  #print(L)
  if not L:
    continue
  temp = heappop(L)
  ans += -temp
print(ans)

Submission status: Wrong Answer

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

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

x = 0
res = 0

hq = []
heapq.heapify(hq)

for i in range(M):
    for j in range(x, N):
        if AB[j][0] > i+1:
            x = j
            break
        heapq.heappush(hq, AB[j][1]*-1)
    
    if hq:
        res += heapq.heappop(hq)*-1

print(res)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from collections import deque

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

ab.sort(key=itemgetter(1, 0))
ab = deque(ab)

ans = 0
while ab:
    a, b = ab.pop()
    if a <= m:
       ans += b
       m -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort(key= lambda x:x[1])
a = a[::-1]
now = 0
ans = 0
for i in range(m):
    while((m-i) < a[now][0]):
        if now == n-1:
            break
        else:
            now += 1
    if a[now][0] <= (m-i):
        ans += a[now][1]
        now += 1
    if now == n:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n , m = map(int,input().split())
kouho = [[] for i in range(m)]
hosyu = [0 for i in range(m)]
for i in range(n):
    a , b = map(int,input().split())
    if a <= m:
        kouho[a-1].append(-b)
for i in reversed(range(m)):
    now = i
    p = 0
    heapq.heapify(kouho[i])
    while kouho[i]:
        if now == m:
            break
        if p == 0:
            p = heapq.heappop(kouho[i])
        if hosyu[now] > p:
            hosyu[now] = p
            p = 0
        now += 1
print(abs(sum(hosyu)))

Submission status: Wrong Answer

Solution code:
import heapq
n , m = map(int,input().split())
kouho = [[] for i in range(m)]
hosyu = [0 for i in range(m)]
for i in range(n):
    a , b = map(int,input().split())
    if a <= m:
        kouho[a-1].append(-b)
for i in range(m):
    now = i
    p = 0
    heapq.heapify(kouho[i])
    while kouho[i]:
        if now == m:
            break
        if p == 0:
            p = heapq.heappop(kouho[i])
        if hosyu[now] > p:
            hosyu[now] = p
            p = 0
        now += 1
print(abs(sum(hosyu)))

Submission status: Wrong Answer

Solution code:
import heapq
n , m = map(int,input().split())
kouho = [[] for i in range(m)]
hosyu = [0 for i in range(m)]
for i in range(n):
    a , b = map(int,input().split())
    if a < m:
        kouho[a-1].append(-b)
for i in range(m):
    now = i
    p = 0
    heapq.heapify(kouho[i])
    while kouho[i]:
        if now == m:
            break
        if p == 0:
            p = heapq.heappop(kouho[i])
        if hosyu[now] > p:
            hosyu[now] = p
            p = 0
        now += 1
print(abs(sum(hosyu)))

Submission status: Wrong Answer

Solution code:
import heapq
n , m = map(int, input().split())
ab=[[] for i in range(10**5)]

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

que=[]
c=0
while que==[] and c<m:
    if ab[c]!=[]:
        que=ab[c]
    c+=1

heapq.heapify(que)
ans = 0
for i in range(m):
    if i>=c:
        que=list(heapq.merge(que,ab[i]))
    if que:
        ans+=heapq.heappop(que)
print(ans*(-1))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

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

    for _ in range(N):
        a, b = map(int, input().split())
        AB[a-1].append(-b)

    ans = 0
    heap = []
    for a in range(M):
        for b in AB[a]:
            heappush(heap, b)
        if heap:
            ans -= heappop(heap)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
A=[0]*N #ラグ
B=[0]*N #報酬
C=[0]*N
for i in range(N):
    A[i],B[i]= map(int,input().split())
    C[i]=[A[i],B[i]]
   
C.sort(key=lambda x:x[0],reverse=True) #ラグは長いものから候補にして考えてみる
C.sort(key=lambda x:x[1],reverse=True) #報酬を最初にもってくる
D=deque(C)

i=0
reward=0
#print(C)

for i in range(M):
    while D:
        a=D.popleft()
        if i+a[0]<=M:
            reward += a[1]
            break
    #print(a,reward)
   
print(reward)

Submission status: Wrong Answer

Solution code:
import heapq

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 - 1 < M:
        jobs[A-1].append(B)

q = []
heapq.heapify(q)
ans = 0
for i in range(M):
    for j in jobs[i]:
        q.append(-j)
    if len(q) != 0:
        ans += -heapq.heappop(q)

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    A, B = map(int, input().split())
    jobs.append((A-1, B))

jobs = sorted(jobs, key=lambda x: x[1], reverse=True)
used = [0] * M
ans = 0
cnt = 0

for job in jobs:
    if job[0] >= M:
        continue
    if used[job[0]] >= M - job[0]:
        continue
    else:
        used[job[0]] += 1
        ans += job[1]
        cnt += 1
        if cnt == M:
            break

print(ans)

Submission status: Wrong Answer

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

AB = []
for _ in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))
AB = sorted(AB, key=lambda x: (-x[1], -x[0]))

ans = 0
for A, B in AB:
    if A <= M:
        ans += B
        M -= 1
        if M == 0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
jobs = []
for _ in range(N):
  jobs.append(list(map(int,input().split())))
jobs.sort(key= lambda x: (-x[1],-x[0]))

res = 0
j = 0
for d in range(M):
  while j<N:
    i,s = jobs[j]
    if d+i <= M:
      res += s
      break
    j += 1
  j += 1

print(res)

Submission status: Wrong Answer

Solution code:
import heapq
N,M = map(int,input().split())
jobs = []
for _ in range(N):
  j = list(map(int,input().split()))
  if j[0] > M: continue
  jobs.append(((-j[1],-j[0]), j[0]))
heapq.heapify(jobs)

res = 0
for d in range(M):
  while jobs:
    t,i = heapq.heappop(jobs)
    s,_ = t
    if d+i <= M:
      res += -s
      break

print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort(key = lambda x:x[1])
day = M
ans = 0
for i in range(N):
    if a[N - 1 - i][0] <= day:
        ans += a[N - 1 - i][1]
        day -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x:(-x[1], x[0]))
ans = 0
MM = 1
while MM <= M:
  a, b = ab.pop(0)
  if MM >= a:
    ans += b
  else:
    ab += [[a,b]]
  MM += 1
  if len(ab) == 0:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
from heapq import *
N,M=map(int,input().split())
bait=[list(map(int,input().split())) for _ in range(N)]
daybait=[[0,0] for _ in range(M)]
for i in range(N):
    v1=bait[i][0]
    v2=bait[i][1]
    bait[i][0]=-v2
    bait[i][1]=v1
#print(bait)
#l=[-float("inf"),1,2,3,4,5,6,7,8,9,10]
#l=[0,1,2,...,M-1]で初期化
#day=xのときl[M-x]=l[M-x-1](M-x>0),-float("inf")(M-x==0)とする
#
l=[i for i in range(M)]
q=[]
heapify(q)
for i in bait:
    heappush(q,i)
#print(q,l)
length=N
incomes=[0 for _ in range(M)]
while length>0:
    income,day=heappop(q)
    length=length-1
    if (0<=M-day):
        days=l[M-day]
        if days!=float("inf"):
            if incomes[days]==0:
                incomes[days]=-income
                if days>0:
                    l[days]=l[days-1]
                else:
                    l[days]=float("inf")
    #print(incomes)
    #print()
    #print(q)
    #input()
print(sum(incomes))

Submission status: Wrong Answer

Solution code:
import collections
import heapq
n,m = map(int,raw_input().split(' '))

elems = [map(int, raw_input().split(' ')) for _ in range(n)]
heap = []
chosen = []

j = 0
cumul = 0
for i in range(1,m+1):

	while(j < len(elems) and elems[j][0] <= i): 
		heapq.heappush(heap,-elems[j][1])
		j+=1
	if heap:
		cumul -= heapq.heappop(heap)

print cumul

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab.sort(reverse=True, key=lambda x: (x[1], x[0]))

    ans = 0
    d = 0

    for a, b in ab:
        if a + d <= m:
            ans += b
            d += 1
        if d == m:
            break
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab.sort(reverse=True, key=lambda x: (x[1], x[0]))

    ans = 0
    d = 0

    for a, b in ab:
        if a + d <= m:
            ans += b
            d += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int,raw_input().split(' '))
h = [0] * (m+1)
for _ in range(n):
	a,b =  map(int, raw_input().split(' '))
	for d in range(m, -1, -1):
		if d - a >=0: h[d] = max(h[d], h[d-a] + b)

print h[m]

Submission status: Wrong Answer

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

N, M = map(int, input().split())
BA = []
for _ in range(N):
    ab = list(map(int, input().split()))
    a = ab[0]
    b = ab[1]
    BA.append((b,a))
BA.sort(reverse=True)

now = 0
ans = 0
for ba in BA:
    a, b = ba[1], ba[0]
    if a > M - now:
        continue
    ans += b
    now += 1
print(ans)

Submission status: Wrong Answer

Solution code:

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

AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append([A, B, i])
    
AB.sort(reverse=True)

#print(AB)

day = 0
idx = 0
count = 0
while day < M:
    for i in range(idx, N):
        if AB[i][0] + day <= M:
            #print(AB[i:])
            ab = AB[i:]
            ab.sort(key=lambda x: x[1], reverse=True)
            #print(ab)
            idx = i + 1
            count += ab[0][1]
            AB[ab[0][2]][1] = 0
            break
    day += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import heapq  # heapqライブラリのimport
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
lsta=[set() for i in range(10**5+1)]
lst=[]
ans=0
for i in range(N):
 A,B=map(int,input().split())
 lsta[A].add(-B)
heapq.heapify(lst)  # リストを優先度付きキューへ
for i in range(1,M+1):
 for j in lsta[i]:
  heapq.heappush(lst, j)
 if lst!=[]:
  ans+=heapq.heappop(lst)
print(-ans)

Submission status: Wrong Answer

Solution code:
import heapq  # heapqライブラリのimport
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
lst=[]
for i in range(N):
 A,B=map(int,input().split())
 lst.append((A,-B))
heapq.heapify(lst)  # リストを優先度付きキューへ
ct=0
noko=1
ans=0
while  lst!=[]:
 c=heapq.heappop(lst) 
 if c[0]>M:
  break
 elif noko>0 or c[0]>ct:
  noko+=(-1+c[0]-ct)
  ct=c[0]
  ans+=c[1]
print(-ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A:
    continue
  for _ in range(br(A,latest)):
    A.pop(0)
    works.insert(br(works,B[0]),B[0])
    B.pop(0)
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import heapq
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i <= m:
            heapq.heappush(l[i], -j)

    ans = 0
    h = []
    for i in range(1, m + 1):
        g = heapq.merge(h, l[i])
        h = list(g)
        if len(h) > 0:
            x = heapq.heappop(h)
            ans += x

    print(-ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    c = list(zip(ab[::2], ab[1::2]))
    c = sorted(c, key=lambda x: (-x[1], -x[0]))

    q = deque(c)
    ans = 0
    while m and q:
        a, b = q.popleft()
        if a <= m:
            ans += b
            m -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    c = list(zip(ab[::2], ab[1::2]))
    c.sort(key=lambda x: (-x[1], -x[0]))  # date -> fee

    q = deque(c)
    ans = 0
    while m and q:
        x, y = q.popleft()
        if x <= m:
            ans += y
            m -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import heapq

readline = stdin.buffer.readline

INF = 10 ** 10

# M日後まで得られる報酬の合計の最大値
N, M = [int(x) for x in readline().split()]

#Ai日後にBiの金
AB = [tuple(map(int, readline().split())) for _ in range(N)]


# 金が貰えて時間がかかる順にソート
AB.sort(key=lambda x: (x[1], x[0]), reverse=True)
AB = deque(AB)

ans = 0

while(AB):
    A, B = AB.popleft()
    if A <= M:
        ans += B
        M -= 1

    if (M <= 0):
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import heapq

readline = stdin.buffer.readline

INF = 10 ** 10

# M日後まで得られる報酬の合計の最大値
N, M = [int(x) for x in readline().split()]

#Ai日後にBiの金
AB = [tuple(map(int, readline().split())) for _ in range(N)]


# 金が貰えて時間がかかる順にソート
AB.sort(key=lambda x: (x[1], x[0]), reverse=True)
AB = deque(AB)

print(AB)

ans = 0

while(AB):
    A, B = AB.popleft()
    if A <= M:
        ans += B
        M -= 1

    if (M <= 0):
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
import heapq

readline = stdin.buffer.readline

INF = 10 ** 10

# M日後まで得られる報酬の合計の最大値
N, M = [int(x) for x in readline().split()]

#Ai日後にBiの金
AB = [tuple(map(int, readline().split())) for _ in range(N)]


# 金が貰えて時間がかかる順にソート
AB.sort(key=lambda x: (x[1], x[0]), reverse=True)
AB = deque(AB)

ans = 0

while(AB):
    A, B = AB.popleft()
    if A <= M:
        ans += B
        M -= 1

    if (M < 0):
        break

print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    if m < ab[i][0]:
        continue
    if day == 1:
        break
    if day - ab[i][0] >= 0:
        ans += ab[i][1]
        day -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
num = sorted([list(map(int, input().split())) for i in range(n)], key = lambda x: x[0])

s = []
heapq.heapify(s)

for i in range(1, m + 1):
  for j in num:
    if(j[0] <= i):
       heapq.heappush(s, j[1])
    else:
      break

print(sum(s))

Submission status: Wrong Answer

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