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

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**9
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)


### FIXED CODE ###

n, a, b = map(int, input().split())
h = [int(input()) for i in range(n)]

left = 0
right = 10**10
mid = (left + right) // 2
while right - left > 1:
    mid = (left + right) // 2
    count = 0
    for i in range(n):
        if h[i] - mid * b > 0:
            if (h[i] - mid * b) % (a - b) == 0:
                count += (h[i] - mid * b) // (a - b)
            else:
                count += (h[i] - mid * b) // (a - b) + 1
    if mid - count >= 0:
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = [0]*q
r = [0]*q
for i in range(q) :
  l[i], r[i] = map(int,input().split())
  c = [0]
  a = 0
  for j in range(n) :
    if s[j:j+2] == 'AC' :
      a += 1
    c.append(a)
  print(c[r[i]-1] - c[l[i]-1])

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
l = [0]*q
r = [0]*q

c = [0]
a = 0
for j in range(n) :
  if s[j:j+2] == 'AC' :
    a += 1
  c.append(a)

for i in range(q) :
  l[i], r[i] = map(int,input().split())
  print(c[r[i]-1] - c[l[i]-1])
### BUGGY CODE ###

S = [i for i in input()]
T = [i for i in input()]
flag = 1
count1 = 0
count2 = 0
if(len(set(S))!=len(set(T))):
  flag = 0
for i in range(len(S)-1):
  if(S[i]==S[i+1]):
    count1 += S.count(S[i])
  if(T[i]==T[i+1]):
    count2 += T.count(T[i])
if(count1!=count2):
  flag = 0
if(flag==1):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

def main():
  S = [s for s in input()]
  T = [s for s in input()]
  R1 = [-1 for i in range(26)]
  R2 = [-1 for i in range(26)]
  for i in range(len(S)):
    a = ord(S[i]) % 26
    b = ord(T[i]) % 26
    if(R1[a] != -1 or R2[b] != -1):
      if(R1[a] != b or R2[b] != a):
        print("No")
        return
    else:
      R1[a]=b
      R2[b]=a
  print("Yes")
  return

main()
### BUGGY CODE ###

import itertools as it
#s = 'abcab'
n = int(input())
s = input()
s_dic = {}
for c in s:
    if not c in s_dic.keys():s_dic[c] = 1
    else:s_dic[c] += 1
#print(s_dic)
g = 0
for i in range(1,len(s_dic)+1):
    a = it.combinations(s_dic.keys(), i)
    #print('lis:',list(a))
    gt = 0
    for t in a:
        #print('combi')
        gi = 1
        for u in list(t):
            #print('u;',u)
            gi *= s_dic[u]
        #print(gi)
        gt += (gi % (10**9+7))
        #gi *= s_dic[t]
    #print(gt)
    g += gt
print(g% (10**9+7))

### FIXED CODE ###

def mul(a,b,p):
    return ((a % p) * (b % p)) % p

def div(a,b,p):
    return mul(a, power_func(b, p-2,p),p)

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

modp = 1000000007
_ = input()
s = input()
d = dict()
for c in s:d[c] = d.get(c,0)+1

g = power_func(2,len(d),modp)
g = (g+modp-1) % modp

for c in sorted(d.keys()):
    subsubg = div((g+1)%modp,2,modp)
    subg = (subsubg % modp) * ((d[c]-1)%modp) % modp
    g = (g + subg) % modp
print(g)
### BUGGY CODE ###

n = int(input())
S = input()
cnt = 0
set_ = set()
for val in range(1000):
    val = str(val).zfill(3)
    a =val[0]
    b = val[1]
    c = val[2]
    flag = False
    for i in range(n):
        if S[i]==a and flag == False:
            for j in range(i+1,n):
                if S[j]==b and flag == False:
                    for k in range(j+1,n):
                        if S[k]==c and flag == False: 
                            cnt += 1
                            flag = True
print(cnt)

### FIXED CODE ###

