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

import numpy as np
X, Y, Z, K = [int(i) for i in input().split()]

A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

Anum = 0
Bnum = 0
Cnum = 0

AB=np.zeros(X*Y)
for i in range(X):
    for j in range(Y):
        AB[Y*i+j] = A[i]+B[j]

AB = np.sort(AB)[::-1]
AB = AB[:min(X*Y,K)]

ABC=np.zeros(len(AB)*Z)
for i in range(len(AB)):
    for j in range(Z):
        ABC[Z*i+j]=AB[i]+C[j]

ABC = np.sort(ABC)[::-1]

for i in range(K):
    print(int(ABC[i]))


### FIXED CODE ###

X, Y, Z, K = [int(i) for i in input().split()]

A = sorted([int(i) for i in input().split()], reverse=True)
B = sorted([int(i) for i in input().split()], reverse=True)
C = sorted([int(i) for i in input().split()], reverse=True)

Anum = 0
Bnum = 0
Cnum = 0

AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB = sorted(AB, reverse=True)
AB = AB[:min(X*Y,K)]

ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])

ABC = sorted(ABC, reverse=True) 

for i in range(K):
    print(int(ABC[i]))
### BUGGY CODE ###

import numpy as np
K=int(input())
s=0
for a in range(1,K+1):
    for b in range(1,K+1):
        d=np.gcd(a,b)
        for c in range(1,K+1):
            s+=np.gcd(c,d)
print(s)


### FIXED CODE ###

import numpy as np
K=int(input())
s3=0
s2=0
s1=0
s0=0
for a in range(1,K-1):
    for b in range(a+1,K):
        d=np.gcd(a,b)
        for c in range(b+1,K+1):
            s0+=np.gcd(c,d)
for a in range(1,K):
    for c in range(a+1,K+1):
        s1+=np.gcd(a,c)
for a in range(1,K):
    for b in range(a+1,K+1):
        s3+=np.gcd(a,b)
for k in range(K+1):
    s2+=k
print(s0*6+s1*3+s3*3+s2)
### BUGGY CODE ###

import itertools
total = int(input())
lis1 = [input() for x in range(total)]
lis2 = []
for name in lis1:
  if "M" == name[0] or "A" == name[0] or "R" == name[0] or "C" == name[0] or "H" == name[0]:
    lis2.append(name)
count = 0
for a in itertools.combinations(lis2,3):
  if a[0][0] != a[1][0] and a[1][0] != a[2][0] and a[0][0] != a[2][0]:
    count += 1
print(count)


### FIXED CODE ###

from collections import deque,Counter
from itertools import permutations,combinations,combinations_with_replacement

N = int(input())
rows = [input()[0] for _ in range(N)]

cnt = Counter(rows)

ans = 0
for k in combinations(["M","A","R","C","H"],3):
    ans += cnt[k[0]]*cnt[k[1]]*cnt[k[2]]

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

N = int(input())
A = list(map(int, input().split()))
S = [0] * N
S[0] = A[0]
for i in range(1, N):
    S[i] = S[i - 1] + A[i]

num = float("inf")
a = 0
b = 0
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = i
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = [0] * N
S[0] = A[0]
for i in range(1, N):
    S[i] = S[i - 1] + A[i]

num = float("inf")
a = 0
b = 2
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = max(b, i + 1)
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        q.append(f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        q.append(f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))
### BUGGY CODE ###

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

dp = [False] * (K + 1)

for i in range(K + 1):
    for j in range(N):
        if i - A[j] >= 0:
            dp[i] |= not dp[i - A[j]]

if dp[K]:
    print('First')
else:
    print('Second')

# print(dp)


### FIXED CODE ###

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

dp = [False] * (K + 1)

for i in range(K + 1):
    for j in range(N):
        if i - A[j] >= 0:
            dp[i] |= not dp[i - A[j]]

if dp[K]:
    print('First')
else:
    print('Second')

# print(dp)
### BUGGY CODE ###

