Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
A = [i*-1 for i in A]

import heapq
heapq.heapify(A)

while K:
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    a, b = a*-1, b*-1
    c = (b+1)//2
    d = a - c
    heapq.heappush(A, b*-1)
    heapq.heappush(A, c*-1)
    heapq.heappush(A, d*-1)
    K -= 1

print(sorted(A)[0]*-1)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def is_ok(n):
    cnt = 0
    for a in A:
        if n >= a:
            continue
        cnt += a // n
    return cnt <= K

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, 10**9+1))
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])

BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
for i in range(N+1):
    for j in range(M+1):
        if AL[i] + BL[j] <= K:
            ans = max(ans, i+j)
        else:
            break

print(ans)

Fixed submission:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])
BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
from bisect import bisect_right
for i in range(N+1):
    zan = K - AL[i]
    if zan < 0:
        break
    ind = bisect_right(BL, zan) - 1
    ans = max(ans, i + ind)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])

BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
for i in range(N+1):
    for j in range(M+1):
        if AL[i] + BL[j] <= K:
            ans = max(ans, i+j)

print(ans)

Fixed submission:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AL = [0]
for i in range(N):
    AL.append(AL[-1] + A[i])
BL = [0]
for i in range(M):
    BL.append(BL[-1] + B[i])

ans = 0
from bisect import bisect_right
for i in range(N+1):
    zan = K - AL[i]
    if zan < 0:
        break
    ind = bisect_right(BL, zan) - 1
    ans = max(ans, i + ind)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

A = sorted(A)
ans = 0
for i in range(N):
    for j in range(i-1, -1, -1):
        if A[i] % A[j] == 0:
            break
    else:
        if i == 0 and A[i] == A[i+1]:
            continue
        ans += 1
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
m = max(A)+10
dp = [0] * m

for x in A:
    dp[x] += 1

ans = 0
for i in range(1, m):
    if dp[i]:
        if dp[i] == 1:
            ans += 1
        for j in range(i, m, i):
            dp[j] = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

from fractions import gcd

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = gcd(i, j)
                ans += gcd(x, k) * 3
            else:
                x = gcd(i, j)
                ans += gcd(x, k) * 6
print(ans)

Fixed submission:
K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 3
            else:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 6
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

from itertools import product
kumi = product(range(1, K+1), repeat=3)

from fractions import gcd

memo = [[None for i in range(K+1)] for i in range(K+1)]
# memo2 = {}

ans = 0
for a, b, c in kumi:
    a, b, c = sorted([a, b, c])
    if memo[a][b] is not None:
        v = memo[a][b]
    else:
        v = gcd(a, b)
        memo[a][b] = v
        memo[b][a] = v
    d = gcd(v, c)
    ans += d

print(ans)

Fixed submission:
K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 3
            else:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 6
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] ^ A[j]) % mod
print(ans % mod)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0

for k in range(60):
    zero = 0
    one = 0
    for i in range(N):
        # A[i]のk桁目のbitが0か1か取り出す
        x = (A[i] >> k) & 1
        if x == 0: zero += 1
        else: one += 1
    ans += (2**k * (zero * one)) % mod

print(ans % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]

tree = {i:[] for i in range(1, N+1)}
for a, b in ab:
    tree[a].append(b)
    tree[b].append(a)

stree = sorted(tree.items(), key=lambda x: -len(x[1]))
print(len(stree[0][1]))
start = stree[0][0]

colormap = {i:[0]*(N+1) for i in range(1, N+1)}
from collections import deque
q = deque([start])
visited = {start}
while q:
    n = q.popleft()
    for p in tree[n]:
        if p in visited:
            continue
        i = 1
        while True:
            if i not in colormap[n] and i not in colormap[p]:
                colormap[n][p] = i
                colormap[p][n] = i
                break
            i += 1
        if p not in visited:
            q.append(p)
            visited.add(p)

for a, b in ab:
    print(colormap[a][b])


Fixed submission:
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) # パス先, パスの色でキューに追加
while q:
    v, pc = q.popleft()
    nc = 0 # 使用する色
    for nv, edge in tree[v]: # nv=パス先 edge=abでの順番
        nc += 1
        if nc == pc: # 渡ってきたパスの色と同じなら+1した色にする
            nc += 1
        color[edge] = nc # 使用する色を答えのリストに格納
        q.append((nv, nc))

print(max(color))
print(*color, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))
 
