Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

# 約数の全列挙
def 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(reverse=True)  # ソート
    return divisors

def sol():
    A, B = map(int, input().split())

    divA = divisors(A)
    comDiv = []

    for a in divA:
        if B % a == 0:
            comDiv.append(a)

    comDiv.sort()
    isIndep = [True] * len(comDiv)
    maxDiv = comDiv[-1]
    divToIndex = {d : i for i, d in enumerate(comDiv)}
    ans = 1

    for i, div in enumerate(comDiv[1:], start=1):
        if isIndep[i]:
            ans += 1
            mul = 2
            while div * mul <= maxDiv:
                if div * mul in divToIndex:
                    isIndep[divToIndex[div * mul]] = False
                mul += 1

    print(ans)

sol()

Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

def sol():
    A, B = map(int, input().split())

    primeA = primeCount(A)
    primeB = primeCount(B)

    ans = 1
    for a in primeA.keys():
        if a in primeB:
            ans += 1

    print(ans)

sol()
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
K = []

for _ in range(M):
    a, _ = map(int, input().split())
    k = 0
    for i in map(int, input().split()):
        k |= (1 << (i - 1))
    K.append((a, k))

dp = [10**18] * (1 << N)
dp[0] = 0
for state in range(1 << N):
    for a, k in K:
        dp[state | k] = min(dp[state | k], dp[state] + a)

ans = dp[(1 << N) - 1]
print(ans if ans < 10**18 else -1)


Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M = map(int, input().split())
    keys = []

    for _ in range(M):
        a, _ = map(int ,input().split())
        C = list(map(int, input().split()))
        cMask = 0
        for c in C:
            cMask |= (1 << (c - 1))
        keys.append((a, cMask))

    dp = [[INF] * (1 << N) for _ in range(M + 1)]  # dp[i][mask] = i番目の鍵までで，状態mask
    dp[0][0] = 0

    for i, (cost, cMask) in enumerate(keys, start=1):
        for mask in range(1 << N):
            dp[i][mask] = min(dp[i][mask], dp[i - 1][mask])
            dp[i][mask | cMask] = min(dp[i][mask | cMask], dp[i - 1][mask] + cost)

    ans = dp[M][(1 << N) - 1]
    if ans == INF:
        print(-1)
    else:
        print(ans)

sol()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N, M = map(int, input().split())

edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                if now == start:
                    break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    if L[-1] != L[0]:
        continue

    L.pop()
    print(len(L))
    ans = [v + 1 for v in L]
    print(*ans, sep='\n')
    exit()

print(-1)

Fixed submission:
from collections import deque

N, M = map(int, input().split())

edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    print(0)
    print()
    exit()

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class SegmentTree:
    def __init__(self, size):
        self._size = (1 << size.bit_length())
        self._data = [INF] * (self._size * 2)

    def update(self, index, value):
        index += self._size - 1
        self._data[index] = value
        while index > 0:
            index = (index - 1) // 2
            self._data[index] = min(self._data[index * 2 + 1], self._data[index * 2 + 2])

    def __query(self, qLeft, qRight, node, left, right):
        if right <= qLeft or qRight <= left:
            return INF
        if qLeft <= left and right <= qRight:
            return self._data[node]

        leftVal = self.__query(qLeft, qRight, node * 2 + 1, left, (left + right) // 2)
        rightVal = self.__query(qLeft, qRight, node * 2 + 2, (left + right) // 2, right)
        return min(leftVal, rightVal)

    def query(self, left, right):
        return self.__query(left, right, 0, 0, self._size)

N, K = map(int, input().split())
P = list(map(int, input().split()))

minTree = SegmentTree(N)
maxTree = SegmentTree(N)

for i, p in enumerate(P):
    minTree.update(i, p)
    maxTree.update(i, -p)

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    if minTree.query(left, right) == P[left] and maxTree.query(left + 1, right + 1) == -P[right]:
        continue
    else:
        if seq >= K:
            if hasSame:
                continue
            else:
                hasSame = True
        ans += 1

print(ans)

Fixed submission:
from collections import deque

N, K = map(int, input().split())
P = list(map(int, input().split()))

maxQ = deque([])
minQ = deque([])

for i in range(K):
    while maxQ:
        if P[maxQ[-1]] <= P[i]:
            maxQ.pop()
        else:
            break
    maxQ.append(i)
    if maxQ[0] == i - K:
        maxQ.popleft()

    while minQ:
        if P[minQ[-1]] >= P[i]:
            minQ.pop()
        else:
            break
    minQ.append(i)
    if minQ[0] == i - K:
        minQ.popleft()

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    while maxQ:
        if P[maxQ[-1]] <= P[right]:
            maxQ.pop()
        else:
            break
    maxQ.append(right)
    if maxQ[0] == right - K:
        maxQ.popleft()

    if left == minQ[0] and right == maxQ[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    while minQ:
        if P[minQ[-1]] >= P[right]:
            minQ.pop()
        else:
            break
    minQ.append(right)
    if minQ[0] == right - K:
        minQ.popleft()

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

sList = [0 for _ in range(N)]

for i in range(N) :
    s = list(input())
    s.sort()
    sList[i] = s

confilm = [False for _ in range(N)]

ans = 0
for i in range(N) :
    if confilm[i] :
        continue
    confilm[i] = True
    count = 1
    for j in range(i + 1, N) :
        if sList[i] == sList[j] :
            confilm[j] = True
            count += 1
    ans += count * (count - 1) // 2

print(ans)

Fixed submission:
N = int(input())

sList = {}

for i in range(N) :
    s = list(input())
    s.sort()
    s = ''.join(s)

    if s in sList :
        sList[s] += 1
    else :
        sList[s] = 1

ans = 0
for _, num in sList.items() :
    ans += num * (num - 1) // 2

print(ans)

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

sList = [0 for _ in range(N)]

for i in range(N) :
    s = list(input())
    s.sort()
    sList[i] = s

confilm = [False for _ in range(N)]

ans = 0
for i in range(N) :
    if confilm[i] :
        continue
    confilm[i] = True
    count = 1
    for j in range(i + 1, N) :
        if sList[i] == sList[j] :
            confilm[j] = True
            count += 1
    ans += count * (count - 1) // 2

print(ans)

Fixed submission:
N = int(input())

sList = {}

for i in range(N) :
    s = list(input())
    s.sort()
    s = ''.join(s)

    if s in sList :
        sList[s] += 1
    else :
        sList[s] = 1

ans = 0
for _, num in sList.items() :
    ans += num * (num - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

# 約数の全列挙
def divisors(n):
    for i in range(int(n**0.5)+1, 0, -1):
        if n % i == 0:
            return i
    return 1

start = divisors(N)

print('0 0 0 {} {} 0'.format(start, N // start))

Fixed submission:
S = int(input())
MOD = 10**9

y2 = -(-S // 10**9)
x2 = -(S - y2 * (10**9))

print('0 0 {} 1 {} {}'.format(MOD, x2, y2))

Buggy python submission (verdict: Time Limit Exceeded):
import math

N = int(input())
sq = int(math.sqrt(N)) + 1
maxRange = 10**9

start = 1
for i in range(1, N) :
    if N // i < maxRange :
        start = i
        break

for i in range(start, sq) :
    if N % i == 0 :
        start = i
        break

print('0 0 0 {} {} 0'.format(start, N // start))

Fixed submission:
S = int(input())
MOD = 10**9

y2 = -(-S // 10**9)
x2 = -(S - y2 * (10**9))

print('0 0 {} 1 {} {}'.format(MOD, x2, y2))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
for _ in range(N) :
    a = int(input())
    A.append(a)

for i in range(N) :
    sub = A[:i] + A[i+1:]
    print(max(sub))

Fixed submission:
N = int(input())
A = []

for i in range(N) :
    a = int(input())
    A.append((a, i))

A.sort(key=lambda A : A[0], reverse=True)

for i in range(N) :
    if i == A[0][1] :
        print(A[1][0])
    else :
        print(A[0][0])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

ball = [0] * N

for i in range(N-1, -1, -1) :
    for j in range(1, N) :
        if i * j >= N :
            break
        bit = (bit + ball[i * j]) % 2
    ball[i] = bit % 2

print(*ball)

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

ball = [0] * N
ans = []

for i in range(1, N+1) :
    ballCount = sum(ball[N-i::N-i+1])
    if ballCount % 2 == A[N-i] :
        pass
    else :
        ball[N - i] = 1
        ans.append(N - i + 1)
print(len(ans))
print(*ans)

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

ball = [0] * N

for i in range(N-1, -1, -1) :
    bit = A[i]
    for j in range(i + 1, N) :
        bit = (ball + ball[i]) % 2
    ball[i] = bit % 2

print(*ball)

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

ball = [0] * N
ans = []

for i in range(1, N+1) :
    ballCount = sum(ball[N-i::N-i+1])
    if ballCount % 2 == A[N-i] :
        pass
    else :
        ball[N - i] = 1
        ans.append(N - i + 1)
print(len(ans))
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
L , R = map(int,input().split())

ans = float('inf')

for i in range(L, R+1) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

print(ans)

Fixed submission:
L , R = map(int,input().split())

ans = float('inf')

for i in range(L, min(R+1,L+2020)) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
L , R = map(int,input().split())

ans = float('inf')

for i in range(L, R+1) :
    for j in range(i+1,R+1) :
        ans = min(ans, (i*j) % 2019)

print(ans)

Fixed submission:
L , R = map(int,input().split())

ans = float('inf')

for i in range(L, min(R+1,L+2020)) :
    for j in range(i+1,min(R+1,i+2020)) :
        ans = min(ans, (i*j) % 2019)

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

out = [0] * N

for i in range(N) :
    ans = A[i]
    sig = i % 2

    # 前半
    for j in range(0,i) :
        ans += (-1)**(j+sig) * A[j]

    # 後半
    for j in range(i+1,N) :
        ans += (-1)**(j+sig+1) * A[j]
    out[i] = ans

print('{} '.format(out[-1]), end='')
out.pop()

for o in out :
    print('{} '.format(o), end='')

print('')

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

ss = 0
for i in range(N) :
    ss += (-1)**i * A[i]

ans = []

for i in range(N) :
    ss = -ss + 2*A[i]
    ans.append(ss)

print('{} '.format(ans[-1]), end='')
ans.pop()

for a in ans :
    print('{} '.format(a), end='')
print('')
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
A = [input() for _ in range(H)]

U = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            U[h][w] = 0
            L[h][w] = 0
        else:
            U[h][w] = 1 + (U[h - 1][w] if h > 0 else 0)
            L[h][w] = 1 + (L[h][w - 1] if w > 0 else 0)

        y = H - h - 1
        x = W - w - 1
        if A[y][x] == '#':
            D[y][x] = 0
            R[y][x] = 0
        else:
            D[y][x] = 1 + (D[y + 1][x] if y < H - 1 else 0)
            R[y][x] = 1 + (R[y][x + 1] if x < W - 1 else 0)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '.':
            ans = max(ans, U[h][w] + D[h][w] + L[h][w] + R[h][w] - 3)
print(ans)


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

s = [0] * H

for i in range(H) :
    s[i] = list(input())

# 端をゼロパディング
L = [[0 for _ in range(W+2)] for _ in range(H+2)]
R = [[0 for _ in range(W+2)] for _ in range(H+2)]
U = [[0 for _ in range(W+2)] for _ in range(H+2)]
D = [[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(1,H+1) :
    for j in range(1,W+1) :
        # 左上から
        if s[i-1][j-1] == '#' :
            L[i][j] = 0
            U[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1
        # 右下から
        if s[-i][-j] == '#' :
            R[-i-1][-j-1] = 0
            D[-i-1][-j-1] = 0
        else :
            R[-i-1][-j-1] = R[-i-1][-j] + 1
            D[-i-1][-j-1] = D[-i][-j-1] + 1

ans = 0

for i in range(1,H+1) :
    for j in range(1,W+1) :
        point = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        if ans < point :
            ans = point

print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()

ans = 0
i = 0

while i < len(s) :
    if s[i] == 'A' :
        if s[i+1] == 'B' and s[i+2] == 'C' : # 置換可能
            j = 1
            for j in range(1,i+1) :
                if not s[i-j] == 'A' : # 後方置換
                    break
            k = 0
            for k in range(0,len(s)) :
                ans += j - 1 + k
                if not s[i+k] == 'A' :
                    break
            i += k + 3
    i += 1

print(ans + 1)

Fixed submission:
S = input()
S = S.replace('BC', 'D').replace('B', ' ').replace('C', ' ').split()

ans = 0
for s in S:
    leftA = 0
    for i, t in enumerate(s[:: -1]):
        if t == 'A':
            ans += max(0, i - leftA)
            leftA += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

C = Counter(map(int, input().split()))

def dfs(now, pr, prev):
    ret = 0
    for to in edges:
        if to == pr:
            continue
        for c, n in C.items():
            if n == 0:
                continue
            C[c] -= 1
            ret = max(ret, dfs(to, now, c) + min(prev, c))
            C[c] += 1
    return ret

print(dfs(0, -1, 0))


Fixed submission:
from collections import deque

N = int(input())

edges = [[] for _ in range(N)]
edgeList = []
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)
    edgeList.append((fr, to))

C = list(map(int, input().split()))
C.sort()

M = sum(C) - C[-1]

values = [-1] * N
que = deque([0])

while que:
    now = que.popleft()
    values[now] = C.pop()
    for to in edges[now]:
        if values[to] == -1:
            que.append(to)

print(M)
print(*values)
Buggy python submission (verdict: Runtime Error):
N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0]).sort()

        index = 0

        for k in range(K-i-j):
            if (merge[0] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)

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

piece = 0
pie = 0

piece = A * 3 + P

print(int(piece / 2))
Buggy python submission (verdict: Time Limit Exceeded):
N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0
actList = [0]*K

for i in range(4**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 4)
        act = int(act / 4)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)



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

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)

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

maxValue = 0
actList = [0]*K

for i in range(5**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 5)
        act = int(act / 5)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)



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

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)
Buggy python submission (verdict: Runtime Error):
N , M = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(len(change)) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))

Fixed submission:
N , M = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(min(N,len(change))) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))

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

A = list(map(int,input().split()))

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = 0

for c in conv :
    if c[1] < A[0] : # 変換後のほうが小さい
        break

    for k in range(c[0]) :
        if A[k] >= c[1] :
            break

        A[k] = c[1]
        change += 1

    if change >= N :
        break

    A.sort()



print(int(sum(A)))

Fixed submission:
N , M = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(min(N,len(change))) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))

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

A = list(map(int,input().split()))

A.sort()

for i in range(M) :
    B , C = map(int,input().split())

    for j in range(B) :
        if A[j] < C :
            A[j] = C
        else :
            break

    A.sort()

print(int(sum(A)))

Fixed submission:
N , M = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(min(N,len(change))) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))