Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02847 (python)

Fixed submission:
s = input()
youbi = ['SUN','MON','TUE','WED','THU','FRI','SAT']
index = youbi.index(s)

day = 7 - index
if day == 0:
  print('7')
else:
  print(day)

Buggy submission (verdict: Runtime Error):
a,b,x = map(int, input().split())

left = 0
right = 10**9 + 1

while (right - left > 1):
  mid = (left + right ) // 2
  if (a*mid+b*len(str(mid))) > x:
    right = mid
  else:
    left = mid
print(left)
Problem p02881 (python)

Fixed submission:
n=int(input())

div = n
result = 10**12

for i in range(1,1000001):
  if n % i == 0:
    div = n // i
    result = min(result, i+div)

print(int(result-2))

Buggy submission (verdict: Runtime Error):
n=int(input())

div1 = 1
div2 = n
result = 10**12
if n == 1:
  print('0')
  exit()

for i in range(1,int(-(-n**0.5//1))+1):
  if n % i == 0:
    div1 *= i
    div2 /= i
    div_sum = div1 + div2
    result = min(result, div_sum)
print(int(result-2))

Buggy submission (verdict: Runtime Error):
n=int(input())

div1 = 1
div2 = n
result = 10**12
if n == 1:
  print('0')
  exit()

for i in range(1,int(-(-n**0.5//1))+1):
  if n % i == 0:
    div1 *= i
    div2 /= i
    div_sum = div1 + div2
    result = min(result, div_sum)
print(int(div_sum-2))

Buggy submission (verdict: Runtime Error):
n=int(input())

div1 = 1
div2 = n
result = 10*10
if n == 1:
  print('0')
  exit()

for i in range(1,int(-(-n**0.5//1))+1):
  if n % i == 0:
    div1 *= i
    div2 /= i
    div_sum = div1 + div2
    result = min(result, div_sum)
print(int(div_sum-2))

Buggy submission (verdict: Runtime Error):
n=int(input())

div1 = 1
div2 = n
result = 10*10
for i in range(1,int(n**0.5+1)):
  if n % i == 0:
    div1 *= i
    div2 /= i
    div_sum = div1 + div2
    result = min(result, div_sum)
print(int(div_sum-2))
Problem p03327 (python)

Fixed submission:
a=int(input())
if a<1000:
	print('ABC')
else:
	print('ABD')

Buggy submission (verdict: Runtime Error):
a=input()
if a<1000:
	print('ABC')
else:
	print('ABD')

Buggy submission (verdict: Runtime Error):
a=input()
if a<1000:
	print('ABC')
else:
	print('ABD')
Problem p02629 (python)

Fixed submission:
def main():
    N = int(input())
    result = []
    
    while N > 0:
        N -= 1
        mod = N % 26
        result.append(chr(mod + ord('a')))
        N //= 26

    result_str = ""
    for i in range(len(result)-1, -1, -1):
        result_str += result[i]

    print(result_str)

main()

Buggy submission (verdict: Runtime Error):
N = int(input())
N -= 1

lower = 'abcdefghijklmnopqrstuvwxyz'
lower_map = {}
for i, c in enumerate(lower):
    lower_map[i] = c

num_of_digits = 1
for i in range(1, 12):
    if 26 ** (i-1) <= N+1 < 26 ** i:
        num_of_digits = i
        break

# TODO: デバグ後は文字列の連結にする
# result = []
result = ""

for i in range(num_of_digits, 0, -1):
    digit = i - 1
    for j in range(0, 26):
        if (26 ** digit) * j <= N < (26 ** digit) * (j+1):
            if digit == 0:
                result += lower_map[j]
            else:
                result += lower_map[j-1]
            N -= (26 ** digit) * j
            break

print(result)
Problem p02580 (python)

Fixed submission:
import bisect

H, W, M = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(M)]
hw.sort()

rows, columns = [0]*H, [0]*W
for h, w in hw:
    rows[h-1] += 1
    columns[w-1] += 1
max_r, max_c = max(rows), max(columns)

argmax_r, argmax_c = [], []
for i in range(H):
    if max_r == rows[i]:
        argmax_r.append(i)

for i in range(W):
    if max_c == columns[i]:
        argmax_c.append(i)

for r in argmax_r:
    for c in argmax_c:
        idx = bisect.bisect_left(hw, [r+1, c+1])
        if idx == M or hw[idx] != [r+1,c+1]:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)

Buggy submission (verdict: Runtime Error):
import bisect

H, W, M = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(M)]
hw.sort()

rows, columns = [0]*H, [0]*W
for h, w in hw:
    rows[h-1] += 1
    columns[w-1] += 1
max_r, max_c = max(rows), max(columns)

argmax_r, argmax_c = [], []
for i in range(H):
    if max_r == rows[i]:
        argmax_r.append(i)

for i in range(W):
    if max_c == columns[i]:
        argmax_c.append(i)

for r in argmax_r:
    for c in argmax_c:
        idx = bisect.bisect_left(hw, [r+1, c+1])
        if hw[idx] != [r+1,c+1]:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)
Problem p02862 (python)

Fixed submission:
class Combination:
    def __init__(self, mod, max_n):
        self.MOD = mod
        self.MAX_N = max_n

        self.f = self.factorial(self.MAX_N)
        self.f_inv = [self.inv(x) for x in self.f]

    def inv(self,x):
        return pow(x, self.MOD-2, self.MOD)
    
    def factorial(self, n):
        res = [1]
        for i in range(1,n+1):
            res.append(res[-1] * i % self.MOD)
        return res
    
    def comb(self, n, r):
        return (self.f[n] * self.f_inv[r] % self.MOD) * self.f_inv[n-r] % self.MOD


X, Y = map(int,input().split())
k, l = (2*Y-X)//3, (2*X-Y)//3

if (X + Y) % 3 != 0 or k < 0 or l < 0:
    print(0)
    exit()

CB = Combination(10**9+7, k+l)
print(CB.comb(k+l,k))

Buggy submission (verdict: Runtime Error):
class Combination:
    def __init__(self, mod, max_n):
        self.MOD = mod
        self.MAX_N = max_n

        self.f = self.factorial(self.MAX_N)
        self.f_inv = [self.inv(x) for x in self.f]

    def inv(self,x):
        return pow(x, self.MOD-2, self.MOD)
    
    def factorial(self, n):
        res = [1]
        for i in range(1,n+1):
            res.append(res[-1] * i % self.MOD)
        return res
    
    def comb(self, n, r):
        return (self.f[n] * self.f_inv[r] % self.MOD) * self.f_inv[n-r] % self.MOD


X, Y = map(int,input().split())

if (X + Y) % 3 != 0:
    print(0)
    exit()

k, l = (2*Y-X)//3, (2*X-Y)//3
CB = Combination(10**9+7, k+l)
print(CB.comb(k+l,k))
Problem p03045 (python)

Fixed submission:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))
N, M = map(int,input().split())

UF = UnionFind(N)

for _ in range(M):
    X, Y, Z = map(int,input().split())
    X, Y = X-1, Y-1
    UF.unite(X,Y)

print(UF.components)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y: self.p[x] = y
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

UF = UnionFind(N)

for _ in range(M):
    X, Y, Z = map(int,input().split())
    X, Y = X-1, Y-1
    UF.unite(X,Y)

S = set()
for i in range(N):
    S.add(UF.root(i))

print(len(S))
Problem p02577 (python)

Fixed submission:
N=int(input())
if N%9 == 0:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
N=input()
if N%9 == 0:
    print("Yes")
else:
    print("No")
Problem p02629 (python)

Fixed submission:
import string

N = int(input())
al = string.ascii_lowercase

# if (N >= 1 and N <= 26):
#     print(al[N - 1])
#     exit()
# elif (N >= 27 and N <= 702):
#     n = N // 26
#     amari = N % 26
#     if (amari == 0 and n != 27):
#         print(al[n - 1] + al[25])
#         exit()
#     elif (amari == 0 and n == 27):
#         print(al[25] + al[25])
#         exit()
#     else:
#         print(al[n - 1] + al[amari - 1])
#         exit()
# elif (N >= 703):
s = ''
num = 26
while N > 26:
    amari = N % num
    N //= 26
    if (amari == 0):
        N -= 1
    if (amari == 0):
        s += al[25]
    else:
        s += al[amari - 1]
if (N == 0):
    s += al[25]
else:
    s += al[N - 1]
print(s[::-1])

Buggy submission (verdict: Runtime Error):
import string

N = int(input())
al = string.ascii_lowercase

if (N >= 1 and N <= 26):
    print(al[N - 1])
    exit()
elif (N >= 27 and N <= 702):
    n = N // 26
    amari = N % 26
    if (amari == 0 and n != 27):
        print(al[n - 1] + al[25])
        exit()
    elif (amari == 0 and n == 27):
        print(al[25] + al[25])
        exit()
    else:
        print(al[n - 1] + al[amari - 1])
elif (N >= 703):
    s = ''
    num = 26
    while N > 26:
        amari = N % num
        N //= 26
        if (amari == 0):
            N -= 1
        if (amari == 0):
            s += al[25]
        else:
            s += al[amari - 1]
if (N == 0):
    s += al[25]
else:
    s += al[N - 1]
print(s[::-1])
Problem p02723 (python)

Fixed submission:
s = input()

if len(s) == 6 and s[2]==s[3] and s[4]== s[5]:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
s = input()

if len(s) == 6 & s[2]==s[3] & s[4]== s[5] {
    return print("Yes")
}else {
    return print("No")
}
Problem p02729 (python)

Fixed submission:
import math
n, m = map(int, input().split())

# 偶数足す偶数
# 奇数たす奇数
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if (n==0 and m>=2):
    ans = ans + combinations_count(m, 2)

elif (n>=2 and m== 0):
    ans = ans + combinations_count(n, 2)
else:
    if (n!=1):
        ans = ans+ combinations_count(n, 2)
    
    if (m != 1):
        ans = ans + combinations_count(m, 2)



print(ans)

Buggy submission (verdict: Runtime Error):
import math
n, m = map(int, input().split())

# 偶数足す偶数
# 奇数たす奇数
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if (n!=1):
    ans = ans+ combinations_count(n, 2)

if (m != 1):
    ans = ans + combinations_count(m, 2)
    
print(ans)
Problem p02912 (python)

Fixed submission:
import math
n,m = map(int,input().split())

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)
 
if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()
 
while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Buggy submission (verdict: Runtime Error):
import math
n, m = map(int, input().split())

list1 = list(map(int,input().split()))
list1.sort()
list1.reverse()

i=0
s = math.floor(list1[0]/2)

if n==1:
    print(math.floor(list[1]/(2**m)))
    # 処理終了
    exit() 

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m==0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))
Problem p03745 (python)

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

