Problem: 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.

Submission attempts (in order):
def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        idx = -1
        max_value = -1
        for j in range(len(ab)):
            if ab[j][0] <= m:
                if max_value <= ab[j][1]:
                    max_value = ab[j][1]
                    idx = j
            else:
                break

        if idx != -1:
            ans += max_value
            ab.pop(idx)

    print(ans)


if __name__ == '__main__':
    p_d()

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

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

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

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

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


if __name__ == '__main__':
    p_e()



    n, m = map(int, input().split())
    a = []
    b = []
    ans = 0

    for _ in range(n):
        s = list(map(int, input().split()))
        a.append(s[0])
        b.append(s[1])

    lv = [a[i] * b[i] for i in range(len(a))]
    li = sorted(zip(lv, a, b), reverse=True)

    for i in range(m):
        for _ in range(len(li)):
            lab = li.pop(0)
            if lab[1] <= m - i:
                ans += lab[2]
                break

    print(ans)



from heapq import heappop, heappush


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

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] == i + 1:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


if __name__ == '__main__':
    p_d()


from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        H = []
        for j, e in enumerate(ab):
            if e[0] <= i:
                heappush(H, (-e[1], j))
                ab.pop(j)
            else:
                break

        if H:
            e = heappop(H)
            ans -= e[0]
            # ab.pop(e[1])

    print(ans)


if __name__ == '__main__':
    p_d()


from collections import defaultdict


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

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

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

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

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


if __name__ == '__main__':
    p_e()


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        idx = -1
        max_value = -1
        for j in range(len(ab)):
            if ab[j][0] <= i:
                if max_value <= ab[j][1]:
                    max_value = ab[j][1]
                    idx = j
            else:
                break

        if idx != -1:
            ans += max_value
            ab.pop(idx)

    print(ans)

from heapq import heappop, heappush


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

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] <= i:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


if __name__ == '__main__':
    p_d()


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted