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

import numpy as np
_N, _M = input().split()
N, M = int(_N), int(_M)
A = np.array(list(map(int,input().split())))

for i in range(M):
  A[A.argmax()] = np.max(A)//2
print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())

A = list(map(int,input().split()))
H = []
for i in A:
  heapq.heappush(H, -int(i))
for i in range(M):
  a = heapq.heappop(H)
  heapq.heappush(H, -(-a//2))
print(-sum(H))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
for i in range(N):
  m = max(d.keys())
  if rest < d[m]:
    res += rest*m
    break
  else:
    res += d[m]*m
    rest -= d[m]
    del d[m]
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
d2 = sorted([x for x in d.keys()],reverse=True)
for m in d2:
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
print(res)
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array([list(map(int,list(input()))) for _ in range(H)],"uint8").T

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)#横に切った回数
        #print(ans)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = [0]*len(M)
        #print(D)
        for s in S:
            for k, m in enumerate(M):
                D[k] += np.sum(s[i] for i in m)
                #print("D",D)
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
    c.append([int(j) for j in input().split()])
 
nums = range(1, m + 1)
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[c[i][1]-1]) - int(retsu[c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

### FIXED CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
  A, B, C, D = map(int, input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[b[i]-1]) - int(retsu[a[i]-1]) == c[i]:
            tmp = tmp + d[i]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)
### BUGGY CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2



print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[[int(i) for i in input().split()] for i in range(m)]
data.sort(key=lambda x:x[1])
data.reverse()
a.sort()
a.reverse()
ans=0
flag=True
for i in range(n):
  if data[0][1]<a[0] or flag==False:
    ans+=a[0]
    a=a[1:]
  else:
    ans+=data[0][1]
    data[0][0]-=1
    if data[0][0]==0:
      if len(data)>1:
        data=data[1:]
      else:
        flag=False
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[1,int(i)] for i in input().split()]
data=[[int(i) for i in input().split()] for i in range(m)]
data.extend(a)
data.sort(key=lambda x:x[1],reverse=True)
ans=0
flag=True
index=0
while n>0:
  tmp=min(data[index][0],n)
  ans+=data[index][1]*tmp
  n-=tmp
  index+=1
print(ans)
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

for p in get_primes(10**6):
  if p > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(pfac)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    print([i-N-1 for i in range(len(conc)) if Z[i] == N])


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return m, n


