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

def main():
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [[0, 0, 1] for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                x += xj*pow(2, n-nj, mod)+yj * \
                    (pow(2, n-nj, mod)-1)-pow(2, nj, mod)+1
                y += yj+pow(2, nj, mod)-1
            dp[i] = [x % mod, y % mod, n]

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()
### BUGGY CODE ###

import math
from functools import reduce

k = int(input())
kl = [i for i in range(1, k+1)]


def gcd(*numbers):
    return reduce(math.gcd, numbers)


total = 0
for i in kl:
    for j in kl:
        for k in kl:
            total += gcd(i, j, k)


print(total)


### FIXED CODE ###

import math

k = int(input())
kl = [i for i in range(1, k+1)]


total = 0
dp = {}
for i in kl:
    for j in kl:
        tmp = math.gcd(i, j)
        for k in kl:
            total += math.gcd(tmp, k)


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

N,Y=[int(i) for i in input().split()]
#a=万 b=五千 c=千
a=0
while a*10000<=Y:
  c=0
  while a*10000+c*1000<=Y:
    B=Y-a*10000-c*1000
    if B%5000==0:
      b=B//5000
      if a+b+c==N:
        print(a,b,c)
        exit()
    c+=1
  a+=1
else :print(-1,-1,-1)

### FIXED CODE ###

N,Y=[int(i) for i in input().split()]
#a=万 b=五千 c=千
a=0
while a*10000<=Y:
  c=0
  while a*10000+c*1000<=Y:
    if a+c>N:break
    B=Y-a*10000-c*1000
    if B%5000==0:
      b=B//5000
      if a+b+c==N:
        print(a,b,c)
        exit()
    c+=1
  a+=1
else :print(-1,-1,-1)
### BUGGY CODE ###

import math

K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      tmp = math.gcd(a,b)
      ans += math.gcd(tmp, c)

print(ans)


### FIXED CODE ###

#-------------------------------------------------------------------------------
# Name:        module6
# Purpose:
#
# Author:      user
#
# Created:     12/04/2020
# Copyright:   (c) user 2020
# Licence:     <your licence>
#-------------------------------------------------------------------------------
from math import gcd



def main():
    k = int(input())
    total = 0

    for a in range(1,k+1):
        for b in range(1,k+1):
            for c in range(1,k+1):
                total += gcd(gcd(a,b),c)
    print(total)


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

import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
tmp,ans = [],[]
for i in range(m):
	if a[i][0] == start:
		tmp.append(a[i][1])
for j in range(m):
	for k in range(len(tmp)):
		if a[j][0] == tmp[k] :
			if a[j][1] == n:
				print('POSSIBLE')
				sys.exit()
print('IMPOSSIBLE')

### FIXED CODE ###

import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])
#print(tmp)
for j in range(m):
		if a[j][0] == start:
			ans.append(a[j][1])
if len(set(tmp)&set(ans)) > 0:
	print('POSSIBLE')
	sys.exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

def resolve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))

    dp = [0 for _ in range(N+K)]

    dp[0] = 0
    dp[1] = abs(H[1] - H[0])
    for tmp in range(1, K):
        #print("tmp:", tmp)
        if tmp+1 >= N:
            break
        candidates = [dp[tmp-k] + abs(H[tmp+1] - H[tmp-k]) for k in range(tmp+1)]
        #print("candidates_a:", candidates)
        dp[tmp+1] = min(candidates)

    #print(dp)
    for i in range(K-1, N-1):
        #print("i", i, "H[i+1]", H[i+1])
        #print("H:", [H[i - k] for k in range(K)])
        #print("diff:", [H[i+1] - H[i - k] for k in range(K)])
        #print("dp:", dp)
        candidates = [dp[i-k] + abs(H[i+1] - H[i-k]) for k in range(K)]
        #print("candidates:", candidates)
        dp[i+1] = min(candidates)

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

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))

    dp = [0] * N

    for i in range(1, N):
        s = max(0, i-K)
        dp[i] = min([c + abs(h - H[i]) for c, h in zip(dp[s:i], H[s:i])] )

    print(dp[N-1])

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

n = int(input())
sum_ij = 1000000000000
for i in range(1, n+1):
  if (n%i==0):
    j = int(n/i)
    if(i+j < sum_ij):
      sum_ij = i+j-2
print(int(sum_ij))

### FIXED CODE ###

