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

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

M = 10**6

import math

import random

X = random.sample(range(N), N)

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    i = X[i]
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                break
                
    num_list[A[i]] += 1
    
    if pairwise[i]>0:
        break
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

input()
a=[int(i) for i in input().split()]
ans=1
for i in a:
  ans*=i
print(ans if ans<=10**18 else -1)

### FIXED CODE ###

input()
a=[int(i) for i in input().split()]
ans=1
if 0 in a:
  print(0)
  exit()
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

A, B, N = map(int,input().split())

ans = 0
for x in range(1, N+1, 1):
  i = (A * x // B) - (A * (x // B))
  if i > ans:
    ans = i
else:
  print(ans)

### FIXED CODE ###

A, B, N = map(int,input().split())

def fl(i):
  return ((A * i) // B) - (A * (i // B))

if B <= N:
  print(int(fl(B - 1)))
else:
  print(int(fl(N)))
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
S = input()
ds = defaultdict(list)
for i in range(N):
    ds[S[i]].append(i)

ans = 0
for s in ds:
    d = defaultdict(lambda:[0,-1])
    if len(ds[s])==1:
        continue
    ans = max(ans,1)
    for i in ds[s]:
        t = s
        j = i+1
        while j-i<=N-j-1:
            t = t+S[j]
            if d[t][1] < i:
                d[t][0] += 1
                d[t][1] = j
                ans = max(ans,j-i)
            j += 1
print(ans)

### FIXED CODE ###

def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    z = Z(s)
    for j in range(len(z)):
        z[j] = min(j,z[j])
    ans = max(ans,max(z))

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

a, b = map(int, input().split())

#最大公約数を求める
max_val = max(a, b)
min_val = min(a, b)

while(1):
  if max_val % min_val ==0:
    break
  else:
    tmp = max_val % min_val
    max_val = min_val
    min_val = tmp
    
#print(min_val)

list = []

for i in range(1, min_val//2 + 1):
  if (min_val % i == 0):
    list.append(i)
    
list.append(min_val)

for i in range(len(list)-1,0, -1): # 1は除外
  for j in range(i-1,0,-1):
 #   print("list[i],list[j]",list[i],list[j])
    if list[i] % list[j] == 0 and list[i] > 2:
      list[i] = 0

#print(list)
for i in range(len(list)-1 ,0,-1):
  if list[i]==0:
    list.pop(i)
      
#print(list)
#sum = 0
#for i in range(len(list)):
 # for j in range(i,len(list)):
  #  if (list[j] % list[i]) == 1:
   #   sum += 1
 
print(len(list))

### FIXED CODE ###

import math

a,b = map(int, input().split())

list_a = []
list_b = []
sqrt_a = math.sqrt(a)
sqrt_b = math.sqrt(b)


for i in range(2, int(sqrt_a) ):  
  if (a % (i) == 0):
    list_a.append( i )
    while( a % (i) == 0 ):
      a = a//(i)
if a > 1:
  list_a.append(a)
      
for i in range(2, int(sqrt_b) ):  
  if (b % (i) == 0):
    list_b.append( i )
    while( b % (i ) == 0 ):
      b = b//(i)
if b > 1:
  list_b.append(b)

#print(list_a)
#print(list_b)

set_a = set(list_a)
set_b = set(list_b)

set_ab = set_a & set_b
  
print(len(set_ab) + 1)
### BUGGY CODE ###

N = int(input())
for i in range(1,10**9):
    if i%2==0 and i%N==0:
        print(i)
        break


### FIXED CODE ###

N = int(input())
if N%2==0:
    print(N)
else:
    print(N*2)
### BUGGY CODE ###

N, K = map(int, input().split())
for i in range(10**18):
    if N > abs(N-K):
        N = abs(N-K)
    else:
        print(N)
        exit()

### FIXED CODE ###

N, K = map(int, input().split())
t = N % K
if t > abs(t-K):
    t = abs(t-K)

print(t)
### BUGGY CODE ###

import bisect as bi

def L(x,l):
    return x-l[bi.bisect_left(l,x)-1]

def R(x,l):
    return l[bi.bisect_left(l,x)]-x

def ans(x):
    global s;global t
    
    # 西の神社から訪ねる(d1)
    d1=dLs=L(x,s);dLt=L(x,t)
    if dLt>dLs:
        d1+=min(L(x-dLs,t),R(x-dLs,t))
    
    d2=dRs=R(x,s);dRt=R(x,t)
    if dRt>dRs:
        d2+=min(L(x+dRs,t),R(x+dRs,t))
    
    d3=dLt
    if dLs>dLt:
        d3+=min(L(x-dLt,s),R(x-dLt,s))
    
    d4=dRt
    if dRs>dRt:
        d4+=min(L(x+dRt,s),R(x+dRt,s))
    
    return min(d1,d2,d3,d4)

A,B,Q=map(int,input().split())
s=[-10**10]
for i in range(A):
    s.append(int(input()))
s.append(2*10**10)

t=[-10**10]
for i in range(B):
    t.append(int(input()))
t.append(2*10**10)

for i in range(Q):
    print(ans(int(input())))

### FIXED CODE ###

import bisect as bi

A,B,Q=map(int,input().split())

s=[-10**11]
for i in range(A):
    s.append(int(input()))
s.append(10**11)

t=[-10**11]
for i in range(B):
    t.append(int(input()))
t.append(10**11)

for k in range(Q):
    x=int(input())
    i=bi.bisect_left(s,x)
    sl=s[i-1];sr=s[i]
    j=bi.bisect_left(t,x)
    tl=t[j-1];tr=t[j]
    # print(sl,sr,tl,tr)
    print(min(abs(x-sl)+abs(sl-tl),abs(x-sl)+abs(sl-tr),abs(x-sr)+abs(sr-tl),abs(x-sr)+abs(sr-tr),\
        abs(x-tl)+abs(tl-sl),abs(x-tl)+abs(tl-sr),abs(x-tr)+abs(tr-sl),abs(x-tr)+abs(tr-sr)))
### BUGGY CODE ###

import numpy as np
import math
import sys
n,m = map(int, input().split())
a = np.array(list(map(int, input().split())))
if m > sum(np.ceil(np.log2(a))):
  print(0)
  sys.exit()
used = 0
while used < m:
  i = a.argmax()
  a[i] = a[i]//2
  used +=1
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int, input().split())
a =list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

used = 0
for _ in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a, -1*(-tmp//2))
print(-sum(a))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  dp=[inf for _ in range(10**5+10)]
  dp[0]=0
  n,k=LI()
  l=LI()

  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        # print(dp[i],abs(l[i]-l[i+j]))
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i]-l[i+j]))
    # print(dp[:n])

  return dp[n-1]

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  dp=[inf]*100010
  dp[0]=0
  for i in range(n):
    for j in range(1,k+1):
      if i+j<n:
        dp[i+j]=min(dp[i+j],dp[i]+abs(l[i+j]-l[i]))

  return dp[n-1]

