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

N,M,K=map(int,input().split())
A,B=[0],[0]
A+=map(int,input().split())
B+=map(int,input().split())

for i in range(1,N+1):
    A[i]+=A[i-1]
for i in range(1,M+1):
    B[i]+=B[i-1]

ans=0
for i in range(N+1):
    if A[i]>K:
        break
    for j in range(M+1):
        if A[i]+B[j]>K:
            break
        ans=max(ans,i+j)

print(ans)


### FIXED CODE ###

N,M,K=map(int,input().split())
A,B=[0],[0]
A+=map(int,input().split())
B+=map(int,input().split())

for i in range(1,N+1):
    A[i]+=A[i-1]
for i in range(1,M+1):
    B[i]+=B[i-1]

ans,j=0,M
for i in range(N+1):
    if A[i]>K:
        break
    while j>0 and A[i]+B[j]>K:
        j-=1
    ans=max(ans,i+j)

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

R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])

count=0
for i in range(N//C[2]+1):
	if(N-C[2]*i>=0):
		for j in range(N//C[1]+1):
			if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
				count+=1
print(count)




### FIXED CODE ###



R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = {}
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans[i] = count
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f in primes:
            primes[f] = max(primes[f], factors[f])
        else:
            primes[f] = factors[f]

ans = 0
for a in A:
    factors = factorization(a)
    tmp = 1
    for p in primes:
        if p in factors:
            tmp *= modpow(p, (primes[p] - factors[p]))
        else:
            tmp *= modpow(p, primes[p])
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


mod = 10 ** 9 + 7
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a

print(ans % mod)
### BUGGY CODE ###

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N] % 998244353)


### FIXED CODE ###

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]


mod = 998244353
dp = [0] * (N + 1)
dpsum = [0] * (N + 1)
dp[1] = 1
dpsum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - LR[j][1], 1)
        ri = i - LR[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li - 1]
        dp[i] %= mod
    dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[N])
### BUGGY CODE ###

N, Q = input().split()
S = input()
for i in range(int(Q)):
    str_l, str_r = input().split()
    l = int(str_l)
    r = int(str_r)
    count = 0
    for j in range(0, r - l, 1):
        if 'A' == S[j+l-1]:
            if 'C' == S[j+l]:
                count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

AC_appearance = [0] * len(S)
counter = 0
for i in range(1, len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        counter += 1
    AC_appearance[i] = counter 

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


N,K = map(int,input().split())
P_List=list(map(int,input().split()))
#print(N,K)
#print(P_List)

def Kitaichi(p):
    result = 0
    for i in range(p):
        result += (i+1)*1/p
    #print(p,result)
    return result

pre_max=0
temp_max=0
max_num=0
for j in range(N-(K-1)):
    for k in range(K):
        temp_max += P_List[j+k]
    #print(temp_max)

    if pre_max < temp_max:
        pre_max = temp_max
        max_num = j
    temp_max=0

#print('max_num:',max_num)
result = 0
for l in range(K):
    result += Kitaichi(P_List[max_num+l])

print(result)

### FIXED CODE ###


N,K = map(int,input().split())
P_List=list(map(int,input().split()))
#print(N,K)
#print(P_List)

def Kitaichi(p):
    result = 0
    for i in range(p):
        result += (i+1)*1/p
    #print(p,result)
    return result

def Kitaichi2(p):
    return (p+1)*0.5

kitaichi_list=[]
ruisekiwa_list=[]
ruisekiwa=0
for a in range(N):
    kitaichi_list.append(Kitaichi2(P_List[a]))
    ruisekiwa += Kitaichi2(P_List[a])
    ruisekiwa_list.append(ruisekiwa)

#print(kitaichi_list)
#print(ruisekiwa_list)
pre_max=0
temp_max=0
max_num=0
for j in range(N-(K-1)):
    if j == 0:
        temp_max = ruisekiwa_list[j+K-1] - 0
    else:
        temp_max = ruisekiwa_list[j+K-1] - ruisekiwa_list[j-1]
    

    if pre_max < temp_max:
        pre_max = temp_max
    temp_max=0

print(pre_max)
### BUGGY CODE ###

from sys import stdin
from functools import reduce 

# 標準入力から読み込み
inputs = [list(map(int, input().split())) for _ in range(2)]
inputs = inputs[1]

output = 0 if (0 in inputs) else reduce((lambda x, y: x * y), inputs)
if output > 1e18:
  output = -1

print(output)

### FIXED CODE ###

from sys import stdin
from functools import reduce 

# 標準入力から読み込み
inputs = [list(map(int, input().split())) for _ in range(2)]
inputs = inputs[1]

if (0 in inputs):
  output = 0
else:
  output = reduce((lambda x, y: -1 if (x * y) > 1e18 or x < 0 or y < 0  else (x * y)), inputs)

print(output)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0
for i, l1 in enumerate(L):
    for j, l2 in enumerate(L[i + 1:]):
        for k, l3 in enumerate(L[i + j + 2:]):
            if (l1 < l2 + l3) and (l2 < l3 + l1) and (l3 < l1 + l2):
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
Lb = L[::-1]
ans = 0
for i, l1 in enumerate(L):
    for j, l2 in enumerate(L[i + 1:]):
        c = l1 - l2
        p = max(0, len(L) - (i + j + 2) - bisect.bisect_right(Lb, c))
        ans += p
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0] * (c3 + 1) for _ in range(c2 + c3 + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])


