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

from bisect import bisect_left

R = lambda: map(int, input().split())
n, m = R()
a = sorted(R())
for _ in range(m):
    b, c = R()
    l = bisect_left(a, c)
    if l > b:
        a[: l - b] = a[b : l]
    for i in range(max(0, l - b), l):
        a[i] = c
print(sum(a))


### FIXED CODE ###

import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: map(int, input().split())
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        heapq.heappop(a)
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heappush(a, (x, y))
    heapq.heappush(a, (c, b - i))
print(sum(starmap(mul, a)))
### BUGGY CODE ###

n=int(input())
a = []
for i in range(n):
    a.append(input())
a_count = [a.count(i) for i in a]
[print(j) for j in sorted(set([a[i] for i in range(len(a_count)) if a_count[i] == max(a_count)]))]

### FIXED CODE ###

d=dict()
for i in range(int(input())):
    s=input()
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
max_v = max(d.values())
print(*sorted([kv[0] for kv in d.items() if kv[1] == max_v]))
### BUGGY CODE ###

import math
N = int(input())
 
yakusu = [0] * (N+1)
for i in range(1,N+1):
    for j in range(1,min(i, int(N/i))+1):
      M = i*j
      if i == j:
        yakusu[M] += 1
      else:
        yakusu[M] += 2

print(sum(yakusu[1:N]))

### FIXED CODE ###

N = int(input())

counter = 0
for i in range(1,N):
    for j in range(1,min(i, int((N-1)/i))+1):
      if i == j:
        counter += 1
      else:
        counter += 2

print(counter)
### BUGGY CODE ###

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b

    return gcd(b % a, a)


N = int(input())
A = [int(v) for v in input().split()]
max_gcd = -1

for i in range(N):
    tmp = None
    for j in range(N):
        if j == i: continue
        if tmp is None:
            tmp = A[j]
            continue

        # print(tmp, A[j], gcd(tmp, A[j]))
        tmp = gcd(tmp, A[j])
    max_gcd = max(tmp, max_gcd)
if max_gcd < 0:
    print(A[0])
else:
    print(max_gcd)


### FIXED CODE ###

N = int(input())
A = [int(v) for v in input().split()]


def gcd(a, b):
    if a > b:
        a, b = b, a

    if a == 0: return b
    return gcd(a, b % a)


L = [0 for _ in range(N + 2)]
R = [0 for _ in range(N + 2)]

for i, a in enumerate(A):
    L[i + 1] = gcd(A[i], L[i])
    R[N-i] = gcd(A[N-i-1], R[N-i+1])

# print(L)
# print(R)

res = -2
for i in range(1, N+1):
    res = max(res, gcd(L[i-1], R[i+1]))
print(res)
### BUGGY CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue.append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A[i] > tmp[-1]:
                tmp.append(A[i])
            else:
                tmp[bisect.bisect_left(tmp, A[i])] = A[i]
            queue.append((i,tmp))
            ans[i] = len(tmp)

    for i in range(N):
        print(ans[i])

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

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

from collections import deque
import copy
n = int(input())

games = [0]*n

for i in range(n):
  games[i] = deque([int(x) for x in input().split()])

ans = 0
already = [False]*n
fin = 0
while True:
  flag = False
  key = copy.deepcopy(already)
  for i in range(n):
    if key[i]:
      continue
    k = games[i][0]-1
    if key[k]:
      continue
    if games[i][0] > i+1 and games[k][0] == i+1:
      flag = True
      key[k] = True
      games[k].popleft()
      games[i].popleft()
      if len(games[k]) == 0:
        already[k] = True
        fin += 1
      if len(games[i]) == 0:
        already[i] = True
        fin += 1
  if flag:
    ans += 1
  else:
    ans = -1
    break
  if fin == n:
    break
    
print(ans)

### FIXED CODE ###

import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()
a = [int(input()) for i in range(m)]

