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

import fractions

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

i = fractions.gcd(A, B)

C = []

for j in range(2, i+1):
    while True:
        if i%j == 0:
            i //= j
            C.append(j)
        else:
            break

print(len(set(C))+1)

### FIXED CODE ###

import fractions

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

x = fractions.gcd(A, B)

C = []

def cal(i):
    for j in range(2, int(-(-i**0.5//1))+1):
        while True:
            if i%j == 0:
                i //= j
                C.append(j)
            else:
                break
    if i != 1:
        C.append(i)
        
    return set(C)

print(1+len(cal(x)))
### BUGGY CODE ###

n,m= map(int, input().split())
a= list(map(int, input().split()))
a.sort()
mod=998244353

def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(list)):
            a((u + 1), l + [list[u]], r, t)
        return r
    return a(0, [], [], target)

x=get_integral_value_combination(a, m)

ans=0
for i in range(len(x)):
    ans+=pow(2,(n-len(x[i])))
    ans%=mod
print(ans)

### FIXED CODE ###

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

mod=998244353
#dp[i][j]:i番目まで見て値がjである集合の個数
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n):
    for j in range(s+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=mod
        if j+a[i]<=s:
            dp[i+1][j+a[i]]+=dp[i][j]
            dp[i+1][j+a[i]]%=mod

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

import numpy as np
n, m, q = [int(item) for item in input().split(" ")]
end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
for item in query:
    print(np.sum(a[(item[0]-1):, :item[1]]))

### FIXED CODE ###

import numpy as np
n, m, q = [int(item) for item in input().split(" ")]
# n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
#     end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
#     query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)
for item in query:
    print(c[item[0]-1, item[1]-1])
    # print(np.sum(a[(item[0]-1):, :item[1]]))
### BUGGY CODE ###

import itertools
import math
k = int(input())
nums = list(range(1,k+1))
list = list(itertools.product(nums,repeat=3))
gcd = []
for i in range(len(list)):
    gcd.append(math.gcd(math.gcd(list[i][0],list[i][1]),list[i][2]))
print(sum(gcd))

### FIXED CODE ###

from math import gcd
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):
            ans += gcd(gcd(a,b),c)
print(ans)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse = True)
q = sorted(list(map(int, input().split())), reverse = True)
r = sorted(list(map(int, input().split())), reverse = True)
S = sorted(p[:X] + q[:Y] + r[:X+Y], reverse = True)
i = 0
ans = 0
a = 0
b = 0
c = 0
while i < (X + Y):
  if S[0] == r[0]:
    c += 1
    r.remove(r[0])
    ans += S[0]
    i += 1
  elif S[0] == p[0] and a < X:
    a += 1
    p.remove(p[0])
    ans += S[0]
    i += 1
  elif S[0] == q[0] and b < Y:
    b += 1
    q.remove(q[0])
    ans += S[0]
    i += 1
  S.remove(S[0])
print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse = True)
q = sorted(list(map(int, input().split())), reverse = True)
r = sorted(list(map(int, input().split())), reverse = True)
S = sorted(p[:X] + q[:Y] + r[:X+Y], reverse = True)
print(sum(S[:X+Y]))
### BUGGY CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())))

    xor = 0
    for i in b:
        xor ^= i

    ans = 0
    for loop in range(29):
        j = 2**loop  # 2のloop乗
        k = (xor & j) // j  # 下からloop桁目のbit
        #print(j, k)
        temp = []
        for i in b:
            ii = (-i) % j
            if ii == 0:
                ii = j
            temp.append(ii)
        temp.sort()
        x = k*len(a) % 2
        for i in a:
            k2 = 0
            if len(a) % 2 == 1:
                k2 = len(a) * (i & j) // j
            x += (k2 + br(temp, i % j)) % 2
            #print(i % j, br(temp, i % j))
        x %= 2
        ans += x*j
        #print(temp, x)
    print(ans)


main()

### FIXED CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()
### BUGGY CODE ###

from scipy.misc import comb

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

K = {}
for row in A:
    if row in K:
        K[row] += 1
    else:
        K[row] = 1

# 辞書Kに関して全探索
D = {}
C = {}
for row in A:
    ans = 0
    if row not in D:
        for i in K:
            tmp = 0
            if i == row:
                tmp = K[i]-1
            else:
                tmp = K[i]
            if tmp not in C:
                ans += comb(tmp, 2, exact=True)
            else:
                ans += C[tmp]
        D[row] = int(ans)
        print(D[row])
    else:
        print(D[row])