print(main())
### BUGGY CODE ###

def zalgo(s):
	lens = len(s)
	a = [0 for _ in range(lens)]
	maxa = 0
	saisho = -1
	saigo = -1
	for i in range(lens):
		cnt = 0
		j = 0
		if saisho != -1:
			j = min(a[i-saisho], max(0, saigo-i))
		while i+j < lens and s[i+j] == s[j]:
			cnt += 1
			j += 1
		if saigo < i+j:
			saigo = i+j
			saisho = i
		a[i] = cnt
		if cnt > maxa and cnt <= i and i != 0:
			maxa = cnt
	return maxa


n = int(input())
s = input()

ans = 0
for i in range(n):
	k = zalgo(s[i:])
	if ans < k:
		ans = k
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

tmp = 0
for i in range(n-1):
	for j in range(i+tmp+1, n):
		if not s[i:j] in s[j:]:
			break
	tmp = max(tmp, j-i-1)

"""
二重ループ型だが実際はO(ans N)でうごく.
"""

print(tmp)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 21)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])


### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

a = int(input())
b = input()
b = list(map(int, b.split()))
c = 1
for d in range(a):
  c = c * b[d]
if c <= 1000000000000000000:
  print(c)
else:
  print(-1)

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
b.sort()
c = 1
e = 0
for d in range(a):
  c = c * b[0]
  b.pop(0)
  if c > 1000000000000000000:
    print(-1)
    e = 1
    break
