Problem p03038 (python)

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

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, N
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r - 1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
        B = n - l
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, M
s = 0
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, M
s = 0
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[-1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
s = 0
for B, C in BC:
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    n = len(A)
    if B > n:
        B = n
    if A[B - 1] <= C:
        s += B * C
        if B == n:
            break
        A = A[B:]
    else:
        error
        for a in A[1:B]:
            if a >= C:
                i = A.index(a)
                s += i * C
                s += sum(A[i:])
                break
        break
else:
    s += sum(A)
print(s)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
s = 0
for B, C in BC:
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    n = len(A)
    if B > n:
        B = n
    if A[B - 1] <= C:
        s += B * C
        if B == n:
            break
        A = A[B:]
    else:
        for i in A[1:B]:
            if A[i] >= C:
                s += i * C
                s += sum(A[i:])
                break
        break
#         a, b = 0, B
#         while a + 1 < b:
#             i = a + (b - a) // 2
#             if A[i] >= C:
#                 b = i
#             else:
#                 a = i
#         s += b * C
#         s += sum(A[b:])
#         break
else:
    s += sum(A)
print(s)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
s = 0
for B, C in BC:
    print(A)
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    n = len(A)
    if B > n:
        B = n
    if A[B - 1] <= C:
        s += B * C
        if B == n:
            break
        A = A[B:]
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        s += b * C
        s += sum(A[b:])
        break
else:
    s += sum(A)
print(s)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
s = 0
for B, C in BC:
    A.sort()
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    if B > len(A):
        B = len(A)
    if A[B - 1] <= C:
        s += B * C
        A = A[B:]
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        A[:b] = [C] * b
        s += sum(A)
        break

print(s)

Buggy submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
s = 0
for B, C in BC:
    A.sort()
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    if A[B - 1] <= C:
        s += B * C
        A = A[B:]
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        A[:b] = [C] * b
        s += sum(A)
        break

print(s)