l = [0] * (n+1)
l[0] = 1
for i in range(n+1):
     if i not in a:

         if i == 1:
            l[i] = 1
         elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007


#print(l)
print(l[n] % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

l = [0] * (n+1)
l[0] = 1

a = 0
if m != 0:
    a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())



#print(l)
print(l[n] % 1000000007)
### BUGGY CODE ###

from collections import defaultdict
def f(n,k):
    to = defaultdict(list)
    for _ in range(n - 1):
        a, b = map(int, input().split())
        to[a] += [b]
        to[b] += [a]
    ans = 1
    fin = [0] * (n + 1)
    nd = [1]
    while nd:
        nnd = []
        for i in nd:
            nk = k
            for i1 in to[i]:
                if fin[i1] == 0:
                    nnd.append(i1)
                else:
                    nk -= 1
                for i2 in to[i1]:
                    if i2 == i: continue
                    nk -= fin[i2]
            fin[i] = 1
            ans = ans * nk % md
        nd = nnd
    print(ans)
md=10**9+7
n,k=map(int,input().split())
f(n,k)


### FIXED CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def per(a, b):
    t = (a, b)
    if t in memo:
        return memo[t]
    re = 1
    for i in range(b):
        re = re * (a - i) % md
    memo[t] = re
    return re

def dfs(i, oi):
    cnt_ko = len(to[i])
    if i == 1:
        re = k * per(k - 1, cnt_ko) % md
    elif cnt_ko == 1:
        return 1
    else:
        re = per(k - 2, cnt_ko - 1)
    for ki in to[i]:
        if ki == oi: continue
        re = re * dfs(ki, i) % md
    return re

md = 10 ** 9 + 7
memo = {}
n, k = map(int, input().split())
to = defaultdict(list)
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a] += [b]
    to[b] += [a]
print(dfs(1, 0))
### BUGGY CODE ###

L, R = map(int, input().split())
mod = 2019
num = (R - L) + 1
ans = 10**9 + 10

for i in range(num):
    for j in range(1+i, num):
        l = L + i
        r = L + j
        if l < r:
            check = (l * r) % mod
            if ans > check:
                ans = check
        else:
            break

print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
mod = 2019
ans = 10 ** 9 * 10

for l in range(L, min(L + mod, R) + 1):
    for r in range(l + 1, min(L + mod, R) + 1):
        ans = min(ans, (l * r) % mod)

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


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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i+1],v[i+1] = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] < W2:
        return Vsum[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


### FIXED CODE ###


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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
Wmin = min(w)

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))
### BUGGY CODE ###

xs, ys, xt, yt = map(int,input().split())
N = int(input())
L = [[xs, ys, 0], [xt, yt, 0]]

for _ in range(N):
    L.append(list(map(int,input().split())))

V = N + 2
G = [[] for _ in range(N+2)]
s = 0

for i in range(N+2):
    for j in range(N+2):
        if i != j:
            G[i].append([j, max(0, ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5 - (L[i][2] + L[j][2]))])


INF = float('inf')

import heapq

def dijkstra(s):
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

d = dijkstra(0)
print(d[1])

### FIXED CODE ###

xs, ys, xt, yt = map(int,input().split())
N = int(input())
L = [[xs, ys, 0], [xt, yt, 0]]

for _ in range(N):
    L.append(list(map(int,input().split())))

V = N + 2
G = [[] for _ in range(N+2)]
s = 0

for i in range(N+2):
    for j in range(N+2):
        if i != j:
            G[i].append([j, max(0, ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5 - (L[i][2] + L[j][2]))])


INF = float('inf')

import heapq

def dijkstra(s):
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

d = dijkstra(0)
print(d[1])
### BUGGY CODE ###

import bisect

import collections


n = int(input())
a = list(map(int, input().split()))
a_counter = collections.Counter(a)
a_keys = sorted(a_counter.keys(), reverse=True)

