Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    #print("find_lt"+str(i))
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    c_c_dict = {}
    for card in cards:
        if card not in c_c_dict:
            c_c_dict[card] = 1
        else:
            c_c_dict[card] += 1

    not_duplicated_cards = list(set(cards))
    #print(not_duplicated_cards)


    for s in S:
        b = s[0]
        c = s[1]
        """
        if c >= cards[-1]:
            cards = cards[b:] + [c for _ in range(b)]
            #print(cards)
            continue
        """
        #if c > cards[0]:
        i = 0
        if c > not_duplicated_cards[i]:
            """
        for i in range(b):
            if c > cards[i]:
                cards[i] = c
            else:
                break
        """

            while(True):
                diff = c_c_dict[not_duplicated_cards[i]] - b
                if diff <= 0:
                    #raise
                    #print(c_c_dict)
                    if c not in c_c_dict:
                        c_c_dict[c] = c_c_dict[not_duplicated_cards[i]]
                        c_c_dict[not_duplicated_cards[i]] = 0
                        _part_cards = not_duplicated_cards[1:]
                        _s_l = find_lt(_part_cards, c)
                        #if _s_l != 0:
                        not_duplicated_cards = _part_cards[:_s_l] + [c] + _part_cards[_s_l:]
                        """
                        else:
                            not_duplicated_cards = not_duplicated_cards + [c]
                        """
                    else:
                        c_c_dict[c] += c_c_dict[not_duplicated_cards[i]]
                        c_c_dict[not_duplicated_cards[i]] = 0
                        del not_duplicated_cards[i]
                        i += 1
                    #print(c_c_dict)
                else:
                    #print(not_duplicated_cards)
                    c_c_dict[not_duplicated_cards[i]] -= b
                    if c not in c_c_dict:
                        c_c_dict[c] = b
                        _part_cards = not_duplicated_cards[:]
                        _s_l = find_lt(_part_cards, c)
                        #if _s_l != 0:
                        #print(not_duplicated_cards)
                        not_duplicated_cards = _part_cards[:_s_l] + [c] + _part_cards[_s_l:]
                        #print(not_duplicated_cards)
                        """
                        else:
                            print(not_duplicated_cards)
                            not_duplicated_cards = not_duplicated_cards + [c]
                            print(not_duplicated_cards)
                        """
                    else:
                        c_c_dict[c] += b
                        i += 1
                b -= c_c_dict[cards[i]]
                if b <= 0:
                    break
                if i >= len(not_duplicated_cards):
                    break
            #print(c_c_dict)
            """
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
            """
        else:
            break

    #print(not_duplicated_cards)

    return sum([card * c_c_dict[card] for card in not_duplicated_cards])

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    #print("find_lt"+str(i))
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    c_c_dict = {}
    for card in cards:
        if card not in c_c_dict:
            c_c_dict[card] = 1
        else:
            c_c_dict[card] += 1

    not_duplicated_cards = list(set(cards))
    print(not_duplicated_cards)


    for s in S:
        b = s[0]
        c = s[1]
        """
        if c >= cards[-1]:
            cards = cards[b:] + [c for _ in range(b)]
            #print(cards)
            continue
        """
        #if c > cards[0]:
        i = 0
        if c > not_duplicated_cards[i]:
            """
        for i in range(b):
            if c > cards[i]:
                cards[i] = c
            else:
                break
        """

            while(True):
                diff = c_c_dict[not_duplicated_cards[i]] - b
                if diff <= 0:
                    #raise
                    print(c_c_dict)
                    if c not in c_c_dict:
                        c_c_dict[c] = c_c_dict[not_duplicated_cards[i]]
                        c_c_dict[not_duplicated_cards[i]] = 0
                        _part_cards = not_duplicated_cards[1:]
                        _s_l = find_lt(_part_cards, c)
                        #if _s_l != 0:
                        not_duplicated_cards = _part_cards[:_s_l] + [c] + _part_cards[_s_l:]
                        """
                        else:
                            not_duplicated_cards = not_duplicated_cards + [c]
                        """
                    else:
                        c_c_dict[c] += c_c_dict[not_duplicated_cards[i]]
                        c_c_dict[not_duplicated_cards[i]] = 0
                        del not_duplicated_cards[i]
                        i += 1
                    print(c_c_dict)
                else:
                    print(not_duplicated_cards)
                    c_c_dict[not_duplicated_cards[i]] -= b
                    if c not in c_c_dict:
                        c_c_dict[c] = b
                        _part_cards = not_duplicated_cards[:]
                        _s_l = find_lt(_part_cards, c)
                        #if _s_l != 0:
                        print(not_duplicated_cards)
                        not_duplicated_cards = _part_cards[:_s_l] + [c] + _part_cards[_s_l:]
                        print(not_duplicated_cards)
                        """
                        else:
                            print(not_duplicated_cards)
                            not_duplicated_cards = not_duplicated_cards + [c]
                            print(not_duplicated_cards)
                        """
                    else:
                        c_c_dict[c] += b
                        i += 1
                b -= c_c_dict[cards[i]]
                if b <= 0:
                    break
                if i >= len(not_duplicated_cards):
                    break
            print(c_c_dict)
            """
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
            """
        else:
            break

    print(not_duplicated_cards)

    return sum([card * c_c_dict[card] for card in not_duplicated_cards])

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    for s in S:
        b = s[0]
        c = s[1]
        if c >= cards[-1]:
            cards = cards[b:] + [c for _ in range(b)]
            #print(cards)
            continue
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    i = 1
    if i < len(S):
        while(True):
            b = S[i][0]
            c = S[i][1]
            if S[i-1][1] == c:
                S[i-1][0] += b
                del S[i]
                i -= 1
            i += 1
            if i >= len(S):
                break

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    i = 1
    if i >= len(S):
        while(True):
            b = S[i][0]
            c = S[i][1]
            if S[i-1][1] == c:
                S[i-1][0] += b
                del S[i]
                i -= 1
            i += 1
            if i >= len(S):
                break

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    i = 1
    while(True):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            del S[i]
            i -= 1
        i += 1
        if i < len(S):
            break

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    i = 1
    while(i < len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            del S[i]
            i -= 1
        i += 1

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    """
    cards_d = {}
    for card in cards:
        if not in cards_d:
            cards_d[card] = 1
        else:
            cards_d[card] += 1
    """
    S = sorted(_S, key=lambda x: x[1])
    i = 1
    while(i < len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            S.pop(i)
            i -= 1
        i += 1
    #print(S)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    #print(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    """
    cards_d = {}
    for card in cards:
        if not in cards_d:
            cards_d[card] = 1
        else:
            cards_d[card] += 1
    """
    """
    S = sorted(_S, key=lambda x: x[1])
    i = 1
    while(i < len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            S.pop(i)
            i -= 1
        i += 1
    #print(S)
    """

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        """
        else:
            break
        """
    #print(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1])
    i = 1
    while(i < len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            S.pop(i)
            i -= 1
        i += 1
    #print(S)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            cards = sorted(cards)
        else:
            break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1])
    for i in range(1, len(S)):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            S[i][0] = 0
            S[i][1] = 0

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            cards = sorted(cards)
        else:
            break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = sorted(A)

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            cards = sorted(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = sorted(A)

    for s in S:
        b = s[0]
        c = s[1]
        for i in range(b):
            if c > cards[i]:
                cards[i] = c
            else:
                break
        cards = sorted(cards)
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = A
    num_cards = len(cards)
    for s in S:
        b = s[0]
        c = s[1]
        min_card_num = min(cards)
        if c > min_card_num:
            for _ in range(b):
                min_card_num = min(cards)
                if c > min_card_num:
                    for i in range(num_cards):
                        if cards[i] == min_card_num:
                            cards[i] = c
                            break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    S = makeIntMatrix(input_string[2:])
    cards = A
    num_cards = len(cards)
    for s in S:
        b = s[0]
        c = s[1]
        for _ in range(b):
            min_card_num = min(cards)
            if c > min_card_num:
                for i in range(num_cards):
                    if cards[i] == min_card_num:
                        cards[i] = c
                        break
    return sum(cards)
    #else:
    #    return len(ra)



def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


Fixed submission:
# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)