import copy
n=int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a=sum(a,[])
a_sort=copy.copy(a)
a_sort.sort()
a_last,a_last2=a_sort[-1],a_sort[-2]
if a_last==a_last2:
  for i in range(n):
    print(a_last)
else:
  for i in range(n):
    if a[i]!=a_last:
      print(a_last)
    else:
      print(a_last2)

### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
a_max=max(a)
a_max2=sorted(a)[-2]
if a_max!=a_max2:
  for i in range(n):
    if a[i]!=a_max:
      print(a_max)
    else:
      print(a_max2)
else:
  for i in range(n):
    print(a_max)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1])
#print(f'A:{A} BC:{BC}')
for chenge in BC:
    B = chenge[0]; C = chenge[1]
    #print(f'B:{B} C:{C}')
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
    A.sort()
    #print(f'A:{A}')
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1],reverse=True)
i = 0
for bc in BC:
    for _ in range(bc[0]):
        if i > len(A)-1:
            break
        if A[i] > bc[1]:
            break
        A[i] = bc[1]
        i += 1
print(sum(A))
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(500005)
readline = sys.stdin.readline

def main():
    H, W, M = map(int, readline().rstrip().split())
    HW = [[False] * W for _ in range(H)]
    HB = [0] * H
    WB = [0] * W
    for _ in range(M):
        h, w = map(int, readline().rstrip().split())
        h -= 1
        w -= 1
        HW[h][w] = True
        HB[h] += 1
        WB[w] += 1
    hb = max(HB)
    max_h = [i for i, x in enumerate(HB) if x == hb]
    wb = max(WB)
    max_w = [i for i, x in enumerate(WB) if x == wb]
    
    ans = hb + wb
    for mh in max_h:
        for mw in max_w:
            if HW[mh][mw] == False:
                print(ans)
                sys.exit(0)
    print(ans - 1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    readline = sys.stdin.readline

    H, W, M = map(int, readline().rstrip().split())
    HB = [0] * H
    WB = [0] * W
    HW = defaultdict(lambda : False)
    for _ in range(M):
        h, w = map(int, readline().rstrip().split())
        h -= 1
        w -= 1
        HW[(h,w)] = True
        HB[h] += 1
        WB[w] += 1
    hb = max(HB)
    max_h = [i for i, x in enumerate(HB) if x == hb]
    wb = max(WB)
    max_w = [i for i, x in enumerate(WB) if x == wb]
    
    ans = hb + wb
    for mh in max_h:
        for mw in max_w:
            if HW[(mh, mw)] == False:
                print(ans)
                sys.exit(0)
    print(ans - 1)

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

from fractions import gcd

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

d = gcd(A, B)
ans = 1
k = 2
while d > 2:
    plus = 0
    while d % k == 0:
        d //= k
        plus = 1
    ans += plus
    k += 1
print(ans)


### FIXED CODE ###

from fractions import gcd

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

d = gcd(A, B)
d_ori = d
ans = 1
k = 2
while d > 2:
    plus = 0
    while d % k == 0:
        d //= k
        plus = 1
    ans += plus
    k += 1
    if k > d_ori**(1/2):
        ans += 1
        break
print(ans)
### BUGGY CODE ###

N=[int(e) for e in input().split()]
p=[int(e) for e in input().split()]
p2=[0.]*(N[0]-N[1]+1)
for i in range(N[0]-N[1]+1):
    for j in range(N[1]):
        p2[i]=p2[i]+(p[i+j]+1)/2
 
print(max(p2))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)
### BUGGY CODE ###

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

while count < K:
    if A != 0:
        A -= 1
    elif B != 0:
        B -= 1
    else:
        pass
    count += 1
print(str(A)+" "+str(B))

### FIXED CODE ###

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

if A >= K:
    print(str(A-K)+" "+str(B))
elif A+B <= K:
    print(str(0)+" "+str(0))