targets = []

t = 0
vt = 1
for v in a:
    while v >= vt:
        t += 1
        vt *= 2
        targets.append(vt)
targets.reverse()


cnt = 0
for key in a_keys:
    if a_counter[key] <= 0:
        continue
    for t in targets:
        if key == t-key:
            p = max(0, min(a_counter[key], a_counter[t-key])) // 2
        else:
            p = max(0, min(a_counter[key], a_counter[t-key]))
        a_counter[key] -= p
        a_counter[t-key] -= p
        cnt += p
print(cnt)


### FIXED CODE ###

import bisect

import collections


n = int(input())
a = list(map(int, input().split()))
a_counter = collections.Counter(a)
a_keys = sorted(a_counter.keys(), reverse=True)

targets = []

t = 0
vt = 1
for v in a:
    while v >= vt:
        t += 1
        vt *= 2
        targets.append(vt)
targets.reverse()


cnt = 0
for key in a_keys:
    if a_counter[key] <= 0:
        continue
    for t in targets:
        if key >= t:
            break
        if key == t-key:
            p = max(0, min(a_counter[key], a_counter[t-key])) // 2
        else:
            p = max(0, min(a_counter[key], a_counter[t-key]))
        a_counter[key] -= p
        a_counter[t-key] -= p
        cnt += p
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9 + 7
def nCr(n, r):
    r = min(r, n-r)
    num, den = 1, 1
    for i in range(r):
        num *= (n-i)
        den *= (i+1)
    return num // den % mod