if n == 1:
    print(1)
    exit()

d = [0] * (n - 1)
if (L[0] > L[1]):
    d[0] = -1
elif (L[0] < L[1]):
    d[0] = 1

for i in range(n):
    if (i == 0):
        continue
    elif (i == n - 1):
        break
    else:
        if (L[i] < L[i + 1]):
            d[i] = 1
        elif (L[i] > L[i + 1]):
            d[i] = -1

prev = 0
count = 0
for i in range(len(d)):
    if (i == 0):
        prev = d[i]
        continue
    if (prev == 1):
        if (d[i] == 1):
            continue
        elif (d[i] == 0):
            continue
        else:
            count += 1
            prev = 0
    elif (prev == -1):
        if (d[i] == -1):
            continue
        elif (d[i] == 0):
            continue
        else:
            count += 1
            prev = 0
    elif (prev == 0):
        if (d[i] == 1):
            prev = 1
        elif (d[i] == -1):
            prev = -1

print(count + 1)

Buggy submission (verdict: Runtime Error):
n = int(input())
L = list(map(int, input().split()))

cnt = 0
larger = 1
smaller = -1

d = [0] * (n - 1)
if (L[0] > L[1]):
    d[0] = -1
elif (L[0] < L[1]):
    d[0] = 1

cnt = 1
for i in range(n):
    if (i == 0):
        continue
    elif (i == n - 1):
        break
    else:
        if (L[i] < L[i + 1] and d[i - 1] >= 0):
            d[i] = 1
        elif (L[i] > L[i + 1] and d[i - 1] <= 0):
            d[i] = -1
        elif (L[i] < L[i + 1] and d[i - 1] < 0):
            cnt += 1
        elif (L[i] > L[i + 1] and d[i - 1] > 0):
            cnt += 1
        elif (L[i] == L[i + 1]):
            continue

