Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict


def factorization(n):
    dict = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            dict[i] = cnt

    if temp != 1:
        dict[temp] = 1

    if not dict:
        dict[n] = 1

    return dict


n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

prime_factors = defaultdict(int)
factors = []

for a in A:
    a_factors = factorization(a)
    for prime, count in a_factors.items():
        prime_factors[prime] = max(count, prime_factors[prime])
    factors.append(a_factors)

B = []
for a, div_factors in zip(A, factors):
    num = 1
    for prime, count in prime_factors.items():
        dived_count = count - div_factors[prime]
        num *= prime ** dived_count
    B.append(num)

print(sum(B)%mod)

### FIXED CODE ###

import fractions


mod = 10 ** 9 + 7

def lcm(a, b):
    return a * b // fractions.gcd(a, b)


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

num = 1
for a in A:
    num = lcm(num, a)

ans = 0
for a in A:
    ans += num // a
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = []
cnt = 0
for i in range(n):
    tmp = input()
    if tmp not in s:
        s.append(tmp)
        cnt+=1
print(cnt)


### FIXED CODE ###

import numpy as np 
n = int(input())
s = np.empty(n,dtype =object)
for i in range(n):
    s[i] = input()
print(np.unique(s).size)
### BUGGY CODE ###

s, t = map(str, [input() for _ in range(2)])

_s, _t = set(s), set(t)

if len(_s) != len(_t):
    print("No")
    exit(0)

for i in range(len(s)):
    if s.count(s[i]) != t.count(t[i]):
        print("No")
        exit(0)
    
    s.replace(s[i], "")
    t.replace(t[i], "")

print("Yes")



### FIXED CODE ###

s, t = [input() for _ in range(2)]

while True:
    if s == "":
        break

    s = s.replace(s[0], "")
    t = t.replace(t[0], "")
    
    if len(s) != len(t):
        print("No")
        exit(0)

print("Yes")
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]*N
for i in range(K):
  dp.append(10**9)
  H.append(10**9)

for i in range(N-1):
  A=[]
  for j in range(K):
    A.append(dp[i-j]+abs(H[i-j]-H[i+1]))
  dp[i+1]=min(A)

print(str(dp[N-1]))

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]*N

for i in range(N-1):
  A=[]
  for j in range(K):
    if i-j>=0:
      A.append(dp[i-j]+abs(H[i-j]-H[i+1]))
  dp[i+1]=min(A)

print(dp[N-1])
### BUGGY CODE ###

n, p = map(int, input().split())

for i in range(1, int(p**(1/n)) + 10):
    if p%(i**n)== 0:
        ans = i

print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
l = []
ans = 1

for i in range(2, int(p**0.5) + 2):
    if p%i == 0:
        cnt = 0
        while p%i == 0:
            p /= i
            cnt += 1
        l.append([i, cnt])

if p != 1:
    l.append([p, 1])

for i, j in l:
    while j >= n:
        ans *= i
        j -= n