if e == 0:
  print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = input()
A = input().split(' ')
A.sort()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))

#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    result = False
    for i in range(n,len(A)):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            result = result or search(base+A[i], m, i+1)
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

### FIXED CODE ###

n = input()
A = input().split(' ')
A.sort()
A.reverse()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))
A.sort()

A_sum = [0]
for a in A:
    A_sum.append(a+A_sum[-1])
A_sum.pop(0)

A.reverse()
A_sum.reverse()


#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    if len(A)-1 < n or m - base > A_sum[n]:
        return False
    result = False
    for i in range(len(A)-1,n-1,-1):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            if search(base+A[i], m, i+1):
                return True
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = input().split()

for x in A:
    a = A[:]
    a.remove(x)
    ans = 0
    for y in set(a):
        m = a.count(y)
        ans += m * (m - 1) // 2
    print(ans)


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())
A = input().split()
a = Counter(A)

ans_all = 0
for x in a.keys():
    m = a[x]
    ans_all += m * (m - 1) // 2

for x in A:
    m = a[x] - 1
    print(ans_all - m)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())

A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = deque()

for i in range(N):
    for j in range(B[i]):
        C.append(A[i])

C = sorted(C)
print(sum(C[:M]))

### FIXED CODE ###

import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline
N, M = map(int, input().split())

A = deque()
for i in range(N):
    A.append(list(map(int, input().split())))

A = sorted(A, key=itemgetter(0))

m=0
cost=0

for i in range(N):
    if m >= M:
        break
    buy = min(M - m, A[i][1])
    cost += A[i][0] * buy
    m += buy

print(cost)
### BUGGY CODE ###

from bisect import *
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  x=bisect_left(LR,k)
  S=LR[:x+1]
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

### FIXED CODE ###

P=998244353
N,K=map(int, input().split())
LR=[list(map(int, input().split())) for _ in range(K)]

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)
### BUGGY CODE ###

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

haba = list()
max_L = 0
min_R = 10 ** 5 + 1
for i in range(M):
    L, R = map(int, input().split())
    haba.append([L, R])
    max_L = max(max_L, L)
    min_R = min(min_R, R)

min_haba = set(range(max_L, min_R + 1))
ids = set()
for L, M in haba:
    h = set(range(L, R + 1))
    ids = ids.union(h.intersection(min_haba))

print(len(ids))

### FIXED CODE ###

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

haba = list()
max_L = 0
min_R = 10 ** 5 + 1
for i in range(M):
    L, R = map(int, input().split())
    haba.append([L, R])
    max_L = max(max_L, L)
    min_R = min(min_R, R)

print(max(min_R + 1 - max_L, 0))
### BUGGY CODE ###

from operator import itemgetter
n,m=map(int,input().split())
l=[]
for i in range(m):
  l2=[]
  a,b=map(int,input().split())
  l2.append(a)
  x=list(map(int,input().split()))
  ct=0
  for i in range(n):
    if i+1 in x:
      ct+=2**i
  l2.append(ct)
  l.append(l2)