print(cnt)
Problem p03804 (python)

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


for i in range(N - M + 1):
    for j in range(N - M + 1):
        check = True
        count = 0
        for k in range(M):
            if (A[i + k][j: j + M] == B[k]):
                # print(A[i + k][j:j + M], B[k])
                count += 1
                continue
            else:
                check = False
                break

        if (check and count == M):
            print('Yes')
            exit()

print('No')

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

B = []
for _ in range(M):
    b = input()
    B.append(b)

idx = [0, 0]
while True:
    if idx[0] == N - 1 and idx[1] == N:
        break
    if A[idx[0]][idx[1]] == B[0][0]:
        check = False
        for i in range(M):
            for j in range(M):
                if 0 <= idx[0] + i < N and 0 <= idx[1] + j < N:
                    if A[idx[0] + i][idx[1] + j] != B[i][j]:
                        check = True
                        break
                else:
                    check = True
                    break
            if check:
                break

        if not check:
            print('Yes')
            exit()
    if idx[1] < N - 1:
        idx[1] += 1
        continue
    else:
        idx[0] += 1
        idx[1] = 1
        continue

print('No')
Problem p03806 (python)

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

sum_a = 0
sum_b = 0
A = []
B = []
C = []
for _ in range(N):
    a, b, c = map(int, input().split())
    sum_a += a
    sum_b += b
    A.append(a)
    B.append(b)
    C.append(c)