### FIXED CODE ###

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

K = {}
for row in A:
  if row in K:
    K[row] += 1
  else:
    K[row] = 1
        
# 最大数を計算
max = 0
for i in K:
  max += int(K[i]*(K[i]-1)/2)

# 辞書Kに関して全探索
for i in A:
  print(max - int(K[i]*(K[i]-1)/2) + int((K[i]-1)*(K[i]-2)/2) )
### BUGGY CODE ###

def velsup(a,b,c,x):
    if a<=x<=b:
        return c
    elif x<a:
        return (a-x)+c
    else:
        return (x-b)+c

N=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=t[i]+S[i]
TT=S[N]
vt=[0 for i in range(2*TT+1)]
for tt in range(TT*2+1):
    ta=tt/2
    va=min(velsup(-1,0,0,ta),velsup(TT,TT+1,0,ta))
    for i in range(N):
        va=min(va,velsup(S[i],S[i+1],v[i],ta))
    vt[tt]=va
ans=0
for i in range(2*TT):
    ans+=(vt[i]+vt[i+1])*0.25
print(ans)

### FIXED CODE ###

def velsup(a,b,c,x):
    if a<=x<=b:
        return c
    elif x<a:
        return (a-x)+c
    else:
        return (x-b)+c

N=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=t[i]+S[i]
TT=S[N]
vt=[0 for i in range(2*TT+1)]
for tt in range(TT*2+1):
    ta=tt/2
    va=min(velsup(-1,0,0,ta),velsup(TT,TT+1,0,ta))
    for i in range(N):
        va=min(va,velsup(S[i],S[i+1],v[i],ta))
    vt[tt]=va
ans=0
for i in range(2*TT):
    ans+=(vt[i]+vt[i+1])*0.25
print(ans)
### BUGGY CODE ###

import queue
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0 for i in range(N + 1)]
for i in range(Q):
	p, x = getlist()
	plus[p] += x

#幅優先
q = queue.Queue()
val = 0
ans = [0 for i in range(N + 1)]
visit = [-1 for i in range(N + 1)]
visit[1] = 1
q.put(1)
while not q.empty():
	m = q.get()
	ans[m] += plus[m]
	visit[m] = 1
	for i in G.graph[m]:
		if visit[i] == -1:
			q.put(i)
			ans[i] += ans[m]

ans2 = []
for i in range(N):
	ans2.append(ans[i + 1])

print(" ".join(list(map(str, ans2))))

### FIXED CODE ###

from collections import deque
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

G = Graph()

N, Q = getlist()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a, b)
	G.add_edge(b, a)

plus = [0] * (N + 1)
for i in range(Q):
	p, x = getlist()
	plus[p] += x

q = deque([]) 
ans = [0] * N
visit = [-1] * (N + 1)
visit[1] = 1
q.append(1)
while q:
	m = q.pop()
	visit[m] = 1
	ans[m - 1] += plus[m]
	x = ans[m - 1]
	for i in G.graph[m]:
		if visit[i] == -1:
			q.append(i)
			ans[i - 1] += x

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

X = int(input())
flag = 0
minB = -1*int(X**0.2)
for B in range(minB,10**9+1):
    Y = (X+B**5)**0.2
    if Y==int(Y):
        print(int(Y),B)
        break


### FIXED CODE ###

X = int(input())
flag = 0
for A in range(-300,301):
    for B in range(-300,301):
        if A**5 - B**5 == X:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break
### BUGGY CODE ###

K = int(input())
tmp = 7
for i in range(1,K+1):
    if tmp%K == 0:
        print(i)
        exit()
    tmp += 7*10**i%K
    tmp %= K
print(-1)

### FIXED CODE ###

K = int(input())
tmp = 7
for i in range(1,K+1):
    if tmp%K == 0:
        print(i)
        exit()
    tmp = (tmp*10 + 7)%K
    tmp %= K
print(-1)
### BUGGY CODE ###

n = int(input())
numbers = input()