### FIXED CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

N = int(sys.stdin.readline())

A = sys.stdin.readline().split(' ')

for rem in range(len(A)):
	pay = 0
	B = []
	for i in range(len(A)):
		if i != rem:
			B.append(int(A[i]))

	for i in range(len(B)):

		a = B[i]
		s = B[i - 1] if i > 0 else 0

		l = a - s
		pay += l if l > 0 else -l

	lastPoint = B[len(B) - 1]
	pay += lastPoint if lastPoint > 0 else -lastPoint

	print(pay)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

N = int(sys.stdin.readline())

A = sys.stdin.readline().split(' ')

A = [int(x) for x in A]

A.insert(0, 0)
A.append(0)

total = 0

for i in range(N + 1):
	total += abs(A[i] - A[i+1])

for i in range(1, N + 1):
	print(str(total - abs(A[i] - A[i + 1]) - abs(A[i] - A[i - 1]) + abs(A[i -1] - A[i + 1])))
### BUGGY CODE ###

# E - Flatten
# https://atcoder.jp/contests/abc152/tasks/abc152_e

from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
            tmp %= MODE
        ret += tmp

    print(ret%MODE)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions 

N = int(input())
A = list(map(int, input().split()))
MODE = 10**9+7

def lcm(a, b):
    return a*b//fractions.gcd(a,b)

_lcm = 1
for a in A:
    _lcm = lcm(a, _lcm)