n = int(input())
S = input()
cnt = 0
set_ = set()
for val in range(1000):
    val = str(val).zfill(3)
    a =val[0]
    b = val[1]
    c = val[2]
    flag = False
    for i in range(n):
        if S[i]==a and flag == False:
            for j in range(i+1,n):
                if S[j]==b and flag == False:
                    for k in range(j+1,n):
                        if S[k]==c and flag == False: 
                            cnt += 1
                            flag = True
                            break
                    break
            break
print(cnt)
### BUGGY CODE ###

from functools import reduce

n = int(input())
a = list(map(int,input().split()))
MAX = 10**18
a.sort()
if a[0] == 0:
    print(0)
else:
    mul = reduce(lambda ans,x:ans*x, a)
    if mul > MAX:
        print(-1)
    else:
        print(mul)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
    
main()
### BUGGY CODE ###

s = input().split();
a = int(s[0]);
b = int(s[1]);
c = int(s[2]);
k = int(s[3]);
max = 0;
while(k > 0):
    if(a > 0):
        max += 1;
        a -= 1;
        k -= 1;
    elif(b > 0):
        b -= 1;
        k -= 1;
    elif(c > 0):
        max -= 1;
        k -= 1;


print(max);

### FIXED CODE ###

s = input().split();
a = int(s[0]);
b = int(s[1]);
c = int(s[2]);
k = int(s[3]);
max = 0;
x = a;
if( (a - k) >= 0 ):
    max = k;
elif((a + b - k) >= 0):
    max = a;
else:
    k = k - (a + b);
    max = -k;
    max = max + a;

print(max);
### BUGGY CODE ###

n=int(input())
nums=input().split()
nums_uniq=[]

for n in nums:
    if n not in nums_uniq:
        nums_uniq.append(n)

#print('uniqnum',nums_uniq)
k=0
for p in nums_uniq:
    if nums.count(p)==int(p):
        continue
    elif nums.count(p)>int(p):
        while nums.count(p)>int(p):
            #print('remove',p)
            nums.remove(p)
            k+=1
    else:
        while nums.count(p)>0:
            #print('remove',p)
            nums.remove(p)
            k+=1
print(k)

### FIXED CODE ###

from collections import Counter
n=int(input())
counter=Counter(map(int,input().split()))
print(sum(c-num if c>=num else c for num,c in counter.items()))
### BUGGY CODE ###

p = int(1e9+7)

N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: format(x, '0b').zfill(60), A))
res = 0

for i in range(60):
    one = 0
    for a in A:
        one += int(a[-(i+1)])
    res += one*(N-one)*2**i
    res %= p

print(res)

### FIXED CODE ###

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

p = int(1e9+7)
res = 0

for i in range(60):
    zc = 0
    oc = 0
    for j in range(len(A)):
        if A[j] % 2 == 0:
            zc += 1
        else:
            oc += 1
        A[j] = A[j] >> 1

    res += zc*oc*2**i
    res %= p

print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[] for _ in range(N)]
    sedge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1].append((v-1,a))
        yedge[v-1].append((u-1,a))
        sedge[u-1].append((v-1,b))
        sedge[v-1].append((u-1,b))
        
    def dij(x,z):
        q = deque([x])
        go = [INF for _ in range(N)]
        go[x] = 0
        while q:
            now = q.pop()
            for fol,d in z[now]:
                if go[fol] > go[now]+d:
                    go[fol] = go[now]+d
                    q.append(fol)
        return go
        
    y,s = dij(s-1,yedge),dij(t-1,sedge)
    ans = []
    u = 0
    for i,j in zip(y[::-1],s[::-1]):
        u = max(u,INF-i-j) 
        ans.append(u)
        
    print(*ans[::-1],sep="\n")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[] for _ in range(N)]
    sedge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1].append((a,v-1))
        yedge[v-1].append((a,u-1))
        sedge[u-1].append((b,v-1))
        sedge[v-1].append((b,u-1))
        
    def dij(x,z):
        q = [(0,x)]
        heapq.heapify(q)
        go = [INF for _ in range(N)]
        go[x] = 0
        while q:
            d,now = heapq.heappop(q)
            if go[now] > d:
                continue
            for d,fol in z[now]:
                if go[fol] > go[now]+d:
                    go[fol] = go[now]+d
                    heapq.heappush(q,(go[fol],fol))
        return go
        
    y,s = dij(s-1,yedge),dij(t-1,sedge)
    ans = []
    u = 0
    for i,j in zip(y[::-1],s[::-1]):
        u = max(u,INF-i-j) 
        ans.append(u)
        
    print(*ans[::-1],sep="\n")

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

