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

def cmp(A,B):
    ans = True
    n = len(A)
    i = 0
    while i < n:
        if A[i] == B[i]:
            i += 1
        else:
            ans = False
            break
    return ans

N = int(input())
L = []
i = 0
while i < N:
    tmp = input()
    L.append(sorted(tmp))
    i += 1

cnt = 0
i = 0

while i < N-1:
    j = i+1
    while j < N:
        if cmp(L[i],L[j]):
            cnt += 1
        j += 1
    i += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    tmp = list(input())
    tmp.sort()
    s.append(str(tmp))
cnt = 0
dict = {}
for x in s:
    if x in dict:
        cnt += dict[x]
        dict[x] += 1
    else:
        dict[x] = 1
print(cnt)
### BUGGY CODE ###

import sys
import heapq as hq
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [(-b[i], i) for i in range(N) if a[i] != b[i]]
hq.heapify(sb)
res = 0
while len(sb):
  v, i = hq.heappop(sb)
  v = -v
  if v < a[i]:
    print(-1)
    exit(0)
  elif v == a[i]: continue
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hq.heappush(sb, (-b[i], i))
print(res)

### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = [int(i) for i in input().split()]

for i in range(len(p_list)-k+1):
    sum_temp = sum(p_list[i:i+k])
    if i == 0:
        sum_max = sum_temp
        index = i
    elif sum_temp > sum_max:
        sum_max = sum_temp
        index = i
    
kitaichi = 0
for i in range(k):
    temp_index = index + i
    kitaichi += (1+p_list[temp_index])/2
    
print(kitaichi)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
p_list = [int(i) for i in input().split()]

p_list = [0] + p_list

cum_list = []
p_sum = 0
for p in p_list:
    p_sum += p
    cum_list.append(p_sum)
    
cum_list = np.array(cum_list)
sum_list = cum_list[k:]-cum_list[:-k]
index = np.argmax(sum_list)

kitaichi = k/2 + sum_list[index]/2

print(kitaichi)
### BUGGY CODE ###

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remains[-(r+1)] = int(''.join(s[n - r - 1:n])) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10)
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)
  

if __name__=='__main__':
  main()


### FIXED CODE ###

n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i

else:
    for i in range(n):
        d = s[i] * pow(10, i, p)
        sum = (sum + d) % p
        cnt[sum] += 1
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2
print(ans)
### BUGGY CODE ###


n = int(input())

ans=0
for i in range(1,n):
    ans+=i

print(ans)

### FIXED CODE ###

from decimal import Decimal

n = int(input())
print(int(Decimal((n-1)/2)*Decimal(n)))
### BUGGY CODE ###

MOD = 1000000007

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

ans = 0
for k in range(60):
    cnt1 = 0
    for x in a:
        if ((x>>k)&1) == 1:
            cnt1 += 1
    ans += cnt1*(n-cnt1)*(1<<k)
    if ans > MOD:
        ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 1000000007

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

ans = 0
for k in range(60):
    mask = 1<<k
    cnt1 = sum(1 for x in a if x&mask != 0)
    ans += cnt1*(n-cnt1)*(1<<k)