lv = 0
a.append(n+1)
ans = 1
for v in a:
    vr = v-1 - lv
    if vr < 0:
        print(0)
        exit()
    r = 0
    for i in range(vr+(-vr//2)+1):
        r += nCr(vr-i, i)
    ans = (ans * r) % mod
    lv = v+1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7
a.append(float('INF'))
a = a[::-1]
dp = [0] * (n+1)
dp[0] = 1
if a[-1] != 1:
    dp[1] = 1
else:
    a.pop()
for i in range(2, n+1):
    if i == a[-1]:
        a.pop()
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod
print(dp[n])
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

e = []
for p in P:
    e.append(sum(range(p + 1)) / p)

ans = prev = sum(e[:k])
for i in range(1, n - k + 1):
    tmp = prev - e[i - 1]+ e[i + k - 1]
    prev = tmp
    ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

m = prev = sum(P[:k])
s = 0
for i in range(1, n - k + 1):
    tmp = prev - P[i - 1]+ P[i + k - 1]
    prev = tmp
    if tmp > m:
        s = i
    m = max(tmp, m)

ans = 0
d = dict()
for i in range(s, s + k):
    p = P[i]
    if p not in d.keys():
        tmp = sum(range(p + 1)) / p
        ans += tmp
        d[p] = tmp
    else:
        ans += d[p]
print(ans)
### BUGGY CODE ###

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]
E = []
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    E.append((fr, to, -(c - P)))
    edges[fr].append(to)
    edgesR[to].append(fr)

def dfs(edges, s):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        for to in edges[st.pop()]:
            if not visited[to]:
                st.append(to)
                visited[to] = True
    return visited

canGo = dfs(edges, 0)
canBack = dfs(edgesR, N - 1)

minDist = [10**18] * N
minDist[0] = 0
for i in range(N + 1):
    for fr, to, c in E:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N and canGo[fr] and canBack[to]:
                print('-1')
                exit()
            minDist[to] = d

print(max(0, -minDist[N - 1]))


### FIXED CODE ###

N, M, P = map(int, input().split())
INF = 10**18

edges = []
E = [[] for _ in range(N)]
R = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    E[fr].append(to)
    R[to].append(fr)

def existsPath(s, edges):
    visited = [False] * N
    visited[s] = True
    st = [s]
    while st:
        now = st.pop()
        for to in edges[now]:
            if visited[to]:
                continue
            st.append(to)
            visited[to] = True
    return visited

canGoFrom1 = existsPath(0, E)
canGoFromN = existsPath(N - 1, R)

minDist = [INF] * N
minDist[0] = 0
for i in range(N):
    for fr, to, c in edges:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N - 1 and canGoFrom1[fr] and canGoFromN[to]:
                print('-1')
                exit()
            minDist[to] = d

print(max(0, -minDist[N - 1]))
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    s = 0
    for i in a:
        s ^= (i%2)
    if s:
        print("NO")
    else:
        print("YES")
    return

#B
def B():
    n = I()
    a = LI()
    while sum(a) != 0:
        b = [0]*2*n
        f = [0]*2*n
        for i in range(n):
            if a[i-1] >= a[i]:
                b[i] += 1
                b[i+n] -= 1
                f[i] += 1
                f[i+n] -= 1+n
        for i in range(2*n-1):
            b[i+1] += b[i]
            f[i+1] += f[i]+b[i]
        for i in range(n):
            f[i] += f[i+n]
            a[i] -= f[i]
            if a[i] < 0:
                print("NO")
                return
    print("YES")
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    s = 0
    for i in a:
        s ^= (i%2)
    if s:
        print("NO")
    else:
        print("YES")
    return

#B
def B():
    n = I()
    a = LI()
    m = n*(n+1)>>1
    s = sum(a)
    if s%m:
        print("NO")
        return
    k = s//m
    b = [k+a[i-1]-a[i] for i in range(n)]
    s = 0
    for i in b:
        if i%n or i < 0:
            print("NO")
            return
        s += i//n
    if s == k:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    A = NLI()
    F = NLI()
    A.sort()
    ok = 10**13
    ng = 0
    for i in range(100):
        mid = (ok+ng) // 2
        limits = [mid//f for f in F]
        limits.sort()
        ks = [max(a-l, 0) for a, l in zip(A, limits)]
        if sum(ks) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, K = NMI()
    A = NLI()
    F = NLI()
    A.sort()
    F.sort(reverse=True)
    ok = 10**13
    ng = 0
    for i in range(100):
        mid = (ok+ng) // 2
        limits = [mid//f for f in F]
        ks = [max(a-l, 0) for a, l in zip(A, limits)]
        if sum(ks) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


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

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

l=[]
d=collections.Counter(a)
count=0

for i in list(set(a)):
    c=0
    d[i]-=1
    if d[i]==0:
        del d[i]
    for j in range(1,math.floor(math.sqrt(i))+1):
        if i%j==0:
            if j in d:
                c=1
                break
            if i%(i//j)==0:
                if (i//j) in d:
                    c=1
                    break
    
    if c==0:
        count+=1
    if i not in d:
        d[i]=1
    else:
        d[i]+=1
print(count)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
am = a[-1]+1
b = [0]*am
for i in a:
    b[i]+=1
    if b[i]==1:
        for j in range(i*2,am,i):
            b[j]=2
print(b.count(1))
### BUGGY CODE ###

N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
for _ in range(M):
    if m!=[]:
        tmp=max(m)[0]
        m=[l for l in m if l[1]<=tmp]
        p+=1
    else:
        break
print(p)

### FIXED CODE ###

N, M = map(int,input().split())
m=[list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))
### BUGGY CODE ###

n = int(input())
a_inputs = [int(input()) for i in range(n)]

ans_li = [max(a_inputs[0:max(i,0)]+a_inputs[min(i+1,n):n]) for i in range(n)]

for ans in ans_li:
    print(ans)

### FIXED CODE ###

n = int(input())
a_inputs = [int(input()) for i in range(n)]

max_a = max(a_inputs)
max_index = a_inputs.index(max(a_inputs))
next_max = sorted(a_inputs)[-2]

for i in range(n):
    if i==max_index:
        print(next_max)
    else:
        print(max_a)