def solve(s: str, t: str):

    T = len(t)
    S = len(s)
    counter = 0
    curr = 0
    head = 0
    updated = True
    while updated:
        updated = False
        for i, c in enumerate(s):
            if c == t[curr]:
                curr += 1
                updated = True
                if curr == T:
                    counter += i
                    break
        if curr == T:
            break
        else:
            counter += S
    if updated == False:
        print(-1)
    else:
        print(counter+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left
from collections import defaultdict
INF = float("inf")


def solve(s: str, t: str):

    S = len(s)
    T = len(t)
    ABC = defaultdict(list)
    for i, c in enumerate(s):
        ABC[c].append(i)

    counter = 0
    head = 0
    # print(ABC)
    for tt in t:
        if len(ABC[tt]) == 0:
            print(-1)
            return
        j = bisect_left(ABC[tt], head) % len(ABC[tt])
        counter += (ABC[tt][j]-head) % S + 1
        # print(tt, ABC[tt], j, ABC[tt][j], "head:",
        # head, ",counter:", counter, S)
        head = (ABC[tt][j]+1) % S
    print(counter)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


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

def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    return solve(i+1, m) or solve(i+1, m-A[i])

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    m = map(int, raw_input().split())

    for m_i in m:
        print "yes" if solve(0, m_i) else "no"

### FIXED CODE ###

def sequence(A, n):
    dic = {}
    
    def solve(i, m):
        if (i, m) in dic:
            return dic[(i, m)]
        if m == 0:
            dic[(i, m)] = True
        elif i >= n:
            dic[(i, m)] = False
        elif solve(i+1, m):
            dic[(i, m)] = True
        elif solve(i+1, m-A[i]):
            dic[(i, m)] = True
        else:
            dic[(i, m)] = False
        return dic[(i, m)]
    
    return solve

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    m = map(int, raw_input().split())

    solve = sequence(A, n)
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"
### BUGGY CODE ###

N,Y=map(int, input().split())
ichiman=0
gosen=0
sen=0
a=0
for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if 10000*i+5000*j+1000*k==Y and i+j+k==N:
        a=1
        ichiman=i
        gosen=j
        sen=k
        break
    if a==1:
      break
  if a==1:
    break
if a==1:
  print(str(ichiman)+' '+str(gosen)+' '+str(sen))
else:
  print('-1 -1 -1')

### FIXED CODE ###

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

for i in range(N+1):
  for j in range(N+1-i):
    if 10000*i+5000*j+1000*(N-i-j)==Y:
      print(str(i)+' '+str(j)+' '+str(N-i-j))
      exit()
        
    
print('-1 -1 -1')
### BUGGY CODE ###

def gcd(num1,num2):
    if num1 % num2 == 0:
        return num2
    return gcd(num2 , num1 % num2)

from functools import reduce

N = int(input())
gcds = []
total = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            nums = 0
            nums = gcd(i,j)
            total += gcd(nums,k)

print(total)

### FIXED CODE ###

from math import gcd

K = int(input())

memo = []
memolist = []
for i in range(1,K+1):
    if i != 1:
        memo.append(memolist)
    memolist = []
    for j in range(1,K+1):
        memolist.append(gcd(i,j))
memo.append(memolist)

result = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            result += gcd(memo[i-1][j-1],k)

print(result)
### BUGGY CODE ###

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

b=[]
for i in range(n):
  if i%2==n%2:
    b.append(A[i])
  else:
    b.insert(0,A[i])
print(*b)

### FIXED CODE ###

from collections import deque
n=int(input())
A=list(map(int,input().split()))

B=deque([])
for i in range(n):
  if i%2==n%2:
    B.append(A[i])
  else:
    B.appendleft(A[i])
print(*B)
### BUGGY CODE ###

from bisect import bisect_left,bisect
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ans=0
for i in range(30):
  a_nex=list(map(lambda x:x%2**(i+1),a))
  b_nex=list(map(lambda x:x%2**(i+1),b))
  b_nex.sort()
  l=0
  for k in a_nex:
    p=bisect_left(b_nex,2**i-k-0.1)
    q=bisect(b_nex,2*2**i-1-k)
    r=bisect_left(b_nex,3*2**i-k-0.1)
    s=bisect(b_nex,4*2**i-1-k)
    l+=q-p+r-s
  if l%2==1:
    ans+=1<<i
print(ans)   
  


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

tcount = 0
rlist = ""
llist = ""

for i in range(q):
    qret = input()
    if qret[0] == "1":
        tcount += 1
    else:
        f = qret[2]
        c = qret[4]
        if f == "1":
            if tcount % 2 == 0:
                llist = c + llist
            else:
                rlist += c
        else:
            if tcount % 2 == 0:
                rlist += c
            else:
                llist = c + llist

if tcount % 2 == 0:
    print(llist + s + rlist)
else:
    print(rlist[::-1] + s[::-1] + llist[::-1])

### FIXED CODE ###

s = input()
q = int(input())

tcount = 0
rlist = ""
llist = ""

for i in range(q):
    qret = input()
    if qret[0] == "1":
        tcount += 1
        # ans = ans[::-1]
    else:
        f = qret[2]
        c = qret[4]
        if f == "1":
            if tcount % 2 == 0:
                llist = c + llist
            else:
                rlist += c
        else:
            if tcount % 2 == 0:
                rlist += c
            else:
                llist = c + llist

if tcount % 2 == 0:
    print(llist + s + rlist)
else:
    print(rlist[::-1] + s[::-1] + llist[::-1])
### BUGGY CODE ###

ans = []
n,k = list(map(int, input().split()))
for i in range(n):
  a, b = list(map(int, input().split()))  
  ans.extend([a for _ in range(b)])
ans.sort()
print(ans[k-1])

### FIXED CODE ###

from collections import defaultdict
ans = defaultdict(int)
n,k = list(map(int, input().split()))

for i in range(n):
  a, b = list(map(int, input().split()))
  ans[a] += b

ord = 0
for key in sorted(ans.keys()):
  ord += ans[key]
  if(ord >= k):
    print(key)
    exit()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

def binbin(binn):
    return bin(binn).count("1")

def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))