ret = 0
for a in A:
    ret += (_lcm // a)

print(ret%MODE)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
from functools import reduce

def solve(K: int):
    K += 1
    ans = []
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                ans.append(gcd(i, gcd(j, k)))
    print(sum(ans))
    return

def gcd(x: int, y: int):
    """xとyの最大公約数を求める"""
    return gcd(y, x % y) if y else x
    
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
from functools import reduce

def solve(K: int):
    K += 1
    ans = []
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                ans.append(gcd(i, gcd(j, k)))
    print(sum(ans))
    return

def gcd(x: int, y: int):
    """xとyの最大公約数を求める"""
    return gcd(y, x % y) if y else x
    
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

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

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

for i in range(m):
    [b, c] = [int(i) for i in input().split()]
    a += [c for i in range(b)]

a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
l = [[int(j) for j in input().split()] for i in range(m)]
l.sort(reverse=True, key=lambda x:x[1])

k = []
for i in l:
    k += [i[1]] * i[0]
    if (len(k) >= n):
        break

k += a
k.sort(reverse = True)
print(sum(k[:n]))
### BUGGY CODE ###

#155 Poll
import collections
n = int(input())
ans = []
for i in range(n):
    ans.append(input())

c = collections.Counter(ans)
max_k_list = [kv[0] for kv in c.items() if kv[1] == max(c.values())]
max_k_list.sort()
print('\n'.join(max_k_list))

### FIXED CODE ###

#155 Poll
n = int(input())
words = {}
for i in range(n):
    name = input()
    if name not in words:
        words[name] = 1
    elif name in words:
        words[name] += 1

num = max(words.values())
max_k_list = [kv[0] for kv in words.items() if kv[1] == num]
max_k_list.sort()
print('\n'.join(max_k_list))
### BUGGY CODE ###

def fct(n):
	v = 1
	for i in range(1, n+1):
		v = v*i
	return v
N, M = map(int, input().split())
ans = 0
if N == M:
	v = fct(N)
	ans = (v*v*2)%1000000007
elif abs(N-M) == 1:
	ans = (fct(N)*fct(M))%1000000007
print(ans)

### FIXED CODE ###

def fct(n):
	v = 1
	for i in range(1, n+1):
		v = (v * i) % 1000000007
	return v
N, M = map(int, input().split())
ans = 0
if N == M:
	v = fct(N)
	ans = (v*v*2)%1000000007
elif abs(N-M) == 1:
	ans = (fct(N)*fct(M))%1000000007
print(ans)
### BUGGY CODE ###

#input
X = int(input())

#output
initial_num = 1

left = 1
right = 10**2
while left + 1 < right:
    mid = (left + right)//2
    if mid **5  > X:
        right = mid
    else:
        left = mid

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
A = left
C = A**5 -X

if C >= 0:
    B = pow(C, 1/5)
else:
    B = -pow(-C, 1/5)

while not is_integer(B):
    A -= 1
    C = A**5 - X
    if C >= 0:
        B = pow(C, 1/5)
    else:
        B = -pow(-C, 1/5)

print(A, int(B))

### FIXED CODE ###

#input
X = int(input())

#output
for a in range(200):
    for b in range(-200, 200):
        if a**5 - b**5 == X:
            print(a, b)
            exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
read = sys.stdin.read
import numpy as np

n, x = map(int, input().split())
BLU = np.array(read().split(), dtype=np.int64).reshape(n, 3)
B, L, U = BLU.T
S = B*L + (x-B)*U
idx = np.argsort(S)[::-1]
S = S[idx]
B = B[idx]
L = L[idx]
U = U[idx]
M = (B*L).sum()

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False

ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

### FIXED CODE ###

"""

重要度はlかuしかとらないと考えてよい
高橋君のほうが青木君より低い点数を取ると決めた科目に対してはl、それ以外はuと定める
それぞれのテストの点数の差をdとして、Σ[a>=b](d*u) - Σ[a<b](d*l) >= 0 を満たす
最小のΣaを求める
→各iについて、biまではli個ずつ減らすことができ、それより多く減らす場合はXを超えない範囲で
 ui個ずつ減らすことができる
→heapqでできそう
 単純なheapqだと、例えば一つのテストの中でlとuの値の差がとても大きい時に
 正しい答えが出せない
→二分探索

"""
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
SBLU = sorted([(b*l+(x-b)*u, b, l, u) for b, l, u in BLU], reverse=True)
S, B, L, U = zip(*SBLU)
M = sum([b*l for b, l, u in BLU])

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False


ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
num_list = []
for i in range(1, N+1):
    c = A.count(i)
    num_list.append(int(c * (c - 1) / 2))
for j in A:
    if num_list[j-1] == 0:
        print(sum(num_list))
    else:
        print(sum(num_list) - (A.count(j) - 1))

### FIXED CODE ###

'''
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')
'''
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
total = 0
for key in cnt.keys():
    total += cnt[key] * (cnt[key] - 1) // 2
for i in range(N):
    tmp = total
    tmp -= cnt[A[i]] * (cnt[A[i]] - 1) // 2
    tmp += (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
    print(tmp)
### BUGGY CODE ###

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

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

ret = [0] * p
fac = [1]
inv = [1]
power = [0] * p
for i in range(1, p) :
    fac.append(fac[-1] * i % p)
    inv.append(pow(fac[-1], p - 2, p))

for i in range(p) :
    if a[i] == 0 :
        continue
    ret[0] += 1
    for j in range(p) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*pow(-i, p-1-j, p)%p
        ret[j] %= p

print(' '.join(map(str, ret)))

### FIXED CODE ###

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

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

ret = [0] * p
fac = [1]
inv = [1]
for i in range(1, p) :
    fac.append(fac[-1] * i % p)
    inv.append(pow(fac[-1], p - 2, p))

for i in range(p) :
    if a[i] == 0 :
        continue
    ret[0] += 1
    power = 1
    for j in range(p-1, -1, -1) :
        ret[j] += -fac[p-1]*inv[p-1-j]*inv[j]*power%p
        ret[j] %= p
        power *= -i
        power %= p
print(' '.join(map(str, ret)))
### BUGGY CODE ###

import copy
import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(n):
    ac=copy.deepcopy(A)
    del ac[i]
    ak=collections.Counter(ac)
    aj=list( ak.values() )
    s=0
    for j in range(len(aj)):
        s=s+com(aj[j],2)
    res[i]=s
print(' '.join(map(str,res)))
    

### FIXED CODE ###

import math
n=int(input())
A = list(map(int, input().split()))
res=[0]*n
import collections
def com(n, r):
    if n<r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

af=collections.Counter(A)
res2=list(af.items())
res3=[0]*n
s=0
for i in range(0,len(res2)):
    s=s+com(res2[i][1],2)
for j in range(0,len(res2)):
    res3[res2[j][0]-1]=s-res2[j][1]+1
for i in range(n):
    res[i]=res3[A[i]-1]

for j in range(n):
    print(res[j])
### BUGGY CODE ###

H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 6
for i in range(2 ** (H - 1)):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1


    ans = min(cand,ans)
print(ans)




### FIXED CODE ###

H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 10
for i in range(2 ** (H )):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1
    ss = []
    for i in range(len(cuts) - 1):  # 広げたら超えてしまっていたら、その一個前で線を引く
        y1 = cuts[i]
        y2 = cuts[i + 1]
        x2 = W
        x1 = beforeW
        s = ruiseki_2d[y2][x2] - ruiseki_2d[y2][x1] - ruiseki_2d[y1][x2] + ruiseki_2d[y1][x1]
        ss.append(s)


    if max(ss) <= K :
        ans = min(cand,ans)
# if ruiseki_2d[-1][-1] <= K:
#     ans = 0
print(ans)
### BUGGY CODE ###

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

seki_list = [0]*n
seki = 1
temp = 0

for i in range(n):
    seki *= A[i]
    seki_list[i] = seki

point = seki_list[k-1]

for i in range(k, n):
    temp = seki_list[i]/seki_list[i-k]
    if temp > point:
        print("Yes")
        point = temp
    else:
        print("No")
        point = temp


### FIXED CODE ###

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

for i in range(k,n):
    if A[i] > A[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

ans = 0
for i in range(60 + 1):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    ans = (ans + 2 ** i * cnt * (N - cnt)) % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(60 + 1):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    ans = (ans + 2 ** i * cnt * (N - cnt)) % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

import itertools
import numpy as np
N = int(input())

def factorization(n):
    res = []
    x = N
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)

    return res

ns = factorization(N)

ans = 10**12 + 1
for i in range(1, len(ns)+1):
    for j in itertools.combinations(ns, i):
        val1 = np.prod(j)
        val2 = N // val1
        ans = min(ans, val1+val2-2)

print(ans)



### FIXED CODE ###

import math
def solve():
    N = int(input())

    ans = 10**12 + 1
    s = int(math.sqrt(N))
    for i in range(1, s+1):
        if N % i == 0:
            val1 = i
            val2 = N // val1
            ans = min(ans, val1+val2-2)
    print(ans)

solve()