inf = float('inf')
dp = np.full(N+1, inf)
dp[1] = 0
for l, r, c in LRC:
    dp[l:r+1] = np.minimum(dp[l:r+1], dp[l] + c)
 
if dp[-1] < inf:
    print(int(dp[-1]))
else:
    print(-1)

Fixed submission:
N, M = map(int, input().split())
LRC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: (x[0], x[1]))

inf = float('inf')
dp = [inf] * N
dp[0] = 0

for l, r, c in LRC:
    for i in range(r, l, -1):
        if dp[i-1] > dp[l-1] + c:
            dp[i-1] = dp[l-1] + c
        else:
            break

if dp[-1] < inf:
    print(dp[-1])
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
A, B = map(int, input().split())

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

l = cf(A, B)
if len(l) == 0:
    print(1)
else:
    c = 1
    for i in range(len(l)):
        for j in range(i):
            if not coprime(l[i], l[j]):
                break
        else:
            c += 1
    print(c)

Fixed submission:
A, B = map(int, input().split())

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

G = gcd(A, B)
l = make_divisors(G)
l.remove(1)
if len(l) == 0:
    print(1)
else:
    c = 1
    for i in range(len(l)):
        for j in range(i):
            if not coprime(l[i], l[j]):
                break
        else:
            c += 1
    print(c)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
H, W, A, B = map(int, input().split())

bins = []
for i in range(2**W):
    b = bin(i)[2:].zfill(W)
    if b.count('0') == A or b.count('1') == A:
        bins.append(b)

for rows in product(bins, repeat=H):
    for i in range(H):
        h = ''
        for r in rows:
            h += r[i]
        if h.count('0') != B and h.count('1') != B:
            break
    else:
        for r in rows:
            print(r)
        exit()
print('No')


Fixed submission:
H, W, A, B = map(int, input().split())

for i in range(H):
    if i < B:
        print('1'*A + '0'*(W-A))
    else:
        print('0'*A + '1'*(W-A))

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
H, W, A, B = map(int, input().split())

bins = []
for i in range(2**W):
    b = bin(i)[2:].zfill(W)
    if b.count('0') == A or b.count('1') == A:
        bins.append(b)

for rows in product(bins, repeat=H):
    for i in range(H):
        h = ''
        for r in rows:
            h += r[i]
        if h.count('0') != B and h.count('1') != B:
            break
    else:
        for r in rows:
            print(r)
        exit()
print('No')


Fixed submission:
H, W, A, B = map(int, input().split())

for i in range(H):
    if i < B:
        print('1'*A + '0'*(W-A))
    else:
        print('0'*A + '1'*(W-A))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
arr = list(map(int, input().split()))
for _ in range(m):
    _max = max(arr)
    i = arr.index(_max)
    arr[i] = _max // 2
print(sum(arr))

Fixed submission:
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)
for _ in range(m):
    _max = max(arr)
    i = arr.index(_max)
    arr[i] = _max // 2
print(sum(arr))

Fixed submission:
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)
for _ in range(m):
    arr[0] = arr[0] // 2
    arr = sorted(arr, reverse=True)
print(sum(arr))

Fixed submission:
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        part = s[i:j]
        if part in s[j:]:
            _max = max(_max, j-i)
        else:
            break
print(_max)

Fixed submission:
n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        if _max >= j-i:
            continue
        part = s[i:j]
        if part in s[j:]:
            _max = j-i
        else:
            break
print(_max)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
h = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        h += 1
print(min(h + 2 * k, n - 1))

Fixed submission:
print(int(input())**3)
Buggy python submission (verdict: Runtime Error):
n = int(input())
bs = list(map(int, input().split()))
arr = []
for i in range(n):
    if i == 0 or i == 1:
        arr.append(bs[0])
    else:
        arr.append(bs[i-1])
        if bs[i-1] < arr[i-1]:
            arr[i-1] = bs[i]
print(sum(arr))


Fixed submission:
n = int(input())
bs = list(map(int, input().split()))
arr = []
for i in range(n):
    if i == 0 or i == 1:
        arr.append(bs[0])
    else:
        arr.append(bs[i-1])
        if bs[i-1] < arr[i-1]:
            arr[i-1] = bs[i-1]
print(sum(arr))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(sum(range(n)))

Fixed submission:
n = int(input())
print(sum(range(n)))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from math import factorial
N = int(input())
d = defaultdict(int)
for i in range(N):
    s = ''.join(sorted(input()))
    d[s] += 1