lst = []
lst2 = []
lst3 = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(pin)
    for j in range(i+1, n):
      pin += numbers[j]
      if pin not in lst2:
        lst2.append(pin)
        for k in range(j+1, n):
          pin += numbers[k]
          if pin not in lst3:
            lst3.append(pin)
          pin = pin[0] + pin[1]
      pin = pin[0]
    if ('0' in lst) and ('1' in lst) and ('2' in lst) and ('3' in lst) and ('4' in lst) and ('5' in lst) and ('6' in lst) and ('7' in lst) and ('8' in lst) and ('9' in lst):
      break
print(len(lst3))


### FIXED CODE ###

n = int(input())
numbers = input()

lst = []
ans = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(pin)
    lst2 = []
    for j in range(i+1, n):
      pin += numbers[j]
      if pin[1] not in lst2:
        lst2.append(pin[1])
        lst3 = []
        for k in range(j+1, n):
          pin += numbers[k]
          if pin[2] not in lst3:
            lst3.append(pin[2])
            ans.append(pin)
          if ('0' in lst3) and ('1' in lst3) and ('2' in lst3) and ('3' in lst3) and ('4' in lst3) and ('5' in lst3) and ('6' in lst3) and ('7' in lst3) and ('8' in lst3) and ('9' in lst3):
            break
          pin = pin[0] + pin[1]
      if ('0' in lst2) and ('1' in lst2) and ('2' in lst2) and ('3' in lst2) and ('4' in lst2) and ('5' in lst2) and ('6' in lst2) and ('7' in lst2) and ('8' in lst2) and ('9' in lst2):
        break
      pin = pin[0]
    if ('0' in lst) and ('1' in lst) and ('2' in lst) and ('3' in lst) and ('4' in lst) and ('5' in lst) and ('6' in lst) and ('7' in lst) and ('8' in lst) and ('9' in lst):
      break
print(len(ans))
### BUGGY CODE ###

n,q = [int(i) for i in input().split()]
 
def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
g = [[] * n for i in range(n)]

par = [-1]*n
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

chk = [0]*n
for i in range(q):
    x, y = map(int, input().split())
    chk[x-1] += y

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

dfs(0,-1)
print(*chk)
### BUGGY CODE ###

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

s = 1
if n == k:
	for i in l:
		s *= i
	print(s % 1000000007)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
		print(s % 1000000007)

	else:
		if k % 2 == 1:
			s = pos.pop()
		while len(pos) >= 2:
			answer.append(pos.pop()*pos.pop())
		while len(neg) >= 2:
			answer.append(neg.pop()*neg.pop())
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
		print(s % 1000000007)

### FIXED CODE ###

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