import math
n = int(input())
sum_ij = 1000000000000
sq_n = int(math.sqrt(n))
for i in range(1, sq_n+1):
  if (n%i==0):
    j = int(n/i)
    if(i+j < sum_ij):
      sum_ij = i+j-2
print(int(sum_ij))
### BUGGY CODE ###

n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
# while m>0:
for i in range(n):
    if m - b[a.index(min(a))] > 0:
        m -= b[a.index(min(a))]
        ans +=  b.pop(a.index(min(a)))*a.pop(a.index(min(a)))
    else:
        ans +=  m*a.pop(a.index(min(a)))
        m = 0
        print(ans)
        exit()

### FIXED CODE ###

n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
test = list(zip(a,b))
test = sorted(test)
i=0
while m>0:
    if m-test[i][1] >=0:
        ans += test[i][0]*test[i][1]
        m -=test[i][1]
    else:
        ans += test[i][0]*m
        m=0
        print(ans)
        exit()
    i+=1
print(ans)
### BUGGY CODE ###

n = int(input())
listA = list(map(int,input().split()))
count = 0
for k in range(n):
  a = listA[k]
  listA.pop(k)
  #Aはset型で数の種類調べる
  A = list(set(listA))
  for i in A:
    c = listA.count(i)
    count += int(c*(c-1)/2)
  print(count)
  listA.insert(k,a)
  count = 0

### FIXED CODE ###

from collections import Counter
n = int(input())
su = 0
l = list(map(int,input().split()))
l1 = Counter(l)
for k in l1.values():
  su += k*(k-1)//2
for t in l:
  a = l1[t]
  q = su-a*(a-1)//2+(a-1)*(a-2)//2
  print(q)
### BUGGY CODE ###

n = int(input())

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

total = 1
for i in List:
  total = total*i

if total <= 1000000000000000000:
  print(total)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
 
List = [int(i) for i in input().split()]
lst = sorted(List, reverse=True)
if lst[-1] == 0:
  print(0)
  exit()
total = 1
for i in lst:
  total = total*i
  if total > 1000000000000000000:
    print(-1)
    exit()
print(total)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = sorted(pos)
neg = sorted(neg)
mod = 10**9+7
ans = 1
sign = 1
if K%2 == 1: #Kが奇数の時pos（ある場合）から必ず１つ取る
    if len(pos) > 0:
        ans = ans*pos.pop() % mod
    else:
        ans = ans*neg.pop(0) % mod
        sign *= -1
    K -= 1
while K > 0: #偶数の場合と奇数の残りの処理
    if len(pos) == 1 and len(neg) == 1:
        ans = ans*-neg.pop()*pos.pop() % mod
    elif sign == 1:#通常バージョン
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.pop()*neg.pop() % mod
        else:
            ans = ans*pos.pop()*pos.pop() % mod
    else:#奇数の前処理で負になっている場合(最終結果も負になるので小さくしたい)
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.pop(0)*neg.pop(0) % mod
        else:
            ans = ans*pos.pop(0)*pos.pop(0) % mod
    K -= 2
ans = ans*sign % mod
print(ans)



### FIXED CODE ###

from collections import deque #両端から取り出すのが速い
N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9+7
ans = 1
sign = 1
if K%2 == 1: #Kが奇数の時pos（ある場合）から必ず１つ取る
    if len(pos) > 0:
        ans = ans*pos.pop() % mod
    else:
        ans = ans*neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0: #偶数の場合と奇数の残りの処理
    if len(pos) == 1 and len(neg) == 1:
        ans = ans*-neg.pop()*pos.pop() % mod
    elif sign == 1:#通常バージョン
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.pop()*neg.pop() % mod
        else:
            ans = ans*pos.pop()*pos.pop() % mod
    else:#奇数の前処理で負になっている場合(最終結果も負になるので小さくしたい)
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2]*pos[-1] < neg[-2]*neg[-1]):
            ans = ans*neg.popleft()*neg.popleft() % mod
        else:
            ans = ans*pos.popleft()*pos.popleft() % mod
    K -= 2
ans = ans*sign % mod
print(ans)
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
i=0
ans=1
flag=0
k=1e18
while(n>i):
	ans*=p[i]
	if(p[i]==0):
		break
	if(ans>k):
		flag=1
	i+=1		
if((ans>k or flag==1) and ans!=0):
		print(-1)