print(ans%MOD)
### BUGGY CODE ###

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
for i in range(length//2+length%2):
    num=0
    # for j in range(width):
    #     if 2*i+j>=length:
    #         break
    #     num+=s_seqcnt[2*i+j]
    # s_sum[i]=num
    if 2*i+width-1>=length:
        s_sum[i]=sum(s_seqcnt[2*i:])
        break
    else:
        s_sum[i]=sum(s_seqcnt[2*i:2*i+width])
# print(s_sum)
print(max(s_sum))


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
s_ruiseki=[0 for i in range(length+1)]
s_ruiseki[0]=0
s_ruiseki[1]=s_seqcnt[0]
for i in range(1,length):
    s_ruiseki[i+1]=s_seqcnt[i]+s_ruiseki[i]
# print(s_ruiseki)
for i in range(length//2+length%2):
    num=0
    if 2*i+width-1>=length:
        s_sum[i]=s_ruiseki[length]-s_ruiseki[2*i]
        break
    else:
        s_sum[i]=s_ruiseki[2*i+width]-s_ruiseki[2*i]
# print(s_sum)
print(max(s_sum))
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

tree = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

tree_next = [0 for _ in range(n)]
for i in range(n):
  key = set()
  for value in tree[i]:
    key.add(value)
    for value2 in tree[value]:
      key.add(value2)
  key.discard(i)
  tree_next[i] = key
not_yet = deque([0])
already = [False]*n
already_list = set()
already[0] = True

ans = 1
while not_yet:
  key = not_yet.popleft()
  next_key = k-len(already_list&tree_next[key])
  ans *= next_key
  ans %= inf
  already_list.add(key)
  for value in tree[key]:
    if not already[value]:
      not_yet.append(value)
      already[value] = True

print(ans)

### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

tree = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

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

from functools import lru_cache

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(tuple(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

@lru_cache(maxsize = 2**26)
def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = info[1]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()

### FIXED CODE ###

from functools import lru_cache

def main():
    N = int(input())
    infos = []
    for i in range(1,N):
        infos.append(tuple(map(int, input().split())))

    for i in range(1,N):
        current_time = 0
        for station_number in range(i,N):
            current_time = next_arrival_time(current_time, infos[station_number -1])
        print(current_time)
    print(0)

@lru_cache(maxsize = 2**26)
def next_arrival_time(current_time, info):
    if current_time <= info[1]:
        return info[1] + info[0]

    next_time = current_time
    remainder = next_time % info[2]
    while remainder != 0:
        next_time += 1
        remainder = next_time % info[2]
    while next_time < current_time:
        next_time += info[2]

    return next_time + info[0]

main()
### BUGGY CODE ###

import numpy as np

N = int(input())

num_list = [int(input()) for i in range(N)]

array = np.array(num_list)

[print((np.delete(array, i).max())) for i in range(N)]

### FIXED CODE ###

N = int(input())

num_list = [int(input()) for i in range(N)]

sort_num_list = sorted(num_list)
max_n = sort_num_list[-1]
smax_n = sort_num_list[-2]

for i in num_list:
  if i==max_n:
    print(smax_n)
  else:
    print(max_n)
### BUGGY CODE ###

K , S = map(int, input().split())
pattern = 0

for i in range(0, K+1):
  for j in range(0, K+1):
    for k in range(0, K+1):
      if (i+j+k)==S:
        pattern = pattern+1
print(pattern)

### FIXED CODE ###

K , S = map(int, input().split())
pattern = 0

for i in range(0, K+1):
  for j in range(0, K+1):
    if ((S - (i+j)) <= K) & (S - (i+j) >= 0):
      pattern = pattern+1
print(pattern)
### BUGGY CODE ###

k=int(input())
s=len(input())
c=1
m=10**9+7
p=0
a=[1]
b=[1]
for i in range(k):
    a.append(a[-1]*25%m)
    b.append(b[-1]*26%m)
for i in range(k+1):
    p=(p+a[i]*b[k-i]*c)%m
    c=(c*(s+i)*pow(i+1,m-2,m))%m
print(p)

### FIXED CODE ###

k=int(input())
s=len(input())
c=1
m=10**9+7
p=0
a=[1]
b=[1]
for i in range(k):
    a.append(a[-1]*25%m)
    b.append(b[-1]*26%m)
for i in range(k+1):
    p=(p+a[i]*b[k-i]*c)%m
    c=(c*(s+i)*pow(i+1,m-2,m))%m
print(p)
### BUGGY CODE ###


def findNumberOfTriangles(arr, n): 
	count = 0
	
	
	 
	for i in range(n): 
		for j in range(i + 1, n): 
			
			
			
			for k in range(j + 1, n): 
				
				 
				 
				if (arr[i] + arr[j] > arr[k] and
					arr[i] + arr[k] > arr[j] and
					arr[k] + arr[j] > arr[i]): 
					count += 1
	return count 
n=int(input())
li = [int(x) for x in input().split()]

print( findNumberOfTriangles(li, len(li))) 


### FIXED CODE ###


def findnumberofTriangles(arr): 
	n = len(arr) 
	arr.sort() 
	count = 0
	for i in range(0, n-2):  
		k = i + 2 
		for j in range(i + 1, n):  
			while (k < n and arr[i] + arr[j] > arr[k]): 
				k += 1
			if(k>j): 
				count += k - j - 1

	return count 

n = int(input())
arr=[int(x) for x in input().split()]
print(findnumberofTriangles(arr))
### BUGGY CODE ###

import fractions
import functools

def multiple(a, b):
    return a*b // fractions.gcd(a, b)
def lcm(nums):
  return functools.reduce(multiple, nums)

def main():
  N = int(input())
  A = list(map(int, input().split()))
  B = set(A[:])
  n = lcm(B)
  ans = 0
  mod = 10**9+7
  for a in A:
    ans += n//a
    ans %= mod

  print(ans)

if __name__ == "__main__":
  main()



### FIXED CODE ###

from fractions import gcd

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

x = 1
for i in range(N):
  x = (x*A[i]) // gcd(x, A[i])

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

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

ans=0
for i in range(N-K+1):
    ans=max(ans, sum(p[i:i+K]))

print((ans+K)/2)

### FIXED CODE ###

import numpy as np

N,K=map(int,input().split())
p=np.array(list(map(int,input().split())))

pcm=np.concatenate([np.array([0]),(p+1).cumsum()],0)

print((pcm[K:]-pcm[0:-K]).max() /2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

ans = 0
two  = 1
for i in range(61):
  n = sum([int(bin(a>>i)[-1]) for a in A])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=(a[i]*a[j])%mod
        ans=ans%mod

print(ans%mod)



### FIXED CODE ###

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

tmp=a[-1]
ans=0
for i in range(n-1):
    ii=n-i-2
    #print(ii)
    ans+=(tmp*a[ii])%mod
    ans=ans%mod
    tmp+=a[ii]%mod

print(ans%mod)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

n=int(input());Alist=list(map(int,input().split()))

def gcd_L(numbers):
    return reduce(gcd, numbers)

M_list = []
for i in range(n):
    alist = Alist[:i] + Alist[i+1:]
    M_list.append(gcd_L(alist))

print(max(M_list))

### FIXED CODE ###

from fractions import gcd
 
n,*a = map(int, open(0).read().split())
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))
### BUGGY CODE ###

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

from collections import deque
maze = []
for i in range(H):
    maze.append(list(input()))
times = [[-1]*W for i in range(H)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
que = deque([])
que.append((Ch, Cw))
times[Ch][Cw] = 0
cnt = 0
flag = 0
while flag==0:
    loc = deque([])
    while que:
        p = que.popleft()
        wallflag = 0
        if p[0] == Dh and p[1] == Dw:
            times[Dh][Dw] = cnt
            flag = 1
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==-1):
                que.append((nh, nw))
                times[nh][nw] = cnt
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]=="#"):
                wallflag = 1
        if wallflag ==1:
            loc.append(p)
    que = deque([])
    while loc:
        p = loc.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                nh = p[0] + i
                nw = p[1] + j
                if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==-1):
                    que.append((nh, nw))
    if len(que)==0:
        break
    cnt += 1

