Problem p03038 (python)

Fixed submission:
def bin_search(lis, target, low, high):
    while high-low!=1:
        mid = (low+high) // 2
        #print(low, mid, high)
        if lis[mid] == target:
            return mid, 1
        elif lis[mid] > target:
            high = mid
        else:
            low = mid
    if lis[low] == target:
        return low, 1
    elif lis[high] < target:
        return high, 0
    else:
        return low, 0
    
    
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
bc = [[int(i) for i in input().split(" ")] for i in range(m)]
bc = sorted(bc, key=lambda x: x[1])
bc.reverse()
a = sorted(a)
ind = 0
ans = 0
flag = 0
for i in bc:
    if ind >= n:
        break
    if a[min(ind+i[0], n-1)] <= i[1]:
        ans += min(i[0], n-ind)*i[1]
        ind += i[0]
    elif a[ind] >= i[1]:
        ans += sum(a[ind:])
        flag = 1
        break
    else:
        tm = bin_search(a[ind:min(ind+i[0], n-1)], i[1], 0, min(i[0], n-ind))
        ans += i[1]*(tm[0]+1)
        ind += tm[0]+1
        ans += sum(a[ind:])
        flag = 1
        break
if flag == 0:
    ans += sum(a[ind:])
print(ans)

Buggy submission (verdict: Runtime Error):
def bin_search(lis, target, low, high):
    while high-low!=1:
        mid = (low+high) // 2
        #print(low, mid, high)
        if lis[mid] == target:
            return mid, 1
        elif lis[mid] > target:
            high = mid
        else:
            low = mid
    if lis[low] == target:
        return low, 1
    elif lis[high] < target:
        return high, 0
    else:
        return low, 0
    
    
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
bc = [[int(i) for i in input().split(" ")] for i in range(m)]
bc = sorted(bc, key=lambda x: x[1])
bc.reverse()
a = sorted(a)
ind = 0
ans = 0
flag = 0
for i in bc:
    if ind >= n:
        break
    if a[min(ind+i[0], n-1)] <= i[1]:
        ans += min(i[0], n-ind)*i[1]
        ind += i[0]
    elif a[ind] >= i[1]:
        ans += sum(a[ind:])
        flag = 1
        break
    else:
        tm = bin_search(a[ind:ind+i[0]], i[1], 0, i[0])
        ans += i[1]*(tm[0]+1)
        ind += tm[0]+1
        ans += sum(a[ind:])
        flag = 1
        break
if flag == 0:
    ans += sum(a[ind:])
print(ans)

Buggy submission (verdict: Runtime Error):
def bin_search(lis, target, low, high):
    while high-low!=1:
        mid = (low+high) // 2
        #print(low, mid, high)
        if lis[mid] == target:
            return mid, 1
        elif lis[mid] > target:
            high = mid
        else:
            low = mid
    if lis[low] == target:
        return low, 1
    elif lis[high] < target:
        return high, 0
    else:
        return low, 0
    
    
n, m = map(int, input().split())
a = [int(i) for i in input().split(" ")]
bc = [[int(i) for i in input().split(" ")] for i in range(m)]
bc = sorted(bc, key=lambda x: x[1])
bc.reverse()
a = sorted(a)
ind = 0
ans = 0
flag = 0
for i in bc:
    if ind >= n:
        break
    if a[min(ind+i[0], n-1)] <= i[1]:
        ans += min(i[0], n-ind)*i[1]
        ind += i[0]
    elif a[ind] >= i[1]:
        ans += sum(a[ind:])
        flag = 1
        break
    else:
        tm = bin_search(a[ind:ind+i[0]], i[1], 0, i[0])
        ans += i[1]*(tm[0]+1)
        ind += tm[0]+1
        ans += sum(a[ind:])
        flag = 1
        break
if flag == 0:
    ans += sum(a[ind:])
print(ans)