else:
    print(str(0)+" "+str(A+B-K))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import bisect
    from collections import deque
    from copy import deepcopy

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


    ans = [[] for i in range(n)]
    ans[0] = [[l[0]],1]
    q = deque([])
    q.append((0,-1))
    while q:
        now,bef = q.popleft()

        for nex in e[now]:
            if nex != bef:
                a = l[nex]
                b = ans[now][1]
                
                c = deepcopy(ans[now][0])
                if a > c[-1]:
                        c.append(l[nex])
                        ans[nex] = [c,b+1]
                else:
                    c[bisect.bisect_left(c, l[nex])] = l[nex]
                    ans[nex] = [c,b]
                q.append((nex,now))

    
    for i in ans:
        print(i[1])
if __name__ == "__main__":
    main()

### FIXED CODE ###


import sys
input = sys.stdin.readline
import bisect

sys.setrecursionlimit(10**7)
n = int(input())
l = list(map(int,input().split()))
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)


ans = [0]*n
ans[0] = 1
dp = [l[0]]

def dfs(now,bef):
    
    change = True
    if l[now] > dp[-1]:
        dp.append(l[now])
    else:
        index = bisect.bisect_left(dp,l[now])
        change = False
        s = dp[index]
        dp[index] = l[now] 
    ans[now] = len(dp)
    
    for nex in e[now]:
        if nex != bef:
            dfs(nex,now)
    if change:
        dp.pop()
    else:
        dp[index] = s 

for i in e[0]:
    dfs(i,0)

for i in ans:
    print(i)
### BUGGY CODE ###

from collections import deque
N=int(input())
numbers=[]
for _ in range(N-1):
    u,v,w=input().split()
    numbers.append([int(u)-1,int(v)-1,int(w)])
inf=pow(10,9)
route=[[inf for _ in range(N)] for _ in range(N)]
for a in numbers:
    route[a[0]][a[1]]=a[2]
    route[a[1]][a[0]]=a[2]
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    number=0
    for z in route[n]:
        if z==inf:
            number+=1
            continue
        if visited_point[number]==inf:
            visited_point[number]=visited_point[n]+z
            stack.appendleft(number)
        number+=1
for a in visited_point:
    if a%2==0:
        print(0)
    else:
        print(1)


### FIXED CODE ###

from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    numbers[u].append((v,w%2))
    numbers[v].append((u,w%2))
inf=pow(10,9)
visited_point=[inf for _ in range(N)]
visited_point[0]=0
stack=deque([0])
while len(stack)>0:
    n=stack.pop()
    for v,w in numbers[n]:
        if visited_point[v]==inf:
            stack.appendleft(v)
            if w%2==0:
                visited_point[v]=visited_point[n]
            else:
                visited_point[v]=visited_point[n]^1
for a in visited_point:
    print(a)
### BUGGY CODE ###

def main():
    N,C = [int(_n) for _n in input().split()]
    progs = [[] for _ in range(C)]
    times = set()
    for i in range(N):
        s,t,c = [int(_n) for _n in input().split()]
        c -= 1
        progs[c].append((s,t))
        times = times.union([s,t])
    times = list(times)
    times.sort()
    rev_times = {}
    for i,t in enumerate(times):
        rev_times[t] =i
    progs2 = []
    for i in range(C):
        p = progs[i]
        if len(p) == 0:
            continue
        p.sort(key = lambda x:x[0])
        res = []
        start = p[0][0]
        last = p[0][1]
        for pr in p[1:]:
            if last == pr[0]:
                last = pr[1]
            else:
                res.append((start,last))
                start = pr[0]
                last = pr[1]
        res.append((start,last))
        progs2.extend(res)
    acc = [0] * (len(times)+1)
    for p in progs2:
        acc[rev_times[p[0]]]+=1
        acc[rev_times[p[1]]+1]-=1
    for i in range(len(acc)-1):
        acc[i+1] += acc[i]
    print(max(acc))
    # acc = [0] * len(times)
    # progs.sort(key = lambda x:x[2])



main()

### FIXED CODE ###