if times[Dh][Dw] == -1:
    print(-1)
else:
    print(times[Dh][Dw])

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())
si, sj, gi, gj = si-1+2, sj-1+2, gi-1+2, gj-1+2
X = [[1] * (W + 4)] * 2 + [[1] * 2 + [1 if a == "#" else 0for a in input()] + [1] * 2 for _ in range(H)] + [[1] * (W + 4)] * 2
H += 4
W += 4

Y = [(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)]
Z = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

def BFS():
    Q = deque([(si, sj)])
    D = [-1] * (H * W)
    D[si*W + sj] = 0
    while Q:
        i, j = Q.popleft()
        x = i * W + j
        for di, dj in Y:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1 or D[y] > D[x]:
                    D[y] = D[x]
                    Q.appendleft((ni, nj))
        for di, dj in Z:
            ni, nj = i+di, j+dj
            y = ni * W + nj
            if X[ni][nj] == 0:
                if D[y] == -1:
                    D[y] = D[x] + 1
                    Q.append((ni, nj))
    return D[gi * W + gj]

print(BFS())
### BUGGY CODE ###

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def split(ary, a, b, i):
    if len(ary) == i:
        if a == 1 or b == 1:
            return a + b - 1
        else:
            return a + b - 2
    v = ary[i]

    v1 = split(ary, a * v, b, i+1)
    v2 = split(ary, a, b * v, i+1)
    return min(v1, v2)

ary = prime_factorize(N)

if len(ary) == 1:
    print(str(ary[0] - 1))
elif len(ary) == 2:
    cost = ary[0] + ary[1] - 2
    print(str(cost))
else:
    v = split(ary, 1, 1, 0)
    print(str(v))

### FIXED CODE ###

import math
N = int(input())

def eval_ab(a, b):
    if a == 1 or b == 1:
        return a + b - 1
    else:
        return a + b - 2
    
min_e = N - 1
a = int(math.sqrt(N)) + 2
for i in range(1, a):

    if N % i == 0:
        j = N // i
        e = eval_ab(i, j)
        min_e = min(e, min_e)

print(min_e)
### BUGGY CODE ###

import math
def gcd_arg3(a,b,c):
    return math.gcd(a,math.gcd(b,c))

k = int(input())