inf = 10 ** 9 + 7
# 3次元dpを考える
dp = [[[inf] * (sum_b + 1) for _ in range(sum_a + 1)] for _ in range(N + 1)]

dp[0][0][0] = 0
for i in range(N):
    for sa in range(sum_a):
        for sb in range(sum_b):
            if sa - A[i] >= 0 and sb - B[i] >= 0:
                dp[i + 1][sa][sb] = min(dp[i][sa - A[i]]
                                        [sb - B[i]] + C[i], dp[i][sa][sb])
            else:
                dp[i + 1][sa][sb] = min(dp[i][sa][sb], dp[i + 1][sa][sb])

ans = inf
for i in range(1, sum_a + 1):
    for j in range(1, sum_b + 1):
        if Ma * j == Mb * i:
            ans = min(ans, dp[N][i][j])

print(ans if ans != inf else -1)

Buggy submission (verdict: Runtime Error):
import math
N, Ma, Mb = map(int, input().split())
cost = [[0] * 10 for _ in range(10)]
for _ in range(N):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    cost[a][b] = c

min_cost = 10 ** 9 + 7
for k in range(N):
    for i in range(N):
        for j in range(N):
            g = math.gcd(i + 1 + k + 1, k + 1 + j + 1)
            if (i + 1 + k + 1) // g == Ma and (k + 1 + j + \
                1) // g == Mb and cost[i][k] + cost[k][j] != 0:
                # print(cost[i][k] + cost[k][j])
                min_cost = min(min_cost, cost[i][k] + cost[k][j])


if min_cost == 10 ** 9 + 7:
    print(-1)
else:
    print(min_cost)
Problem p02578 (python)

Fixed submission:
n = int(input())
arr = list(map(int, input().split()))
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
arr = map(int, input().split())
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)
Problem p02676 (python)

Fixed submission:
k = int(input())
a = str(input())
 
if len(a) <= k:
	print(a)
else:
	print(a[:k] + "...")

Buggy submission (verdict: Runtime Error):
k = int(input())
a = str(input())