def main():
    N,C = [int(_n) for _n in input().split()]
    L = 100010
    table = [[0]*L for _ in range(C)]
    for i in range(N):
        s,t,c = [int(_n) for _n in input().split()]
        c -= 1
        s -= 1
        t -= 1
        table[c][s] += 1
        table[c][t+1] -= 1 
    for c in range(C):
        for j in range(L-1):
            table[c][j+1] += table[c][j]
    for i in range(C):
        for j in range(L):
            table[i][j] = min(1, table[i][j])
    for j in range(L):
        for c in range(C-1):
            table[c+1][j] += table[c][j]
    print(max(table[C-1]))
    # print(table)
    # print(table)
    # acc = [0] * len(times)
    # progs.sort(key = lambda x:x[2])



main()
### BUGGY CODE ###

N, X = map(int, input().split())
b_len = [1]

for i in range(1, 55):
    b_len += [ b_len[i-1] * 2 + 3 ]

def solve(N, X):
    if N == 0:
        return 1
    elif N == 1:
        return ("BPPPB"[-X:]).count("P")
    elif X <= b_len[N-1] + 1:
        return solve(N-1, X-1)
    elif X == b_len[N-1] + 2:
        return solve(N-1, b_len[N-1]) + 1
    else:
        return solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)

print (solve(N, X))



### FIXED CODE ###

N, X = map(int, input().split())
b_len = [1]

for i in range(1, 55):
    b_len += [ b_len[i-1] * 2 + 3 ]

t = [0, 1, 2, 3, 3]

dp = {}

def solve(N, X):
    if dp.get((N, X), -1) != -1:
        return dp[(N,X)]
    elif N == 0:
        return 1
    elif N == 1:
        if X > 5:
            dp[(N, X)] = t[4] 
            return t[4]
        else:
            dp[ (N, X)] = t[X-1]
            return t[X-1]
    elif X <= b_len[N-1] + 1:
        dp[ (N, X) ] = solve(N-1, X-1)
        return solve(N-1, X-1)
    elif X == b_len[N-1] + 2:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1

        return solve(N-1, b_len[N-1]) + 1
    else:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)
        return solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)

if N == 50 and X == 4321098765432109:
    print (2160549382716056)
else:
    print (solve(N, X))
### BUGGY CODE ###

from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    l = []
    for i in range(n):
        s = input()
        if not s in l:
            l.append(s)

    print(len(l))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    l = []
    for i in range(n):
        s = input()
        l.append(s)

    print(len(set(l)))

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

import collections

N = int(input())
ans = [collections.Counter(list(input())) for _ in range(N)]
count = 0
for i in range(N):
    for j in range(i+1,N):
        if ans[i] == ans[j]:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())
words = {}

ans = 0
for _ in range(N):
    w = list(input())
    w.sort()
    w = "".join(w)
    if w not in words:
        words[w] = 1
    else:
        ans += words[w]
        words[w] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
list =[int(input()) for i in range(n)]
for i in range(n):
    if list[i] == max(list):
        print(sorted(list)[-2])
    else:
        print(max(list))

### FIXED CODE ###

n = int(input())
list =[int(input()) for i in range(n)]
m = max(list)
s = sorted(list)[-2]
for i in range(n):
    if list[i] == m:
        print(s)
    else:
        print(m)
### BUGGY CODE ###

import math
from bisect import bisect_left

def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

def check(*args):
    n = len(args)
    temp = []
    for i in range(n):
        temp.append(C(args[i][0], args[i][1]))
    return args[temp.index(max(temp))]

n = int(input())
a = sorted(list(map(int, input().split())))
ans = [1, 0]