ans_list = list()
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans_list.append(gcd_arg3(a,b,c))

print(sum(ans_list))

### FIXED CODE ###

import math
def gcd_arg3(a,b,c):
    return math.gcd(a,math.gcd(b,c))

k = int(input())

sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        gcd_a_b = math.gcd(a,b)
        for c in range(1,k+1):
            sum += math.gcd(gcd_a_b,c)

print(sum)
### BUGGY CODE ###

import numpy as np

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

a_dic = {}
for i, a in enumerate(A):
    a_dic[i] = a

for m in range(M):
    max_a = max(a_dic, key=a_dic.get)
    a_dic[max_a] = a_dic[max_a] // 2

ans = sum(a_dic.values())
if ans < 0:
    ans = 0
print(ans)


### FIXED CODE ###

import time
import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = time.time()
ans = []
for a in A:
    heapq.heappush(ans, -a)

for _ in range(M):
    l = heapq.heappop(ans)
    heapq.heappush(ans, -((-l)//2) )

print(-sum(ans))
### BUGGY CODE ###

from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != i)
print(1 if n == 1 else cnt)

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)
### BUGGY CODE ###

n = int(input())
from fractions import gcd
import math
import functools
t = []
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            t.append([i,j,k])
for i in range(len(t)):
    gcd = functools.reduce(math.gcd, t[i])
    ans += gcd
print(ans)



    

### FIXED CODE ###

n = int(input())
from fractions import gcd
import math
import functools
t = []
ans = 0
for i in range(1,n+1):
    for j in range(i,n+1):
        for k in range(j,n+1):
            #t.append([i,j,k])
            t = [i,j,k]
            if i==j==k:
                gcd = functools.reduce(math.gcd, t)
                ans += gcd
            elif i!=k and j!=k and i!=j:
                gcd = functools.reduce(math.gcd, t)
                ans += gcd*6
            else:

                gcd = functools.reduce(math.gcd, t)
             
                ans += gcd*3
            #print(t,ans)

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

# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 * 20
m = [[0] * N for _ in range(N)]
tt = [0] * N

#print(ret)
#print(len(ret))

for r in range(N):
	for c in range(r+1, N):
		m[r][c] = c - r
		#m[c][r] = m[r][c]
		tt[m[r][c]] += 1
		m[c][r] = m[r][c]

def Set(r, c, v):
	tt[m[r][c]] -= 1
	m[r][c] = v
	tt[m[r][c]] += 1

for r in range(N):
	if m[r][X] < m[r][Y]:
		Set(r, Y, m[r][X]+1)
	for c in range(Y+1, N):
		if m[r][c] <= m[r][c-1]:
			break
		Set(r, c, m[r][c-1]+1)
	for c in range(Y-1, X, -1):
		if m[r][c] <= m[r][c+1]:
			break
		Set(r,c, m[r][c+1]+1)

for t in tt[1:]:
	print (t)

### FIXED CODE ###

# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 * 20
m = [[0] * N for _ in range(N)]
tt = [0] * N

#print(ret)
#print(len(ret))

for r in range(N):
	for c in range(r+1, N):
		m[r][c] = c - r
		#m[c][r] = m[r][c]
		tt[m[r][c]] += 1
		m[c][r] = m[r][c]

def Set(r, c, v):
	if m[r][c] < v:
		return False
	else:
		tt[m[r][c]] -= 1
		m[r][c] = v
		tt[m[r][c]] += 1
		return True

for r in range(N):
	if not Set(r, Y, m[r][X]+1):
		continue
	for c in range(Y+1, N):
		if not Set(r, c, m[r][c-1]+1):
			break
	for c in range(Y-1, X, -1):
		if not Set(r,c, m[r][c+1]+1):
			break

for t in tt[1:]:
	print (t)
### BUGGY CODE ###

import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
L = []
for i in range(m):
    L.append(list(map(int,input().split())))
for i in range(m):
    b = L[i][0]
    c = L[i][1]
    for j in range(b):
        heapq.heappush(A,c)
    for j in range(b):
        heapq.heappop(A)
print(sum(A))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
L = []
for i in range(n):
  L.append([A[i],1])
for i in range(m):
  a,b = map(int,input().split())
  L.append([b,a])
L.sort()
L.reverse()
s = 0
t = 0
ans = 0
while s < n:
  if L[t][1]+s <= n:
    ans += L[t][1]*L[t][0]
    s += L[t][1]
    t += 1
  else:
    ans += L[t][0]*(n-s)
    s = n
    t += 1
print(ans)