else:
		print(ans)
		


### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
i=0
ans=1
flag=0
k=1e18
while(n>i):
	if(p[i]==0):
		flag=1
	i+=1
if(flag==1):
	print(0)
else:
	flag=0
	i=0			
	while(n>i):
		ans*=p[i]
		if(ans>k):
			flag=1
			break
		i+=1		
	if( flag==1):
		print(-1)
	else:
		print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
F = np.zeros(N+1, dtype=int)
K = np.arange(N+1, dtype=int)

for i in range(1,(N+1)//2+1):
    F[::i] += 1

F[(N+1)//2+1:] += 1

print(np.sum(K * F))

### FIXED CODE ###

import numpy as np

N = int(input())

count = 0
for i in range(1, N+1):
    count += (N // i) * (i + i * (N//i)) // 2


print(count)
### BUGGY CODE ###

import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
L = []
for p in P:
    for i,j in zip(p,p[1:]):
        xi,yi = zahyo[i]
        xj,yj = zahyo[j]
        L.append(((xi-xj)**2+(yi-yj)**2)**0.5)
    Lsum = sum(L)
print(Lsum/len(P))

### FIXED CODE ###

import itertools
N = int(input())
zahyo =[list(map(int,input().split())) for _ in range(N)]
N_list = [i for i in range(N)]
P = itertools.permutations(N_list,N)
P = list(P)
sm = 0
for p in P:
    for i,j in zip(p,p[1:]):
        xi,yi = zahyo[i]
        xj,yj = zahyo[j]
        sm += (((xi-xj)**2+(yi-yj)**2)**0.5)
print(sm/len(P))
### BUGGY CODE ###

n = int(input())
arr = []
for _ in range(n):
    s = input()
    if not(s in arr):
        arr.append(s)
print(len(arr))

### FIXED CODE ###

n = int(input())
arr = set()
for _ in range(n):
    arr.add(input())
print(len(arr))
### BUGGY CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

n = int(input())

data = []
for _ in range(n):
    data.append("".join(sorted(input())))
# print(data)
data.sort()
# print(data)

answer = 0
for i in range(0,n-1):
    for j in range(i+1,n):
        if data[i] == data[j]:
            answer+=1
        else:
            break
print(answer)

### FIXED CODE ###

"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

n = int(input())

data = {}
for _ in range(n):
    temp = "".join(sorted(input()))
    # print(temp)
    if temp in data.keys():
        data[temp] += 1
    else:
        data[temp] = 1
# print(data)

answer = 0
for num in data.values():
    answer += (num*(num-1))//2
print(answer)
### BUGGY CODE ###

n,x,y=map(int,input().split())

def min_dis(i,j):
    return min(abs(j-i),min(abs(j-x)+abs(y-i)+1,abs(x-i)+abs(j-y)+1))
discount = [0]*n 

for i in range(1,n+1):
    for j in range(1,n+1):
        if i<j:
            discount[min_dis(i,j)]+=1

for i in range(1,n):
    print(discount[i])

### FIXED CODE ###

n,x,y=map(int,input().split())

def min_dis(i,j):
    return min(abs(j-i),min(abs(j-x)+abs(y-i)+1,abs(x-i)+abs(j-y)+1))
discount = [0]*n 

for i in range(1,n+1):
    for j in range(1,n+1):
        if i<j:
            discount[min_dis(i,j)]+=1

for i in range(1,n):
    print(discount[i])
### BUGGY CODE ###

s=list(map(len,input().split("T")))
x,y=map(int,input().split())
def f(t,w):
    for i in range(1<<len(t)):
        z=0
        for j in range(len(t)):
            z+=[1,-1][i>>j&1]*t[j]
        if z==w:
            return True
    return False
print("Yes"if f(s[2::2],x-s[0]) and f(s[1::2],y) else "No")

### FIXED CODE ###

s=list(map(len,input().split("T")))
x,y=map(int,input().split())
def f(t,w):
    m=[{} for i in range(len(t)+1)]
    m[0][0]=1
    for i in range(len(t)):
        for z in m[i]:
            m[i+1][z+t[i]]=1
            m[i+1][z-t[i]]=1
    return w in m[len(t)]
print(["No","Yes"][f(s[2::2],x-s[0]) and f(s[1::2],y)])
### BUGGY CODE ###

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

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)][::-1]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [-x for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

uf = UnionFind(N)
ans = []
for a, b in AB:
    roots = uf.roots()
    ans.append(sum([i*(N-i) for i in roots]))
    uf.union(a, b)
for a in ans[::-1]:
    print(a//2)

### FIXED CODE ###

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

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)][::-1]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [-x for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

uf = UnionFind(N)
ans = []
cnt = N*(N-1)//2
for a, b in AB:
    ans.append(cnt)
    if uf.same(a, b):
        continue
    cnt -= uf.size(a)*uf.size(b)
    uf.union(a, b)
for a in ans[::-1]:
    print(a)
### BUGGY CODE ###

import math

def binaryinsertion(A,x):
    left=0;right=len(A)-1
    while(True):
        centre = math.floor((left + right) / 2)
        if(right == left):
            if(x[0]<A[left][0]):
                A.insert(left,x)
                break
            else :
                A.insert(left + 1,x)
                break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###


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

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

    return divisors

kous = list(map(make_divisors, As))
all = []
for v in kous:
    all += v
all = sorted(list(set(all)), reverse=True)

ans = 1
i = 0
for v in all:
    count = 0
    for k in kous:
        if v in k:
            count += 1
    if count >= N-1:
        ans = all[i]
        break
    i+=1
    
print(ans)


### FIXED CODE ###

import sys
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd



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

left_gcds = [gcd(As[0], As[0])]
for i in range(1, len(As)):
    left_gcds.append(gcd(left_gcds[i-1], As[i]))

right_gcds = [gcd(As[-1], As[-1])]
for i in range(1, len(As)):
    right_gcds.append(gcd(right_gcds[i-1], As[-(i+1)]))
right_gcds.reverse()

gcds = []
for i in range(N):
    if i == 0:
        gcds.append(right_gcds[1])
    elif i == N-1:
        gcds.append(left_gcds[-2])
    else:
        gcds.append(gcd(left_gcds[i-1], right_gcds[i+1]))
print(max(gcds))
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
target = [list(map(int, input().split())) for i in range(M)]
# target = sorted(target, key = lambda x:x[1], reverse=True)
# print(target)

'''
4 4
1 3
2 2
1 1
2 4


'''


for t in target:
    A.extend([t[1]] * t[0])
A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
target = [list(map(int, input().split())) for i in range(M)]
target = sorted(target, key = lambda x:x[1], reverse=True)
# print(target)

'''
4 4
1 3
2 2
1 1
2 4


'''


for t in target:
    A.extend([t[1]] * t[0])
    if len(A) > N * 2:
        break
A.sort(reverse=True)

print(sum(A[:N]))
### BUGGY CODE ###

N, M = map(int, input().split())
job_list = {}
for i in range(N):
	day, pay = map(int, input().split())
	if((day-1) in job_list):
		job_list[day-1].append(pay)
	else:
		job_list[day-1] = [pay]

now_date = 0
money = 0
now_job_list = []
sorted = False
for i in range(M):
	if(i in job_list):
		now_job_list.extend(job_list[i])
		sorted = False
	if(len(now_job_list) > 0):
		if(not sorted):
			now_job_list.sort()
			sorted = True
		money += now_job_list.pop()
print(money)


### FIXED CODE ###

N, M = map(int, input().split())
job_list = {}
for i in range(N):
	day, pay = map(int, input().split())
	if((day-1) in job_list):
		job_list[day-1].append(pay)
	else:
		job_list[day-1] = [pay]

now_date = 0
money = 0
now_job_list = []
sorted = False
for i in range(M):
	if(i in job_list):
		now_job_list.extend(job_list[i])
		sorted = False
	if(len(now_job_list) > 0):
		if(not sorted):
			now_job_list.sort()
			sorted = True
		money += now_job_list.pop()
print(money)
### BUGGY CODE ###

n = int(input())
s = input()
ans = float('inf')
for i in range(n):
    tmp = s[:i].count('W') + s[i+1:].count('E')
    ans = min(ans, tmp)
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
a = s[1:].count('E')
inf = float('inf')
ans = [inf]*n
ans[0] = a
for i in range(1,n):
    if s[i] == 'E':
        ans[i] = ans[i-1] - 1
        if s[i-1] == 'W':
            ans[i] += 1
        else:
            continue
    else:
        ans[i] = ans[i-1]
        if s[i-1] == 'W':
            ans[i] += 1
        else:
            continue
print(min(ans))