def main():
    N = int(input())
    X = input().strip()

    x = int(X, 2)
    xc = binbin(x)
    for i in range(N):
        z = pow(2, N - i - 1)
        if X[i] == '0':
            if x + z == 0:
                print(0)
            else:
                print(1 + popcount((x + z) % (xc + 1)))
        else:
            if x - z == 0:
                print(0)
            else:
                print(1 + popcount((x - z) % (xc - 1)))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


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

N = int(input())

A = [None] * N
B = [None] * N
L = list(range(N))
F = [False] * N

for n in range(N):
    a, b = map(int, input().split())
    A[n] = a
    B[n] = b

P = 0
Q = 0

T = True

C    = zip(A, B, L)
C    = sorted(C, key=lambda x: [x[0], x[1]], reverse=True)
D    = zip(B, A, L)
D    = sorted(D, key=lambda x: [x[0], x[1]], reverse=True)

C_A, C_B, C_L = map(list, zip(*C))
D_B, D_A, D_L = map(list, zip(*D))

for _ in range(N):
    if T:
        for i in range(len(C_L)):
            if F[C_L[i]] == False:
                P        += C_A[i]
                F[C_L[i]] = True
                T         = False
                del C_A[i]
                del C_L[i]
                break
    else:
        for i in range(len(D_L)):
            if F[D_L[i]] == False:
                Q        += D_B[i]
                F[D_L[i]] = True
                T         = True
                del D_B[i]
                del D_L[i]
                break

print(P-Q)


### FIXED CODE ###

N = int(input())

A = [None] * N
B = [None] * N
C = [None] * N

for n in range(N):
    a, b = map(int, input().split())
    A[n] = a
    B[n] = b
    C[n] = a + b

Z = zip(A, B, C)
Z = sorted(Z, key=lambda x: [x[2]], reverse=True)

A, B, C = map(list, zip(*Z))

T = True
R = 0

for i in range(N):
    if T:
        R += A[i]
        T  = False
    else:
        R -= B[i]
        T  = True

print(R)
### BUGGY CODE ###

n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
l=len(b)
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)
    

### FIXED CODE ###

n,x,m= list(map(int, input().strip().split()))
t=0
b=[]
b.append(x)
for i in range(m+1):
        if b[-1]**2%m in b:
            b.append(b[-1]**2%m)
            break
        else:
            b.append(b[-1]**2%m)
        
l=len(b) 
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

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

import itertools
N,K = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(N)]

tup = ()
for i in range(N):
    tup += (i,)

data = list(itertools.combinations(tup,2))
ans = []

for x in range(len(data)):
    for y in range(len(data)):
        cnt = 0
        x_side = data[x]
        y_side = data[y]
        x_left = min(s[x_side[0]][0],s[x_side[1]][0])
        x_right = max(s[x_side[0]][0],s[x_side[1]][0])
        y_bottom = min(s[y_side[0]][1],s[y_side[1]][1])
        y_top = max(s[y_side[0]][1],s[y_side[1]][1])
        for i in s:
            if (x_left <= i[0] and i[0] <= x_right)and(y_bottom <= i[1] and i[1] <= y_top):
                cnt += 1
        if cnt >= K:
            ans.append((x_right-x_left)*(y_top-y_bottom))
    
        
print(min(ans))

### FIXED CODE ###

n,K = map(int,input().split())

x,y = [],[]
xx,yy = [],[]

for i in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)



xx.sort()
yy.sort()
ans = 10**20

for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]

        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]


        for k in range(n):
            for l in range(k):
                by,ty = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans,(rx-lx)*(ty-by))



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

import itertools

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

prime = prime_factorize(N)
min_cnt = 10**13
if len(prime) == 1:
    print(prime[0]-1)
else:
    for i in range(1,2 ** len(prime)-1):
        x = 1
        y = 1
        index = 0
        while index <= len(prime)-1:
            if i & 1 == 1:
                x *= prime[index] 
            else:
                y *= prime[index]
            i = i >> 1
            index += 1
        min_cnt = min(min_cnt, (x-1) + (y-1))
    print(min_cnt)




### FIXED CODE ###

N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

min_cnt = 10**13
divisor = make_divisors(N)

for i in range(len(divisor)):
    b = N // divisor[i]
    min_cnt = min(min_cnt, (divisor[i]-1 + b-1))
print(min_cnt)