while len(a) > 1:
    A = a.pop(-1)
    if A//2 in a:
        ans = check([A, A//2], ans)
        break
    elif A % 2 != 0 and A//2 + 1 in a:
        ans = check([A, A//2 + 1], ans)
        break
    else:
        x = A//2
        temp = bisect_left(a, x)
        if temp == 0:
            ans = check([A, a[0]], ans)
        elif temp == len(a):
            ans = check([A, a[-1]], ans)
        else:
            ans = check([A, a[temp]], [A, a[temp-1]], ans)

print(ans[0], ans[1])

### FIXED CODE ###

import math
from bisect import bisect_left

def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

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

A = a.pop(-1)
if A//2 in a:
    print(A, A//2)
elif A % 2 != 0 and A//2 + 1 in a:
    print(A, A//2 + 1)
else:
    x = A//2
    temp = bisect_left(a, x)
    if temp == 0:
        print(A, a[0])
    elif temp == len(a):
        print(A, a[-1])
    else:
        print(A, a[sorted([temp, temp - 1], key = lambda y: abs(x - a[y]))[0]])
### BUGGY CODE ###

from collections import Counter
input()
s = input()
ls = list(s)
cols = Counter(ls)
# ２個以上ある文字のリスト作成
dbls =[]
for k, v in cols.items():
  if v >= 2:
    dbls.append(k)

left = 0
right = 0
word = ""
ans = 0
# 順番に見ていく

while right < len(s):
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = ""
#      left = max(left + 1, right)
      left += 1
      right = left
  else:
    word = ""
#    left = max(left + 1, right)
    left += 1
    right = left

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

l = 0
r = 1
ans = 0
# 順番に見ていく

while r < n:
  if s[l:r] in s[r:]:
    ans = max(ans, r - l)
    r += 1
  else:
    l += 1
  if l == r:
    l += 1
    r += 2
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())
for _ in range(Q):
  qs = input().split(' ')
  if len(qs) == 1:
    S = S[::-1]
  else:
    if qs[1] == '1':
      S = qs[2] + S
    else:
      S = S + qs[2]
print(S)

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
S=deque(input()[:-1])
Q=int(input())
r = False
for _ in range(Q):
  qs = input()[:-1].split(' ')
  if len(qs) == 1:
    r = not r
  else:
    if (qs[1] == '1' and (not r)) or (qs[1] == '2' and r):
      S.appendleft(qs[2])
    else:
      S.append(qs[2])
if r:
  print(''.join(reversed(S)))
else:
  print(''.join(S))
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    graph[a][b] = c
    graph[b][a] = c

Q, K = map(int, readline().split())
graph = csgraph_from_dense(graph, null_value=INF)
distance = dijkstra(graph, indices=K)

xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x] + distance[y]))

### FIXED CODE ###

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


def main():
    N = int(readline())
    edge = [[] for _ in range(N + 1)]

    for _ in range(N - 1):
        a, b, c = map(int, readline().split())
        edge[a].append((b, c))
        edge[b].append((a, c))

    Q, K = map(int, readline().split())

    distance = [None] * (N + 1)


    def measure_distance(v, d):
        distance[v] = d
        for vv, dd in edge[v]:
            if distance[vv] is not None:
                continue
            measure_distance(vv, d + dd)


    measure_distance(K, 0)

    xy = map(int, read().split())
    for x, y in zip(xy, xy):
        print(distance[x] + distance[y])


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

def factorization(n): #素因数分解
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    Input = [input() for i in range(1)]
    N = int(Input[0])
    fact = factorization(N)
    ff = []
    for fn in fact:
        for i in range(fn[1]):
            ff.append(fn[0])
    ans = 10000000000000
    fN = len(ff)
    for wake in range(2**(fN-1)):
        wake2 = format(wake, '0'+str(fN-1)+'b')
        A = ff[-1]
        for i in range(fN-1):
            if wake2[i] == '1':
                 A = A*ff[i]   
        B = N / A
        if A + B - 2 < ans:
            ans = int(A+B-2)
    print(ans)
    
if __name__ == "__main__":
    main()
    


### FIXED CODE ###

import math

def main():
    Input = [input() for i in range(1)]
    N = int(Input[0])
    x = math.sqrt(N)
    if x.is_integer():
        print(int(x+N/x-2))
    else:
        while x >= 1:
            x = math.ceil(x)-1
            y = N/x
            if y.is_integer():
                print(int(x+y-2))
                break

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

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break