if len(a) <= k:
	print(a)
else
	print(a[:k] + "...")
Problem p02723 (python)

Fixed submission:
s = input()
if(s[2]!=s[3] or s[4]!=s[5]):
  print("No")
  exit()
else:
  print("Yes")

Buggy submission (verdict: Runtime Error):
s = input()
if(s[2]!=s[3] || s[4]!=s[5]):
  print("No")
  exit()
else:
  print("Yes")
Problem p02598 (python)

Fixed submission:
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()
if K == 0:
    print(A[-1])
else:
    ans = 10**9
    l = 0
    r = 10**9
    while l < r:
        # t以下の長さにするのに必要な切る回数
        t = (l + r) // 2
        if t == 0:
            break
        # print(t)
        n = K
        for a in A:
            n -= (a - 1) // t
            if n < 0:
                break
        if n >= 0:
            ans = min(ans, t)
        if n >= 0:
            r = t
        else:
            l = t + 1

    print(ans)

Buggy submission (verdict: Runtime Error):
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()
if K == 0:
    print(A[-1])
else:
    ans = 10**9
    l = 0
    r = 10**9
    while l < r:
        # t以下の長さにするのに必要な切る回数
        t = (l + r) // 2
        # print(t)
        n = K
        for a in A:
            n -= (a - 1) // t
            if n < 0:
                break
        if n >= 0:
            ans = min(ans, t)
        if n >= 0:
            r = t
        else:
            l = t + 1

    print(ans)
Problem p02779 (python)

Fixed submission:
import sys
from pprint import pprint

def solve(n, a):
    exists = set()
    for a_i in a:
        if a_i in exists:
            return "NO"
        exists.add(a_i)
    return "YES"

if __name__ == '__main__':
    n = sys.stdin.readline().strip()
    a = list(map(int,sys.stdin.readline().strip().split(" ")))
    
    print(solve(n, a))

Buggy submission (verdict: Runtime Error):
import sys
from pprint import pprint

def solve(n, k, p):
    E = [(1.0 + p_i)/2 for p_i in p]
    # pprint(E)
    
    ans = 0
    for i in range(n - k + 1):
        # print(i+3)
        ans = max(ans, sum([E[i+j] for j in range(k)]))
        # print(i, sum([E[i+j] for j in range(k)]))
    print(ans)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    p = list(map(int, sys.stdin.readline().strip().split(" ")))
    solve(n, k, p)
Problem p02831 (python)

Fixed submission:
import sys
from pprint import pprint
import fractions

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

def solve(a, b):
    print(lcm(a, b))

if __name__ == '__main__':
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    solve(a, b)

Buggy submission (verdict: Runtime Error):
import sys
import math

def solve(a, b):
    print(math.gcd(a, b))

if __name__ == '__main__':
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    solve(a, b)
Problem p03013 (python)

Fixed submission:
import sys

N, M = map(int, sys.stdin.readline().strip().split())
A = set()
for _ in range(M):
    A.add(int(sys.stdin.readline()))

# i段目の階段への到達方法の数
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if 1 in A else 1

for i in range(2, N+1):
    if i in A:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= 1000000007

print(dp[N])

Buggy submission (verdict: Runtime Error):
import sys
from pprint import pprint

def solve(n, m, a):
    sum = 1
    a_pre = 0
    for a_i in a:
        if a_pre != 0 and a_pre == a_i:
            return 0
        if a_i == 1:
            a_pre = a_i + 1
            continue
        pattern = (a_i - 1 - a_pre - 1)
        #print pattern
        sum *= 2**pattern
        a_pre = a_i + 1
    pattern = (n - a_pre - 1)
    #print pattern
    sum *= 2**pattern

    return sum % 1000000007


if __name__ == '__main__':

    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = []
    for i in range(m):
        a.append(int(sys.stdin.readline().strip()))
    print solve(n, m, a)
Problem p03038 (python)

Fixed submission:
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

Buggy submission (verdict: Runtime Error):
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

Buggy submission (verdict: Runtime Error):
import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count+1):
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)