Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)


Fixed submission:
from sys import exit
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
if len(S) == 1:
    print(sum(A))
    for _ in range(n - 1):
        print(0)
    exit()
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)
Buggy python submission (verdict: Runtime Error):
s = input()
print(s.rfond("Z") - s.find("A") + 1)

Fixed submission:
s = input()
print(s.rfind("Z") - s.find("A") + 1)
Buggy python submission (verdict: Runtime Error):
x = input()
y = x % 11
if y > 0:
    cnt = 1
    if y > 6:
        cnt += 1
else:
    cnt = 0
    
print(x // 11 + cnt)


Fixed submission:
x = int(input())
y = x % 11
if y > 0:
    cnt = 1
    if y > 6:
        cnt += 1
else:
    cnt = 0
    
print((x // 11) * 2 + cnt)
Buggy python submission (verdict: Runtime Error):
n = int(input())
graph = [[] for _ in range(n)]
for i in range(1, n):
    graph[int(input()) - 1].append(i)


def dfs(x):
    arr = [dfs(y) for y in graph[x]]
    if not (arr):
        return 0
    arr.sort(reverse=True)
    return max(i + a for i, a in enumerate(arr, 1))


print(dfs(0))


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
graph = [[] for _ in range(n)]
for i in range(1, n):
    graph[int(input()) - 1].append(i)


def dfs(x):
    arr = [dfs(y) for y in graph[x]]
    if not (arr):
        return 0
    arr.sort(reverse=True)
    return max(i + a for i, a in enumerate(arr, 1))

print(dfs(0))
Buggy python submission (verdict: Runtime Error):
K, S = map(int, input().split())
count = 0
for x in range(K + 1):
  for y in range(K + 1):
    if S - x - y <= K:
      conut += 1
print(count)

Fixed submission:
K, S = map(int, input().split())
count = 0
for x in range(K + 1):
  for y in range(K + 1):
    if 0 <= S - x - y <= K:
      count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
x, y = map(int, input().split())
ans = 10 ** 9 + 3
if y >= x:
    ans = min(ans, abs(y - x))
if - y >= x:
    ans = min(ans, abs(-y - x) + 1)
if y >= -x:
    ans = min(ans, abs(y + x) + 1)
if - y >= -x:
    ans(min(ans, abs(-y + x) + 2))
print(ans)

Fixed submission:
x, y = map(int, input().split())
if abs(y) > abs(x):
    if (x >= 0 and y > 0):
        print(abs(y - x))
    elif x * y <= 0:
        print(abs(y) - abs(x) + 1)
    else:
        print(abs(y) - abs(x) + 2)
else:
    if x > 0 and y > 0:
        print(x - y + 2)
    elif x * y < 0 or (y == 0 and x > 0):
        print(abs(x) - abs(y) + 1)
    else:
        print(abs(x - y))
Buggy python submission (verdict: Runtime Error):
S = input()
cntb = 1000000 if if S[0] == "B" and S[-1] == "B" else 0
cntw = 1000000 if S[0] == "W" and S[-1] == "W" else 0
for s in S.split("B"):
  if s != "":
    cntb += 1
for s in S.split("W"):
  if s != "":
    cntw += 1
print(min(cntb, cntw))

Fixed submission:
from sys import exit
S = input()
#0回判定
x = len(S)
if S.count("B") == x or S.count("W") == x:
    print(0)
    exit()



cntw=0
for s in S.split("W"):
    if s:
        cntw += 1
cntb=0
for s in S.split("B"):
    if s:
        cntb += 1
print(abs(cntb - cntw) + min(cntb, cntw) * 2 - 1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
A = deque(map(str, input()))
B = deque(map(str, input()))
C = deque(map(str, input()))
x = A.popleft()
for _ in range(10000000):
    if x == "a":
        if A:
            x = A.popleft()
        else:
            print("A")
            break
    elif x == "b":
        if B:
            x = B.popleft()
        else:
            print("B")
    else:
        if C:
            x = C.popleft()
        else:
            print("C")


Fixed submission:
from collections import deque
A = deque(map(str, input()))
B = deque(map(str, input()))
C = deque(map(str, input()))
x = A.popleft()
for _ in range(10000000):
    if x == "a":
        if A:
            x = A.popleft()
        else:
            print("A")
            break
    elif x == "b":
        if B:
            x = B.popleft()
        else:
            print("B")
            break
    else:
        if C:
            x = C.popleft()
        else:
            print("C")
            break
Buggy python submission (verdict: Runtime Error):
n, l = map(int, input().split())
A = sorted([input() for _ in range(l)])
print("".join(A))


Fixed submission:
N, L = map(int, input().split())
S = [input() for i in range(N)]
print("".join(sorted(S)))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1
                explored.add(next)
                for i in route[next]:
                    if i not in explored and i not in stock:
                        stock.append(i)
            ans = max(ans,cnt)
    print(ans)
main()            


Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            explored.add(nnext)
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1   
                for i in route[next]:
                    if i not in explored:
                        stock.append(i)
                        explored.add(i)
            ans = max(ans,cnt)
    print(ans)
main()
Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

amax = 0
count = 0

for i in alst:
    if alst[amax] + count <= k:
        count += alst[amax]
        amax += 1
    else:
        break
# print("a:" + str(amax))
"""
while alst[amax] + count <= k:
    # print(str(amax) + " " + str(count))
    count += alst[amax]
    amax += 1
# print(amax)
#amaxはaの最大冊数
"""

anslst = []
count = 0
for i in range(amax+1):
    count = sum(alst[:i])
    bmax = 0
    for j in blst:
        if blst[bmax] + count <= k:
            count += blst[bmax]
            bmax += 1
        else:
            break
    # print("i:" + str(i) + " b:" + str(bmax))
    anslst.append(i+bmax)

print(max(anslst))


Fixed submission:
n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

asum = [0]
bsum = [0]

for i, new in enumerate(alst):
    if asum[i] + new <= k:
        asum.append(asum[i] + new)
    else:
        break
for i, new in enumerate(blst):
    if bsum[i] + new <= k:
        bsum.append(bsum[i] + new)
    else:
        break

bmax = len(bsum)-1
ans = 0

for i, atime in enumerate(asum):
    while atime + bsum[bmax] > k:
        bmax -= 1
    ans = max(ans, i+bmax)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

amax = 0
count = 0

for i in alst:
    if alst[amax] + count <= k:
        count += alst[amax]
        amax += 1
    else:
        break
# print("a:" + str(amax))
"""
while alst[amax] + count <= k:
    # print(str(amax) + " " + str(count))
    count += alst[amax]
    amax += 1
# print(amax)
#amaxはaの最大冊数
"""

anslst = []
count = 0
for i in range(amax+1):
    count = sum(alst[:i])
    bmax = 0
    for j in blst:
        if blst[bmax] + count <= k:
            count += blst[bmax]
            bmax += 1
        else:
            break
    # print("i:" + str(i) + " b:" + str(bmax))
    anslst.append(i+bmax)

print(max(anslst))


Fixed submission:
n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

asum = [0]
bsum = [0]

for i, new in enumerate(alst):
    if asum[i] + new <= k:
        asum.append(asum[i] + new)
    else:
        break
for i, new in enumerate(blst):
    if bsum[i] + new <= k:
        bsum.append(bsum[i] + new)
    else:
        break

bmax = len(bsum)-1
ans = 0

for i, atime in enumerate(asum):
    while atime + bsum[bmax] > k:
        bmax -= 1
    ans = max(ans, i+bmax)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
h = [0] + list(map(int,input().split()))
a,b = [], []
for i in range(m):
    road = list(map(int,input().split()))
    a.append(road[0])
    b.append(road[1])

ans = 0

for i in range(1,n+1):
    max_hight = 0
    j = 0
    while i in a[j:]:
        index = j + a[j:].index(i)
        hight = h[b[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    j = 0
    while i in b[j:]:
        index = j + b[j:].index(i)
        hight = h[a[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    if h[i] > max_hight:
        ans += 1

print(ans)
    

Fixed submission:
n,m = map(int,input().split())
h = [None] + list(map(int,input().split()))
road = [[] for _ in range(n+1)]
count = 0
for _ in range(m):
    a,b = map(int,input().split())
    road[a].append(b)
    road[b].append(a)
for i in range(1,n+1):
    max_hight = 0
    for j in road[i]:
        max_hight = max(max_hight, h[j])
    if h[i]>max_hight:
        count += 1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
h = [0] + list(map(int,input().split()))
a,b = [], []
for i in range(m):
    road = list(map(int,input().split()))
    a.append(road[0])
    b.append(road[1])

ans = 0

for i in range(1,n+1):
    max_hight = 0
    j = 0
    while i in a[j:]:
        index = j + a[j:].index(i)
        hight = h[b[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    j = 0
    while i in b[j:]:
        index = j + b[j:].index(i)
        hight = h[a[index]]
        max_hight = max(max_hight, hight)
        j = index + 1
    if h[i] > max_hight:
        ans += 1

print(ans)
    

Fixed submission:
n,m = map(int,input().split())
h = [None] + list(map(int,input().split()))
road = [[] for _ in range(n+1)]
count = 0
for _ in range(m):
    a,b = map(int,input().split())
    road[a].append(b)
    road[b].append(a)
for i in range(1,n+1):
    max_hight = 0
    for j in road[i]:
        max_hight = max(max_hight, h[j])
    if h[i]>max_hight:
        count += 1

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

k = int(input())
ans = 0
for l in range(1,k+1):
  for m in range(1,k+1):
    for n in range(1,k+1):
      ans += math.gcd(math.gcd(l,m),n)

print(ans)

Fixed submission:
import math
import itertools
def gcd(lst):
  return math.gcd(math.gcd(lst[0],lst[1]), lst[2])

k = int(input())
lst = [i for i in range(1,k+1)]
itr = itertools.combinations_with_replacement(lst, 3)
ans = 0

for i in itr:
  st = set(i)
  num = len(st)
  if num == 1:
    ans += i[0]
  elif num == 2:
    a,b = st
    ans += math.gcd(a,b) * 3
  else:
    ans += math.gcd(math.gcd(i[0],i[1]), i[2]) * 6

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for l in range(1,k+1):
  for m in range(1,k+1):
    for n in range(1,k+1):
      ans += gcd(l,m,n)

print(ans)

Fixed submission:
import math
import itertools
def gcd(lst):
  return math.gcd(math.gcd(lst[0],lst[1]), lst[2])

k = int(input())
lst = [i for i in range(1,k+1)]
itr = itertools.combinations_with_replacement(lst, 3)
ans = 0

for i in itr:
  st = set(i)
  num = len(st)
  if num == 1:
    ans += i[0]
  elif num == 2:
    a,b = st
    ans += math.gcd(a,b) * 3
  else:
    ans += math.gcd(math.gcd(i[0],i[1]), i[2]) * 6

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = [None for _ in range(n)]
    rgb_acc = [None for _ in range(n)]
    rgb_st = {"R","G","B"}
    rgb_lst = ["R","G","B"]
    for i, char in enumerate(s):
        if char == "R":
            rgb[i] = [1,0,0]
        elif char == "G":
            rgb[i] = [0,1,0]
        else:
            rgb[i] = [0,0,1]
    
    rgb_acc[0] = rgb[0]
    for i in range(1, n):
        rgb_acc[i] = rgb_acc[i-1][:]
        rgb_acc[i][rgb[i].index(1)] += 1
    
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
           if s[i]!=s[j]:
                ex = rgb_st - {s[i], s[j]}
                ex = ex.pop()
                index = rgb_lst.index(ex)
                cnt = rgb_acc[n-1][index]-rgb_acc[j][index]
                if j+1 <= 2*j-i < n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt

    print(ans)
main()

Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = [None for _ in range(n)]
    rgb_acc = [None for _ in range(n)]
    rgb_st = {"R","G","B"}
    rgb_lst = ["R","G","B"]
    for i, char in enumerate(s):
        if char == "R":
            rgb[i] = [1,0,0]
        elif char == "G":
            rgb[i] = [0,1,0]
        else:
            rgb[i] = [0,0,1]
    
    rgb_acc[0] = rgb[0]
    for i in range(1, n):
        rgb_acc[i] = rgb_acc[i-1][:]
        rgb_acc[i][rgb[i].index(1)] += 1
    
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
           if s[i]!=s[j]:
                ex = rgb_st - {s[i], s[j]}
                ex = ex.pop()
                index = rgb_lst.index(ex)
                cnt = rgb_acc[n-1][index]-rgb_acc[j][index]
                if j+1 <= 2*j-i < n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt

    print(ans)
main()
Buggy python submission (verdict: Runtime Error):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    x,y,x = LI()
    print(z,x,y)
main()

Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    x,y,z = LI()
    print(z,x,y)
main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    s = S()
    q = I()
    lst = collections.deque(list(s))
    state = False

    for _ in range(q):
        query = LS()
        if len(query) == 1:
            state = not state
        else:
            if state:
                if query[1] == "1":
                    lst.append(query[2])
                else:
                    lst.appendleft(query[2])
            else:
                if query[1] == "1":
                    lst.appendleft(query[2])
                else:
                    lst.append(query[2])
    ans = ""
    if state:
        for _ in range(len(lst)):
            ans += lst.pop()
    else:
        ans = "".join(lst)

    print(ans)
main()            


Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    s = S()
    q = I()
    lst = collections.deque(list(s))
    state = False

    for _ in range(q):
        query = LS()
        if len(query) == 1:
            state = not state
        else:
            if state:
                if query[1] == "1":
                    lst.append(query[2])
                else:
                    lst.appendleft(query[2])
            else:
                if query[1] == "1":
                    lst.appendleft(query[2])
                else:
                    lst.append(query[2])
    ans = ""
    if state:
        for _ in range(len(lst)):
            ans += lst.pop()
    else:
        ans = "".join(lst)

    print(ans)
main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,k = LI()
    p = LI()
    for i,x in enumerate(p):
        if x%2 == 0:
            x = x//2+0.5
        else:
            x = x//2+1
        p[i] = x
    
    ans = 0
    for i in range(n-k+1):
        lst = p[i:i+k]
        # print(p,lst)
        ans = max(ans,sum(lst))
    
    print(ans)
main()            


Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,k = LI()
    p = LI()
    for i,x in enumerate(p):
        if x%2 == 0:
            x = x//2+0.5
        else:
            x = x//2+1
        p[i] = x

    nowsum = sum(p[:k])
    ans = nowsum
    for i in range(k,n):
        nowsum = nowsum - p[i-k] + p[i]
        # print(p,lst)
        ans = max(ans,nowsum)
    
    print(ans)
main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n = I()
    s = list(S())
    itr = itertools.combinations(s,3)
    st = set()
    for i in itr:
        st.add(i)
    print(len(st))
main()

Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    sys.setrecursionlimit(10**5)
    n = I()
    s = S()
    global cnt
    cnt = 0
    def tansaku(st,depth):
        global cnt
        for i in range(10):
            index = st.find(str(i))
            if index != -1:
                if depth == 0:
                    cnt += 1
                    # print(i)
                # print(st,i,index,depth)
                else:
                    tansaku(st[index+1:],depth-1)
    tansaku(s,2)

    print(cnt)

main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n, m = LI()
    a = LI()
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]

    for i in range(m):
        b[i], c[i] = LI()

    dic = collections.Counter(a)
    queue = collections.deque(sorted(list(set(a)|set(c))))

    mn = min(a)
    while queue[0] < mn:
        queue.popleft()

    for i in range(m):
        for x in list(queue):
            if x < c[i]:
                tem = dic[x]
                dic[x] = max(dic[x]-b[i], 0)
                b[i] -= tem-dic[x]
                dic[c[i]] += tem-dic[x]
                if dic[x] == 0:
                    queue.popleft()
                if b[i] == 0:
                    break
            else:
                break

    ans = 0
    for k, v in dic.items():
        ans += k*v

    print(ans)

        


main()


Fixed submission:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n, m = LI()
    a = LI()
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]

    for i in range(m):
        b[i], c[i] = LI()

    dic = collections.Counter(a)
    queue = collections.deque(sorted(list(set(a)|set(c))))

    mn = min(a)
    while queue[0] < mn:
        queue.popleft()

    for i in range(m):
        cnt = 0
        for x in queue:
            if x < c[i]:
                tem = dic[x]
                dic[x] = max(dic[x]-b[i], 0)
                b[i] -= tem-dic[x]
                dic[c[i]] += tem-dic[x]
                if dic[x] == 0:
                    cnt += 1
                if b[i] == 0:
                    break
            else:
                break
        for _ in range(cnt):
            queue.popleft()
    ans = 0
    for k, v in dic.items():
        ans += k*v

    print(ans)

        


main()