def gcd(m,n) :
    x = max(m,n)
    y = min(m,n)
    if x%y == 0 :
        return y
    else :
        while x%y != 0 :
            z = x%y
            x = y
            y = z
        else :
            return z

def lcm(m,n) :
    return int(m*n/gcd(m,n))

N,M = map(int,input().split())
S = list(input())
T = list(input())
A = []
B = []
counter = 0
if N % M == 0 or S[0] != T[0] :
    print(-1)
else :
    L = lcm(N,M)
    for i in range(N) :
        A.append(i*L//N+1)
    for j in range(M) :
        B.append(j*L//M+1)
for k in range(len(B)) :
    if B[k] in A :
        for x in range(len(A)) :
            if A[x] == B[k] :
                a = A[k]
        if S[k] == a :
            break
        else :
            counter += 1
    else :
        counter += 1
if counter == len(B) and len(B) != 0 :
    print(L)
    

### FIXED CODE ###

def gcd(m,n) :
    x = max(m,n)
    y = min(m,n)
    if x%y == 0 :
        return y
    else :
        while x%y != 0 :
            z = x%y
            x = y
            y = z
        else :
            return z

def lcm(m,n) :
    return int(m*n/gcd(m,n))

N,M = map(int,input().split())
S = list(input())
T = list(input())
L = lcm(N,M)
A = []
B = []
flag = 0
counter = 0
if N >= M :
    for i in range(N) :
        A.append(i*L//N+1)
    for j in range(M) :
        b = j*L//M+1
        if j*N % M == 0 :
            index = N*j//M
            if S[index] == T[j] :
                counter += 1
            else :
                flag = 1
                break
        else :
            counter += 1
    if flag == 1 :
        print(-1)
    else :
        if counter == M :
            print(L)
else :
    for i in range(M) :
        A.append(i*L//M+1)
    for j in range(N) :
        b = j*L//N+1
        if j*M % N == 0 :
            index = M*j//N
            if T[index] == S[j] :
                counter += 1
            else :
                flag = 1
                break
        else :
            counter += 1
    if flag == 1 :
        print(-1)
    else :
        if counter == N :
            print(L)
### BUGGY CODE ###

n, k, c = map(int, input().split())
s = input()
accu = []
tmp = 0
r = 0
for cc in s:
    r -= 1
    if cc=='x' or r>0:
        accu.append(tmp)
        continue
    tmp += 1
    accu.append(tmp)
    r = c+1


for i, cc in enumerate(s):
    if cc=='x':
        continue
    if i>0 and accu[i]==accu[i-1]:
        continue
    if i==0:
        tmp = 0
    else:
        tmp = accu[i-1]
    r = 0
    for j in range(i+1, n):
        r -= 1
        if s[j]=='x' or r>0:
            continue
        tmp += 1
        if tmp >= k:
            break
        r = c+1
    else:
        if tmp<k:
            print(i+1)


### FIXED CODE ###

n, k, c = map(int, input().split())
s = input()
fo = []
ba = []
r = 0
for ind, cc in enumerate(s):
    ind += 1
    r -= 1
    if cc=='x' or r>0:
        continue
    fo.append(ind)
    if len(fo)==k:
        break
    r = c+1
r = 0
for ind, cc in enumerate(reversed(s)):
    ind = n-ind
    r -= 1
    if cc=='x' or r>0:
        continue
    ba.append(ind)
    if len(ba)==k:
        break
    r = c+1

for f, b in zip(fo, reversed(ba)):
    if f==b:
        print(f)
### BUGGY CODE ###

s=input()
n=len(s)
# アルファベット(a〜z)→数値(1〜26)小文字限定
a2n = lambda c: ord(c) - ord('a') + 1
# 数値(1〜26)→アルファベット(a〜z)
n2a = lambda c: chr(c+64).lower()
d={}
d_={}
for i in range(1,27):
  d[n2a(i)]=[0]
  d_[n2a(i)]=0
for i in range(n):
  d_[s[i]]+=1
  for j in range(1,27):
    d[n2a(j)].append(2*d_[n2a(j)]-(i+1))
def func(l):
  mina=[0,0]
  for k in range(2,n+1):
    if mina[0]<l[k]:
      return [mina[1]+1,k]
    elif mina[0]>l[k-2]:
      mina=[l[k-2],k-2]
  return [-1,-1]
for i in range(1,27):
  tmp=func(d[n2a(i)])
  if tmp[0]>0:
    print(tmp[0],tmp[1])
    exit()
print(-1,-1)


### FIXED CODE ###

s=input()
n=len(s)
n2a = lambda c: chr(c+64).lower()
d={}
d_={}
for i in range(1,27):
  d[n2a(i)]=[0]
  d_[n2a(i)]=0
for i in range(n):
  d_[s[i]]+=1
  for j in range(1,27):
    d[n2a(j)].append(2*d_[n2a(j)]-(i+1))
def func(l):
  mina=[0,0]
  for k in range(2,n+1):
    if mina[0]<l[k]:
      return [mina[1]+1,k]
    elif mina[0]>l[k-2]:
      mina=[l[k-2],k-2]
  return [-1,-1]
for i in range(1,27):
  tmp=func(d[n2a(i)])
  if tmp[0]>0:
    print(tmp[0],tmp[1])
    exit()
print(-1,-1)
### BUGGY CODE ###

k = int(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

import math
from functools import reduce

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

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

ans = 0
dic = {}
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            tmp = [a,b,c]
            tmp = list(sorted(tmp))
            moji = list(map(str,tmp))
            moji = " ".join(moji)
            try:
                dic[moji]
                ans += dic[moji]
            except:
                num = gcd(tmp[0],tmp[1],tmp[2])
                ans += num
                dic[moji] = num


print(ans)

### FIXED CODE ###

k = int(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

import math
from functools import reduce

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

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

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(a,b,c)

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

import sys
sys.setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for i in range(2 * (10 ** 5))]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for i in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v = -1):
    global d
    for p in T[u]:
        if p != v:
            d[p] += d[u]
            dfs(p, u)

dfs(0)

for v in d:
    print(v)


### FIXED CODE ###

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

N, Q = map(int, input().split())
T = [[] for _ in range(2 * (10 ** 5))]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for _ in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v):
    global d
    for p in T[u]:
        if p == v:
            continue
        d[p] += d[u]
        dfs(p, u)

dfs(0, -1)

for v in d:
    print(v)
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = [int(i) for i in input().split()]
f_list = [int(i) for i in input().split()]
a_list.sort(reverse=True)
f_list.sort()

if k >= sum(a_list):
    print(0)
    exit()

point = []
for i in range(n):
    point.append(a_list[i] * f_list[i])

def binary_search(point, k):
    left = 0
    right = 10 ** 12
    while left + 1< right:
        ans = 0
        center = (left + right) // 2
        for i in range(n):
            if point[i] > center:
                ans += a_list[i] - (center // f_list[i])
        if ans <= k:
            right = center
        else:
            left = center
    return right    
    
value = binary_search(point, k)
print(value)

### FIXED CODE ###

n, k = map(int, input().split())
a_list = [int(i) for i in input().split()]
f_list = [int(i) for i in input().split()]
a_list.sort(reverse=True)
f_list.sort()

if k >= sum(a_list):
    print(0)
    exit()

point = []
for i in range(n):
    point.append(a_list[i] * f_list[i])

import math
def binary_search(point, k):
    left = 0
    right = 10 ** 12
    while left + 1< right:
        ans = 0
        center = (left + right) // 2
        for i in range(n):
            if point[i] > center:
                ans += a_list[i] - (center // f_list[i])
        if ans <= k:
            right = center
        else:
            left = center
    return right    
    
value = binary_search(point, k)
print(value)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
st=set()
while q:
	fro=q.popleft()
	Visit[fro]=1
	st.add(fro)
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
revst=set()
while q:
	fro=q.popleft()
	Visit[fro]=1
	revst.add(fro)
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

#1からもNからも到達可能な頂点の集合
use = st & revst

new_N=sum(use)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if a in use and b in use:
		fedge.append((a,b,c))


D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
cnt=0
for i in range(new_N):
	for a,b,c in fedge:
		cnt+=1
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

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

### FIXED CODE ###

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

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_c

def getMaxGCD(count,product):
	maxPossibleInt = int(float(product)**(1.0/float(count)))
	checkGCDRange = range(maxPossibleInt+1,0,-1)
	maxGCD = maxPossibleInt+1
	for i in checkGCDRange:
		powNumber = i**count
		amari = product % powNumber
		if amari == 0:
			maxGCD = i
			break

	return maxGCD

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))

### FIXED CODE ###

# _*_ coding:utf-8 _*_
#  CADDi2018 for Beginners C
#  https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_a

def getMaxGCD(count,product):
	# getPrimeFunction
	primeSet = []  # リストの初期化
	maxCheckNumber = round(product ** (1 / 2))
	checkRange = range(2, maxCheckNumber + 1, 1)
	for i in checkRange:
		baseCount = 0
		while product % i == 0:
			baseCount = baseCount + 1
			product = product // i
		if  0 < baseCount:
			primeSet.append((i, baseCount))
# 二つを引数にしそれぞれ出力する
	if 1 < product:
		primeSet.append((product, 1))

	gcdNumber = 1
	for baseCount,powNumber in  primeSet:
		gcdNumber = gcdNumber * (baseCount ** ( powNumber // count))
	return gcdNumber

if __name__ == '__main__':
	n , p  = map(int,input().strip().split(' '))
	if n == 1:
		print(p)
		exit(0)
	if p == 1:
		print(1)
		exit(0)
	solution=getMaxGCD(n,p)
	print('{}'.format(solution))
### BUGGY CODE ###

import numpy as np
n = int(input())

if n == 1:
    print(1)
else:
    res_v = np.zeros(n + 1, dtype='int64')
    res_v_cumsum = np.zeros(n + 1, dtype='int64')
    res_v[0] = 0
    res_v[1] = 1
    res_v[2] = 1
    res_v_cumsum[0] = 0
    res_v_cumsum[1] = 1
    res_v_cumsum[2] = 2

    M = 1000000007

    for k in range(3, n):
        res_v[k] = (1 + res_v_cumsum[k-1] - res_v[k-2]) % M
        res_v_cumsum[k] = (res_v_cumsum[k-1] + res_v[k]) % M

    print((((res_v_cumsum[n-2] * (((n-1) * (n-1)) % M)) % M) + ((res_v_cumsum[n-1] * (n-1)) % M) + n + (n-1)*(n-1)%M) % M)

### FIXED CODE ###

n = int(input())

if n == 1:
    print(1)
else:
    res_v = [0]*(n + 1)
    res_v_cumsum = [0]*(n + 1)
    res_v[0] = 0
    res_v[1] = 1
    res_v[2] = 1
    res_v_cumsum[0] = 0
    res_v_cumsum[1] = 1
    res_v_cumsum[2] = 2

    M = 1000000007

    for k in range(3, n):
        res_v[k] = (1 + res_v_cumsum[k-1] - res_v[k-2]) % M
        res_v_cumsum[k] = (res_v_cumsum[k-1] + res_v[k]) % M
    #print(res_v)
    print((((res_v_cumsum[n-2] * (((n-1) * (n-1)) % M)) % M) + ((res_v_cumsum[n-1] * (n-1)) % M) + n + (n-1)*(n-1)%M) % M)
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
BC.sort(key=lambda x: (x[1]), reverse=True)

for B, C in BC: # O(10^5)
    A.sort()
    if A[0] > C:
        break
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break

print(sum(A))

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda x: (x[1]), reverse=True)

i = 0
A_len = len(A)

for B, C in BC: # O(10^5)
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
            if i > A_len - 1:
                print(sum(A))
                exit()
        else:
            print(sum(A))
            exit()

print(sum(A))