t = 0
for c in d.values():
    if 1 < c:
        t += factorial(c) / 2
print(int(t))

Fixed submission:
from collections import defaultdict
from math import factorial
N = int(input())
d = defaultdict(int)
for i in range(N):
    s = ''.join(sorted(input()))
    d[s] += 1
t = 0
for c in d.values():
    if 1 < c:
        t += c * (c-1) // 2
print(t)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = []
c = 0
for i in range(N):
    s = sorted(input())
    c += a.count(s)
    a.append(s)
print(c)

Fixed submission:
from collections import defaultdict
from math import factorial
N = int(input())
d = defaultdict(int)
for i in range(N):
    s = ''.join(sorted(input()))
    d[s] += 1
t = 0
for c in d.values():
    if 1 < c:
        t += c * (c-1) // 2
print(t)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = []
c = 0
for i in range(N):
    s = sorted(input())
    c += a.count(s)
    a.append(s)
print(c)

Fixed submission:
from collections import defaultdict
from math import factorial
N = int(input())
d = defaultdict(int)
for i in range(N):
    s = ''.join(sorted(input()))
    d[s] += 1
t = 0
for c in d.values():
    if 1 < c:
        t += c * (c-1) // 2
print(t)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
from collections import deque
AB = deque(sorted([list(map(int, input().split())) for i in range(N)]))

from heapq import *
q = []
heapify(q)
ans = 0
remain_days = 1
while remain_days <= M:
    for a, b in list(AB):
        if a <= remain_days:
            heappush(q, -1 * AB.popleft()[1])
    if q:
        v = heappop(q)
        ans += -1 * v
    remain_days += 1
print(ans)

Fixed submission:
from heapq import *
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for _ in range(n)]
jobs.sort(reverse=True)
ans = 0
q = []
# 残り何日でのごとの仕事の候補をqに追加していく
for i in range(1, m+1):
    while jobs and jobs[-1][0] <= i:
        # -1かけてqに追加
        heappush(q, -jobs.pop(-1)[1])
    if q:
        #　残り何日でごとに、-1かかってるので一番高いお金をもらえる仕事がpopされる
        ans -= heappop(q)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
mod = 10**9+7
P = 13

dp = [[0 for _ in range(P)] for _ in range(N)]

# 1桁目だけ事前計算
if S[N-1] == '?':
    tmp = [0 for _ in range(P)]
    for i in range(10):
        tmp[i % P] = 1
    dp[0] = tmp
else:
    dp[0][int(S[N-1]) % P] = 1

for i in range(1, N):
    k = N-i-1
    if S[k] == '?':
        base = 10**i % P
        rems = [0 for _ in range(P)]
        for j in range(10):
            rems[base * j % P] += 1
        for m in range(P):
            for n in range(P):
                a = dp[i-1][m] * rems[n] % mod
                dp[i][(m+n) % P] = (dp[i][(m+n) % P] + a) % mod
    else:
        r = 10**i * int(S[k]) % P
        for j in range(P):
            dp[i][(j+r)%P] = max(dp[i][(j+r)%P], dp[i-1][j])

print(dp[-1][5])

Fixed submission:
S = input()
N = len(S)
mod = 10**9+7
P = 13
 
dp = [[0 for _ in range(P)] for _ in range(N)]
 
# 1桁目だけ事前計算
if S[N-1] == '?':
    tmp = [0 for _ in range(P)]
    for i in range(10):
        tmp[i % P] = 1
    dp[0] = tmp
else:
    dp[0][int(S[N-1]) % P] = 1
 
for i in range(1, N):
    k = N-i-1
    if S[k] == '?':
        base = pow(10, i, P)
        for j in range(10):
            r = base*j % P
            for m in range(P):
                dp[i][(m+r)%P] = (dp[i][(m+r)%P] + dp[i-1][m]) % mod
    else:
        r = pow(10, i, P) * int(S[k]) % P
        for j in range(P):
            dp[i][(j+r)%P] = max(dp[i][(j+r)%P], dp[i-1][j])
 