print(int(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
A = []
for i in range(n):
    a, b = map(int, input().split())
    B = [a] * b
    A.extend(B)
A = sorted(A)
print(A[k-1])

### FIXED CODE ###

n, k = map(int, input().split())

A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

C = zip(A, B)
C = sorted(C)
A, B = zip(*C)
for i in range(n):
    a = A[i]
    b = B[i]
    k -= b
    if k <= 0:
        print(a)
        break
### BUGGY CODE ###

from collections import deque

n = int(input())
s = input()
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_a = 0
    rejected_a = 0
    count_internal_b = deque()
    sum_internal_b = 0
    for r, c in enumerate(s):
        if c == 'D':
            count_a += 1
        elif c == 'M':
            count_internal_b.append(count_a)
            sum_internal_b += count_a
        elif c == 'C':
            left_limit = r - k
            while l <= left_limit:
                old_c = s[l]
                if old_c == 'D':
                    rejected_a += 1
                elif old_c == 'M':
                    sum_internal_b -= count_internal_b.popleft()
                l += 1
            ans += sum_internal_b - rejected_a * len(count_internal_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

sum=0
for x in range(0,1+(3000//r)):
    for y in range(0,1+(3000-x*r)//g):
        if r*x+g*y<=n and (n-r*x-g*y)%b==0:
            sum+=1
print(sum)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

sum=0
for x in range(0,1+(n//r)):
    for y in range(0,1+(n-x*r)//g):
        if (n-r*x-g*y)%b==0:
            sum+=1
print(sum)
### BUGGY CODE ###

from fractions import gcd
K = int(input())
N = 0

for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            g = gcd(a,b)
            g = gcd(g,c)
            if(a != 1 or b != 1 or c != 1 ):
                if(a != b or a != c):
                    if(a != K or b != K or c != K ):
                        if(a != b and a != c and b != c):
                            g *= 6
                        else:
                            g *= 3
            N += g

print(N)

### FIXED CODE ###

import math
K = int(input())
N = 0

for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            g = math.gcd(a,b)
            g = math.gcd(g,c)
            if(a != 1 or b != 1 or c != 1 ):
                if(a != b or a != c):
                    if(a != K or b != K or c != K ):
                        if(a != b and a != c and b != c):
                            g *= 6
                        else:
                            g *= 3
            N += g

print(N)
### BUGGY CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    # 5-1292 で一周
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

    dp = [[0] * 13 for _ in range(n + 1)]
    dp[0][0] = 1

    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * 10 ** i) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod

    print(dp[n][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

    dp = [[0] * 13 for _ in range(n + 1)]
    dp[0][0] = 1

    mul = 1
    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * mul) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod
        mul *= 10
        mul %= 13
    print(dp[n][5])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
s=[]
ans=0
for i in range(n):
    s.append(p[i])
    if min(s)==p[i]:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
mins=p[0]
for i in range(1,n):
    if mins>p[i]:
        ans+=1
        mins=p[i]
print(ans+1)
### BUGGY CODE ###

import math as f

K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            total += f.gcd(f.gcd(i, j), k)

print(total)


### FIXED CODE ###

import math as f

K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        ij = f.gcd(i, j)
        if ij == 1:
            total += K
            continue
        for k in range(1, K + 1):
            total += f.gcd(ij, k)

print(total)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

m = 1
for i in a:
    m *= i

if m > 10 ** 18:
    print(-1)
else:
    print(m)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)


if a[-1] == 0:
    print(0)
else:
    m = 1

    for i in a:
        m *= i
        if m > 10 ** 18:
            break

    if m > 10 ** 18:
        print(-1)
    else:
        print(m)
### BUGGY CODE ###

import collections
import numpy as np

n=int(input())
x=np.array([int(item) for item in input().split()])

c = collections.Counter(x)
x_sorted=np.sort(x)

for i in range(n):
  if c[x[i]]>1:
    print(x_sorted[n//2-1])
  else:
    ind=np.ones(n,dtype=bool)
    ind[np.searchsorted(x_sorted,x[i])]=False
    print(x_sorted[ind][n//2-1])
    

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
x_sorted = sorted(x)
pin = x_sorted[n//2]
pre = x_sorted[n//2 - 1]
for i in range(n):
  if x[i] < pin:
    print(pin)
  else:
    print(pre)
### BUGGY CODE ###

def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()

result = []
for skip in range(N):
    l = 0
    r = 0
    for v in range(0, skip):
        l = GCD(l, A[v])
    for v in range(N-1, skip, -1):
        r = GCD(r, A[v])
    result.append(GCD(l, r))

print(max(result))

### FIXED CODE ###

def GCD(a, b):
    """ Euclidean algorithm"""
    if a < b: (a, b) = (b, a)
    if b == 0: return a
    m = a % b
    while m != 0:
        a = b
        b = m
        m = a % b
    return b

N = int(input())
A = [ int(v) for v in input().split() ]

if N < 2 and 1e5 < N: raise()
for v in A:
    if v < 1 and v < 1e9: raise()


l_list = []
l = 0
for i in range(0, N):
    l = GCD(l, A[i])
    l_list.append( l )

r_list = []
r = 0
for i in range(-1, -(N+1), -1):
    r = GCD(r, A[i])
    r_list.append( r )

n = []    
for i in range(0, N):
    if i-1 < 0:
        l = 0
    else:
        l = l_list[i-1]
    if N-i-2 < 0:
        r = 0
    else:
        r = r_list[N-i-2]
    n.append(GCD(l, r))
print(max(n))
### BUGGY CODE ###

import itertools

K, S = map(int, input().split())
count = 0
for v in itertools.combinations(range(S + 2), 2):
    x = v[0]
    y = v[1] - v[0] - 1
    if max(x, y, S - x - y) <= K:
        count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1
print(count)
### BUGGY CODE ###

import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

YenCost, SnuukCost = Yen(s), Snuuk(t)
TotalCost = []
for i in range(n):
    TotalCost.append(YenCost[i] + SnuukCost[i])

print(ini - min(TotalCost))
for i in range(1, n):
    print(ini - min(TotalCost[i:n]))

### FIXED CODE ###

import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

Yen, Snuuk = Yen(s), Snuuk(t)
total, minCost = [], []
tempmin = float("inf")
for i in reversed(range(n)):
    total.append(Yen[i] + Snuuk[i])
    tempmin = min(tempmin, Yen[i] + Snuuk[i])
    minCost.append(tempmin)

for i in reversed(range(n)):
    print(ini - minCost[i])
### BUGGY CODE ###

def resolve():
    import sys
    import math

    readline = sys.stdin.readline

    N = int(readline())

    for i in range(1, N + 1):
        ans = 0
        li = int(math.sqrt(i))
        for x in range(1, li):
            xx = x * x
            for y in range(1, li):
                yy = y * y
                xy = x * y
                x_y = x + y
                value = (x_y) ** 2 - 4 * (xx + yy + xy - i)
                if value <= 0:
                    continue
                cal = math.sqrt(value)
                z1 = (-(x_y) + cal) * 0.5
                z2 = (-(x_y) - cal) * 0.5
                if (1
                        and 1 <= z1
                        and z1 % 1 == 0):
                    ans += 1
                if (1
                        and 1 <= z2
                        and z2 % 1 == 0):
                    ans += 1
        print(ans)


resolve()


### FIXED CODE ###

import sys


def resolve():
    import numpy as np

    readline = sys.stdin.readline

    N = int(readline())

    f = np.zeros(10001, np.int64)

    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                n = x * x + y * y + z * z + x * y + y * z + z * x
                if n > 10000:
                    continue
                f[n] += 1
    for i in range(1, N + 1):
        print(f[i])

resolve()
### BUGGY CODE ###

import numpy as np
N = int(input())
a = [int(i) for i in input().split(" ")]
a = np.array(a,dtype='int')
def count(a):
    return [1 if i==1 or i== 0 or i == -1 else 0 for i in a]
if N == 1:
    print(1)
else:
    min_ = min(a)-1
    max_ = max(a)+1
    ans = -1
    for K in range(min_,max_):
        b = a - K
        tmp = sum(count(b))
        if ans < tmp:
            ans = tmp
    print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = [int(i) for i in input().split(" ")]
dic_num=defaultdict(int)

for i in a:
    dic_num[i] += 1
ans = -1
for X in range(min(a),max(a)+1):
    tmp = (dic_num[X-1] + dic_num[X] + dic_num[X+1])
    if ans < tmp:
        ans = tmp
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
cnt = 0
m = [0] * n
mn = 0
for i in range(0, n):
    if a[i] <= mn:
        m[cnt] = a[i]
        mn = a[i]
        cnt += 1
        continue
    for j in range(cnt):
        if m[j] < a[i]:
            m[j] = a[i]
            break
    else:
        m[cnt] = a[i]
        mn = a[i]
        cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
import collections
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
m = collections.deque([])
for i in range(0, n):
    j = bisect.bisect_left(m, a[i])
    if j == 0:
        m.appendleft(a[i])
    else:
        m[j - 1] = a[i]
print(len(m))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in set(a):
    b = a.count(i)
    dic.setdefault(i, b)
    if b > 1:
        ans += b*(b-1)//2
for i in a:
    print(ans - (dic[i] - 1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 0
ans = 0
dic = {}
for i in a:
    if i not in dic.keys():
        dic[i] = 1
    else:
        dic[i] += 1
for i in dic.values():
    ans += i*(i-1)//2
for i in a:
    print(ans - (dic[i] - 1))
### BUGGY CODE ###

'''
ITP-1_7-B
 ????????????????????°
1 ?????? n ?????§?????°?????????????????????????????§???????????°?????????????????????????¨???? x ??¨??????????????????????????°???
?±???????????????°?????????????????????????????????
????????°???1 ?????? 5 ?????§?????°???????????????????????§????????????????¨???? 9 ??¨???????????????????????????
1 + 3 + 5 = 9
2 + 3 + 4 = 9
??????????????????????????????
???Input
?????°??????????????????????????\?????¨??????????????????????????????????????????????????§??????
????????§??????????????? n???x ??? 1 ???????????????????????????
n???x ?????¨?????? 0 ?????¨?????\?????????????????¨????????????
n ??? 3 ??\??? 100?????\?????¨????????????
???Output
????????????????????????????????????????????????????????°????????????????????????????????????
'''
n, x = map(int, input().split())

while True:

    # EndCheck
    if n == x == 0:
        break

    ansCnt = 0
    for cnt1 in range(1,n+1):
        for cnt2 in range(cnt1+1,n+1):
            for cnt3 in range(cnt2+1,n+1):
                if cnt1 + cnt2 + cnt3 == x:
                    ansCnt += 1
                    break
    print(ansCnt)

### FIXED CODE ###

'''
ITP-1_7-B
 ????????????????????°
1 ?????? n ?????§?????°?????????????????????????????§???????????°?????????????????????????¨???? x ??¨??????????????????????????°???
?±???????????????°?????????????????????????????????
????????°???1 ?????? 5 ?????§?????°???????????????????????§????????????????¨???? 9 ??¨???????????????????????????
1 + 3 + 5 = 9
2 + 3 + 4 = 9
??????????????????????????????
???Input
?????°??????????????????????????\?????¨??????????????????????????????????????????????????§??????
????????§??????????????? n???x ??? 1 ???????????????????????????
n???x ?????¨?????? 0 ?????¨?????\?????????????????¨????????????
n ??? 3 ??\??? 100?????\?????¨????????????
???Output
????????????????????????????????????????????????????????°????????????????????????????????????
'''

while True:
    n, x = map(int, input().split())

    # EndCheck
    if n == x == 0:
        break

    ansCnt = 0
    for cnt1 in range(1,n+1):
        for cnt2 in range(cnt1+1,n+1):
            for cnt3 in range(cnt2+1,n+1):
                if cnt1 + cnt2 + cnt3 == x:
                    ansCnt += 1
                    break

    print(ansCnt)
### BUGGY CODE ###

N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
for i in range(len(l2)):
    if sum(l[i:i+K-1])==0:
        l2[i]=1
        
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif (i!=0) and (P[i-1] < min(P[i:i+K-1])) and (P[i+K-1] > max(P[i:i+K-1])):
        continue
    else:
        count += 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def init(init_val,n):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    return max([x,y])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

def init2(init_val,n):
    #set_val
    for i in range(n):
        seg2[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg2[i]=segfunc2(seg2[2*i+1],seg2[2*i+2])

def segfunc2(x,y):
    return min([x,y])

def update2(k,x):
    k += num-1
    seg2[k] = x
    while k:
        k = (k-1)//2
        seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

def query2(p,q):
    if q<=p:
        return ide_ele2
    p += num-1
    q += num-2
    res=ide_ele2
    while q-p>1:
        if p&1 == 0:
            res = segfunc2(res,seg2[p])
        if q&1 == 1:
            res = segfunc2(res,seg2[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc2(res,seg2[p])
    else:
        res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
    return res

#####単位元######
ide_ele2 = 10**9

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg2=[ide_ele2]*2*num

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
init(P,N)
init2(P,N)
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < query2(i,i+K-1)) and (P[i+K-1] > query(i,i+K-1)) and (i!=0):
        continue
    else:
        count += 1
print(count)
### BUGGY CODE ###

import heapq

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

heapq.heapify(A)

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        tmp = heapq.heappop(A)
        if tmp >= c:
            heapq.heappush(A, tmp)
            break
        heapq.heappush(A, c)

print(sum(A))

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))