dp=[[999999999999 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
  for j in range(2**n):
    dp[i][j|l[i-1][1]]=min(dp[i-1][j|l[i-1][1]],dp[i-1][j]+l[i-1][0],dp[i][j|l[i-1][1]])
  for j in range(2**n):
    dp[i][j]=min(dp[i][j],dp[i-1][j])

if dp[m][2**n-1]<10**11:
  print(dp[m][2**n-1])
else:
  print(-1)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
l=[]
for i in range(m):
  l2=[]
  a,b=map(int,input().split())
  l2.append(a)
  x=list(map(int,input().split()))
  ct=0
  for i in range(n):
    if i+1 in x:
      ct+=2**i
  l2.append(ct)
  l.append(l2)

dp=[[999999999999 for i in range(2**n)] for j in range(m+1)]
dp[0][0]=0
for i in range(1,m+1):
  for j in range(2**n):
    dp[i][j|l[i-1][1]]=min(dp[i-1][j|l[i-1][1]],dp[i-1][j]+l[i-1][0],dp[i][j|l[i-1][1]])
  for j in range(2**n):
    dp[i][j]=min(dp[i][j],dp[i-1][j])

if dp[m][2**n-1]<10**11:
  print(dp[m][2**n-1])
else:
  print(-1)
### BUGGY CODE ###

import sys
 
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
 
    for j in range(N):
        if j == 0:
            print(max(A[1:]))
 
        elif j == N-1:
            print(max(A[:N-1]))
 
        else:
            print(max(max(A[:j]), max(A[j+1:])))
 
 
main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(sys.stdin.readline()) for i in range(N)]
    anoA = sorted(A)
    mA = max(A)

    for j in range(N):
        if mA == A[j]:
            print(anoA[-2])

        else:
            print(mA)


main()
### BUGGY CODE ###

import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = collections.Counter(a)
v = list(d.values())
ans = 0
while len(v) > k:
    ans += v.pop(v.index(min(v)))

print(ans)


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = collections.Counter(a)
v = list(d.values())
v = sorted(v)

ans = 0
i = 0
while len(v) - i > k:
    ans += v[i]
    i += 1

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

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))
    
for i in range(n):
    lis[i]=lis[i].zfill(l)

d=[[0]*2 for _ in range(60)]

for i in range(n):
    l=len(lis[i])
    for j in range(l):
        d[j][int(lis[i][-j-1])]+=1

ans=0
for i in range(60):
    ans+=(d[i][0]*d[i][1]*2**i)%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import math

K=int(input())
ans=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(i,math.gcd(k,j))
print(ans)

### FIXED CODE ###

from math import gcd

K=int(input())
ans=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,gcd(k,j))
print(ans)
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline

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

n = fractions.gcd(A, B)
if n == 1:
    print(1)
    sys.exit()


def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)

    # divisors.sort()
    return divisors


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


d = make_divisors(n)
p = set(get_sieve_of_eratosthenes(n))

print(len(d & p) + 1)


### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline

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

n = fractions.gcd(A, B)
if n == 1:
    print(1)
    sys.exit()


def factorization(n):
    arr = []
    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
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


a = {x[0] for x in factorization(A)}
b = {x[0] for x in factorization(B)}

print(len(a & b) + 1)
### BUGGY CODE ###

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Bad")
    elif q == 0:print("Good")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n,m = ips()
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
a = []
for i in range(m):
    b = [int(i) for i in input().split()]
    b.append(i)
    a.append(b)
a.sort()
city = a[0][0]
ct = 0
c = []
d = []
for i in range(m):
    if city != a[i][0]:
        city = a[i][0]
        ct =1
    else:ct+=1
    cna = str(city)
    cnb = str(ct)
    cna = cna.zfill(6)
    cnb = cnb.zfill(6)
    name = ''.join([cna,cnb])
    c.append([a[i][2],name])
    d.append(int(a[i][2]))
for i in range(m):
    print(c[d.index(i)][1])
"""
c.sort()
for i in range(m):
    print(c[i][1])
"""

### FIXED CODE ###

import math
import fractions
import copy
import numpy as np
#以下てんぷら
def j(q):
    if q==1: print("POSSIBLE")
    elif q == 0:print("IMPOSSIBLE")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
#これを消すとなぜかWAになる呪い

a = []
for i in range(m):
    b = [int(i) for i in input().split()]
    b.append(i)
    a.append(b)
a.sort()
city = a[0][0]
ct = 0
c = []
for i in range(m):
    if city != a[i][0]:
        city = a[i][0]
        ct =1
    else:ct+=1
    cna = str(city)
    cnb = str(ct)
    cna = cna.zfill(6)
    cnb = cnb.zfill(6)
    name = ''.join([cna,cnb])
    c.append([a[i][2],name])
c.sort()
for i in range(m):
    print(c[i][1])
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for  _ in range(M)]#リストの表記が違う
BC.sort(key=lambda x: x[1],reverse=True)#リバースと-1の違い

for b,c in BC:
    A.extend([c]*b)
    if len(A)>N**2:
        break
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))