print(dp[-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
arr = [int(input()) for _ in range(N)]

for i in range(N):
    a = arr[:i] + arr[i+1:]
    print(max(a))

Fixed submission:
N = int(input())
arr = [int(input()) for _ in range(N)]
sarr = sorted(arr, reverse=True)

for i in range(N):
    a = arr[i]
    if a == sarr[0]:
        print(sarr[1])
    else:
        print(sarr[0])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
ans = []

from functools import lru_cache
@lru_cache(maxsize=None)
def rec(ind):
    if ind >= N:
        ind -= N
    return A[ind]*2

for i in range(N):
    t = 0
    for j in range(N//2):
        ind = i+1+j*2
        t += rec(ind)
    ans.append(total-t)
print(*ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
# 山1に降った量の半分をxと置くと、山2はA1-x、山3はA2-(A1-x)となり、翻って山1はA3-(A2-(A1-x))
# x = A3-A2+A1+x
# x = (A1+A3-A2) // 2
x = (sum(A[::2]) - sum(A[1::2])) // 2
ans = [x*2]
for i in range(N-1):
    a = A[i] - x
    ans.append(a*2)
    x = a
print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
ans = []
for i in range(N):
    t = 0
    for j in range(N//2):
        ind = i+1+j*2
        if ind >= N:
            ind -= N
        t += A[ind]*2
    ans.append(total-t)
print(*ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
# 山1に降った量の半分をxと置くと、山2はA1-x、山3はA2-(A1-x)となり、翻って山1はA3-(A2-(A1-x))
# x = A3-A2+A1+x
# x = (A1+A3-A2) // 2
x = (sum(A[::2]) - sum(A[1::2])) // 2
ans = [x*2]
for i in range(N-1):
    a = A[i] - x
    ans.append(a*2)
    x = a
print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
ans = []
for i in range(N):
    t = 0
    for j in range(N//2):
        ind = i+1+j*2
        if ind >= N:
            ind -= N
        t += A[ind]*2
    ans.append(total-t)
print(*ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
# 山1に降った量の半分をxと置くと、山2はA1-x、山3はA2-(A1-x)となり、翻って山1はA3-(A2-(A1-x))
# x = A3-A2+A1+x
# x = (A1+A3-A2) // 2
x = (sum(A[::2]) - sum(A[1::2])) // 2
ans = [x*2]
for i in range(N-1):
    a = A[i] - x
    ans.append(a*2)
    x = a
print(*ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // gcd(x, y)

lcmv = lcm(C, D)
bc = B // C
bd = B // D
bl = B // lcmv
ac = (A-1) // C
ad = (A-1) // D
al = (A-1) // lcmv
print(B - A + 1 - ((bc + bd - bl) - (ac + ad - al)))

Fixed submission:
from fractions import gcd
A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // gcd(x, y)

lcmv = lcm(C, D)
bc = B // C
bd = B // D
bl = B // lcmv
ac = (A-1) // C
ad = (A-1) // D
al = (A-1) // lcmv
print(B - A + 1 - ((bc + bd - bl) - (ac + ad - al)))
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
for b, c in BC:
    A.extend([c]*b)
_A = [-a for a in A]
heapq.heapify(_A)
ans = 0
for i in range(N):
    ans += -1 * heapq.heappop(_A)
print(ans)


Fixed submission:
from collections import defaultdict as dd
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]

cards = dd(int)
for a in A:
    cards[a] += 1
for b, c in BC:
    cards[c] += b

ans = 0
for k, v in sorted(cards.items(), key=lambda x: -x[0]):
    if N > v:
        ans += k*v
    else:
        ans += k*N
        break
    N -= v
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
for b, c in BC:
    A.extend([c]*b)
print(sum(sorted(A)[-N:]))

Fixed submission:
from collections import defaultdict as dd
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]

cards = dd(int)
for a in A:
    cards[a] += 1
for b, c in BC:
    cards[c] += b

ans = 0
for k, v in sorted(cards.items(), key=lambda x: -x[0]):
    if N > v:
        ans += k*v
    else:
        ans += k*N
        break
    N -= v
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
l = [list(input()) for _ in range(H)]

from collections import deque
q = deque()
for i, r in enumerate(l):
    for j, c in enumerate(r):
        if c == '#':
            l[i][j] = 0
            q.append((i, j))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if (0 <= y+dy < H) and (0 <= x+dx < W) and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

m = 0
for r in l:
    for c in r:
        if m < c:
            m = c
print(m)

Fixed submission:
H, W = map(int, input().split())
l = [list(input()) for _ in range(H)]

from collections import deque
q = deque()
for i, r in enumerate(l):
    for j, c in enumerate(r):
        if c == '#':
            l[i][j] = 0
            q.append((i, j))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if (0 <= y+dy < H) and (0 <= x+dx < W) and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

m = 0
for r in l:
    for c in r:
        if m < c:
            m = c
print(m)