s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []

	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)

	pos.sort()
	neg.sort(reverse=True)
	answer = []

	if k % 2 == 1 and not pos:
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)

	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k//2):
			if len(pos) >= 2:
				answer.append(pos.pop()*pos.pop())
			else:
				break
		for i in range(k//2):
			if len(neg) >= 2:
				answer.append(neg.pop()*neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k//2):
			s *= answer[i]
			s %= 1000000007
		print(s)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
sum = 0
ans = []
for i in range(n-(k-1)):
    sum = 0
    for j in range(i,i+k):
        sum += ((((p[j]+1)*p[j])/2)/p[j])
    ans.append(sum)
print(max(ans))

### FIXED CODE ###

import numpy

n,k = map(int,input().split())
p = list(map(int,input().split()))
q = []
for i in range(n):
    q.append(((((p[i]+1)*p[i])/2)/p[i]))

res = numpy.cumsum(q)
ans = []
ans.append(res[k-1])
for i in range(k,n):
  ans.append(res[i]-res[i-k])
print(max(ans))
### BUGGY CODE ###

k,s = map(int, input().split())
c = 0
for x in range(k+1):
  for y in range(x,k+1):
    for z in range(y,k+1):
      if x+y+z == s:
        if x == y == z:
          c += 1
        elif (x == y and y != z) or (x != y and y == z):
          c += 3
        else:
          c += 6
print(c)

### FIXED CODE ###

k,s = map(int, input().split())
c = 0
for x in range(k+1):
  for y in range(k+1):
    if 0 <= s-x-y <= k:
      c += 1
print(c)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = sum(a)
ans = 0
for i in range(n-1):
    m -= a[i]
    ans += a[i] * m
    ans %= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

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

P = [i+A[i] for i in range(N)]
Q = [j-A[j] for j in range(N)]

cnt = 0
for i in range(N-1):
    cnt += Q[i+1:].count(P[i])

print(cnt)

### FIXED CODE ###

import collections

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

P = [i+A[i] for i in range(N)]
Q = [j-A[j] for j in range(N)]

Q_dict = collections.Counter(Q)

cnt = 0
for i in range(N-1):
    Q_dict[Q[i]] -= 1
    cnt += Q_dict[P[i]]

print(cnt)
### BUGGY CODE ###

num = int(input())
data = []
for i in range(num):
    tmp = int(input())
    data.append(tmp)
for i in range(num):
    tmp = (data[0:i])+(data[i+1:num])
    print(max(tmp))

### 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())
a = []

for _ in range(n):
    var = int(input())
    a.append(var)

first = int(max(a))
if 1<a.count(first):
    second = int(first)
else:
    second = sorted(set(a))[-2]

for _ in a[:]:
    if _ == first:
        print(second)
    else:
        print(first)
### BUGGY CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  s=pin()[:-1]
  K=int(pin())
  d=[]
  for i in range(1,len(s)+1):
    for j in range(len(s)-i+1):
      t=s[j:j+i]
      d.append(t)
    d.sort()
  l=sorted(list(set(d)))
  print(l[K-1])
  return 
main()

### FIXED CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  s=pin()[:-1]
  K=int(pin())
  d=[]
  for i in range(1,K+1):
    for j in range(len(s)-i+1):
      d.append(s[j:j+i])
  ans=sorted(list(set(d)))
  print(ans[K-1])
  return
main()

#解説AC
### BUGGY CODE ###

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

MOD = 998244353 # prime
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD

res = 0
init_nCk()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += nCk(N,a)*nCk(N,b)
        res %= MOD
print(res)

### FIXED CODE ###

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

MOD = 998244353 # prime
MAX = 10**6

fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX

def init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def C(n, k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return fac[n]%MOD * (finv[k] * finv[n-k] % MOD) % MOD

res = 0
init()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += C(N,a)*C(N,b)
        res %= MOD
print(res)
### BUGGY CODE ###

N = int(input())
S = []
for x in range(N):
    S.append(input())
P = sorted([x for x in set(S) if S.count(x) == max([S.count(x) for x in set(S)])])
for x in P:
    print(x)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k] += 1
    else:
        ans.update({k: 1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
edges = []
colors = set()
N = 0

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def to_tree(edges_, n):
    tree_ = {i:[] for i in range(1,n+1)}
    for a, b in edges_:
        tree_[a].append(b)
        tree_[b].append(a)
    return tree_

def suc(u, parent):
    for v in [v for v in tree[u] if (u,v) in edges and (u,v) != (u, parent)]:
        yield u, v

def assign(assignment, u, parent):
    suc_edges = suc(u, parent)
    if not suc_edges:
        return

    lest_colors = colors - {assignment.get((parent, u))}
    for edge, color in zip(suc_edges, lest_colors):
        assignment[edge] = color
        v = edge[0] if edge[1] == u else edge[1]
        assign(assignment, v, u)

def main():
    global tree, edges, colors, N
    N = int(input())
    colors = set(range(1,N))
    edges = list(readlines(N-1))
    tree = to_tree(edges, N)
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = {}
N = 0

def assign(assignment, u, prev_color):
    color = 1
    for v in tree[u]:
        if color == prev_color:
            color += 1
        assignment[u,v] = color
        assign(assignment, v, color)
        color += 1

def main():
    global tree, N
    N = int(input())
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

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

import sys

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = {}
for i in range(m):
    b,c = map(int, input().split())
    if d.get(c) == None:
        d[c] = b
    else:
        d[c] = d[c] + b

for c, b in sorted(d.items()):
    A.sort()
    if b > n:
        b = n

    if A[0] < c:
        if A[b-1] > c:
            for i in range(n):
                if i // c == 0:
                    f = i
                break
            A[:f]=[c]*f
        else:
            A[:b]=[c]*b


print(sum(A))

### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = [list(map(int,input().split())) for _ in range(m)]

d.sort(key=lambda x:-x[1])
total = sum(A)
heapq.heapify(A)

for i in range(m):
    for j in range(d[i][0]):
        tmp = heapq.heappushpop(A, d[i][1])
        if tmp < d[i][1]:
                total += (d[i][1] - tmp)
        else:
            break

print(total)