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

import sys
import numpy as np
from numba import njit

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,unicode_type,i8[:,:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = input()#np.array([ord(_) for _ in input()])
    dp = np.zeros((N + 1, N + 1), dtype=int)
    print(main(N, S, dp))


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
### BUGGY CODE ###

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


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


count = (2 ** N) - 1
count -= cmb(N, A)
count -= cmb(N, B) 
print(count % (10 ** 9 + 7))


### FIXED CODE ###

N, A, B = map(int, input().split())
MAX = max(A, B) + 1
MOD = 1000000007
nCk = [0] * MAX
nCk[0] = 0
nCk[1] = N


def mod_pow(a, n, m):
    res = 1
    while n != 0:
        if n & 1:
            res = (res * a) % m
        n = n >> 1
        a = (a * a) % m
    return res


def mod_inv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


for i in range(2, MAX):
    nCk[i] = (nCk[i-1] * ((N-i+1) * mod_inv(i, MOD))) % MOD

count = (mod_pow(2, N, MOD) - 1 - nCk[A] - nCk[B]) % MOD
print(int(count))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read

MOD = 998244353
 
N, S, *As = map(int, read().split())
import copy
answer = 0
f = [0]*3010
for A in As:
    c = copy.deepcopy(f)
    t = [0]*A
    f = t+c
    f = f[:-A]
    f = [x+y for x,y in zip(f,c)]
    f[0] += 1
    f[A] += 1
    #f %= MOD
    answer += f[S]

answer %= MOD
print(answer)

### FIXED CODE ###

def main():
  import sys
  read = sys.stdin.buffer.read
  r = 998244353
  U, S, *A = map(int, read().split())
  import copy
  ans = 0
  f = [0]*3010
  for a in A:
      c = copy.copy(f)
      f = [0]*a+c[:-a]
      f = [x+y for x,y in zip(f,c)]
      f[0] += 1
      f[a] += 1
      ans += f[S]
  ans %= r
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

######### D 
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))
    
walk = [(0,1),(1,0),(0,-1),(-1,0)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]

q = deque()
q.append((Ch,Cw))
num = 0
meiro[Ch][Cw] = num


while q != deque():
#for _ in range(10):
    ph, pw = q.popleft()
    
    if meiro[ph][pw] != num:
        num += 1
    
    for h, w in walk:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] != '#' and meiro[th][tw] != meiro[ph][pw]:
            meiro[th][tw] = meiro[ph][pw]
            q.appendleft((th,tw))
    
    for h, w in warp:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] == '.':
            meiro[th][tw] = meiro[ph][pw] + 1
            q.append((th,tw))
    
if meiro[Dh][Dw] == '.':
    print(-1)
else:
    print(meiro[Dh][Dw])

### FIXED CODE ###

######### D 
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))
    
walk = [(0,1),(1,0),(0,-1),(-1,0)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]

q = deque()
q.append((Ch,Cw))
num = 0
meiro[Ch][Cw] = num


while q != deque():
#for _ in range(10):
    ph, pw = q.popleft()
    
    if meiro[ph][pw] != num:
        num += 1
    
    for h, w in walk:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] != '#' and meiro[th][tw] != meiro[ph][pw]:
            meiro[th][tw] = meiro[ph][pw]
            q.appendleft((th,tw))
    
    for h, w in warp:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] == '.':
            meiro[th][tw] = meiro[ph][pw] + 1
            q.append((th,tw))
    
if meiro[Dh][Dw] == '.':
    print(-1)
else:
    print(meiro[Dh][Dw])
### BUGGY CODE ###

def prime_number(num):
    if num == 2 :
        return 1
    elif (num%2)==0:
        return 0
    elif num > 2:
        for i in range(3,num-1,2):
            if (num % i) == 0:
                return 0
        return 1

N =int(input())
count = 0
for i in range(0,N):
    num = int(input())
    count += int(prime_number(num))
print(count)


### FIXED CODE ###

import math
def isPrimeNum(num):
    sqrtNum = int(math.sqrt(num)) + 1
    if(num == 2 or num == 3):
        return True
    elif(num % 2 == 0):
        return False
    else:
        for i in range(3, sqrtNum , 2):
            if(num % i == 0 ):
                return False
        return True
    
count = 0
N = int(input())
for i in range(N):
    num = int(input())
    if(isPrimeNum(num)):
        count += 1

print(count)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
p = input().split()
p = [((int(i)+1)/2) for i in p]
arr_1d = np.array(p)
SUM_P = []
for i in range(N-K+1):
    SUM_P.append(np.sum(p[i:i+K]))
print(max(SUM_P))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
SUM_P=sum(p[0:K])
all_sum_p=[SUM_P]
for i in range(N-K):
    SUM_P=SUM_P-p[i]+p[i+K]
    all_sum_p.append(SUM_P)
print((max(all_sum_p)+K)/2)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys

readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
dic = defaultdict(list)
par = [i for i in range(N)]
rank = [0]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def unit(x, y):
  x = find(x)
  y = find(y)
  if x==y:
    return
  elif rank[x]<rank[y]:
    par[x] = y
    return
  elif rank[y]<rank[x]:
    par[y] = x
  else:
    par[y] = x
    rank[x] += 1

for i in range(M):
  l, r, d = map(int, readline().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  unit(l-1, r-1)


dist = [-1]*N
m = []
for x in range(N):
  y = find(x)
  m += [(y,0)]
  dist[y] = 0
m = set(m)
stuck = deque(m)
while stuck:
  e, a = stuck.popleft()
  flag = False
  for c in dic[e]:
    p, d = c
    x = d + dist[e]
    if dist[p]==-1:
      dist[p] = x
      stuck += [(p, x)]
    elif dist[p]!=x:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  print('Yes')

### FIXED CODE ###

from collections import defaultdict, deque
N, M = map(int, input().split())
used = [True]*N
dic = defaultdict(list)
for i in range(M):
  l, r, d = map(int,input().split())
  l -= 1
  r -= 1
  used[r] = False
  dic[l] += [(r,d)]

dist = [-1]*N
q = deque([])
for i in range(N):
  if used[i]:
    q += [i]
    dist[i] = 0

ans = True
while q:
  e = q.popleft()
  flag = False
  for p, d in dic[e]:
    if dist[p]==-1:
      dist[p] = d+dist[e]
      q += [p]
    elif dist[p]!=dist[e]+d:
      ans = False
      flag = True
      break
  if flag:
    break
if ans:
  if -1 not in dist:
    print('Yes')
  else:
    print('No')
else:
  print('No')
### BUGGY CODE ###

import sys
 
input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    print(min(x_set))
  else:
    print(-1)

### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

dist_matrix = [[INF]*N for _ in range(N)]
for A, B, C in ABC:
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

for i in range(N):
	dist_matrix[i][i] = 0

#for i in range(N):
#	print(dist_matrix[i])

def Warshall_Floyd(dist, N):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

Warshall_Floyd(dist_matrix, N)

#for i in range(N):
#	print(dist_matrix[i])

ans = INF
for x in permutations(r):
	dis = 0
	for i in range(1, R):
		dis += dist_matrix[x[i-1]-1][x[i]-1]
	ans = min(ans, dis)

print(ans)


### FIXED CODE ###

import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
dist_matrix = [[INF]*N for _ in range(N)]

for _ in range(M):
	A, B, C = MAP()
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

for i in range(N):
	dist_matrix[i][i] = 0

#for i in range(N):
#	print(dist_matrix[i])
#print()

def Warshall_Floyd(dist, N):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Warshall_Floyd(dist_matrix, N)

#for i in range(N):
#	print(dist_matrix[i])


ans = INF
for x in permutations(r):
	tmp = x[0]
	dis = 0
	for i in range(1, R):
		dis += dist_matrix[tmp-1][x[i]-1]
		tmp = x[i]
	ans = min(ans, dis)
	
print(int(ans))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

def b_search(L,key,left,right):
    #L[i] < keyを満たす最大のi
    #L[i] < key <= L[i+1]
    if key <= L[0]:
        return 0
    elif key > L[len(L)-1]:
        return len(L)
    else:
        mid = (left+right)//2
        if L[mid] < key and key <= L[mid+1]:
            return mid+1
        elif L[mid] >= key:
            return b_search(L,key,left,mid)
        else:
            return b_search(L,key,mid,right)

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += b_search(L[j+1:],L[i]+L[j],0,len(L[j+1:]))
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
d = []
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))

dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)

num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)

### FIXED CODE ###

N, W = map(int, input().split())
d = []
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))

d = sorted(d)
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)


num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

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

N, K, Q = map(int, input().split())
point = [0] * N

for i in range(Q):
    point[int(input()) - 1] += 1
    i += 1

for i in range(len(point)):
    ans = K - (sum(point) - point[i])
    if ans > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
point = [0] * N

for i in range(Q):
    point[int(input()) - 1] += 1
    i += 1

sum_point = sum(point)

for i in range(N):
    ans = K - (sum_point - point[i])
    if ans > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def simulator(n, a, b, s):
    print()
    boolean_list = ['No'] * n
    count = 0
    for i in range(n):
        if s[i]=='a' and count < a+b:
            count += 1
            boolean_list[i] = 'Yes'
        if s[i]=='b' and count < a+b and s[:i].count('b') <b :
            count += 1
            boolean_list[i] = 'Yes'
    
    for _ in boolean_list:
        print(_)

n, a, b = map(int,input().split())
s = input()
simulator(n, a, b, s)

### FIXED CODE ###

def simulator(n, a, b, s):
    print()
    boolean_list = ['No'] * n
    count = 0
    for i in range(n):
        if s[i]=='a' and count < a+b:
            count += 1
            boolean_list[i] = 'Yes'
        if s[i]=='b' and count < a+b and s[:i].count('b') <b :
            count += 1
            boolean_list[i] = 'Yes'
    
    for _ in boolean_list:
        print(_)

n, a, b = map(int,input().split())
s = input()
simulator(n, a, b, s)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [0 for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [[0, dic[0]]]
    visit[0] = 1
    counter = 1
    while counter < n:
        t = next_visit.pop(0)
        for s in t[1]:
            if visit[s] == 0:
                point[s] += point[t[0]]
                visit[s] = 1
                counter += 1
                next_visit.append([s, dic[s]])
    print(" ".join(map(str, point)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**3
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    seat = [[1] * N for _ in range(N)]
    zero = [[1] * N for _ in range(N)]

    ans = 0

    for i in P:
        x = (i-1) % N
        y = (i-1) // N
        min_cnt = INF
        if x == 0 or x == N-1 or y == 0 or y == N-1:
            min_cnt = 0
        else:

            dp = [[INF] * N for _ in range(N)]
            d = 0
            q = []
            heapify(q)
            heappush(q,(d,x,y))
            dp[x][y] = 0
            while q:
                d,i,j = heappop(q)
                for di,dj in ((1,0),(0,1),(-1,0),(0,-1)):
                    if not(0 <= i+di < N and 0 <= j+dj < N):
                        break
                    if zero[i+di][j+dj] == 0:
                        break
                    e = seat[i+di][j+dj]
                    if dp[i+di][j+dj] > d+e:
                        dp[i+di][j+dj] = d+e
                        heappush(q,(d+e,i+di,j+dj))
                else:
                    continue
                min_cnt = d
                break

        seat[x][y] = 0
        if min_cnt == 0:
            # q = collections.deque()
            # q.append((x,y))
            zero[x][y] = 0
            # while q:
            #     i,j = q.popleft()
            #     for di,dj in ((1,0),(0,1),(-1,0),(0,-1)):
            #         if not(0 <= i+di < N and 0 <= j+dj < N): continue
            #         if seat[i+di][j+dj] == 1 or zero[i+di][j+dj] == 0: continue
            #         zero[i+di][j+dj] = 0
            #         q.append((i+di,j+dj))
        ans += min_cnt
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

import numpy as np

X, Y, A, B, C = map(int, input().split())

p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = sorted(list(map(int,input().split())), reverse=True)

for i in r:
    p_min = p[0]
    q_min = q[0]

    if p_min > i and q_min > i:
        break

    p_min_diff = i - p_min
    q_min_diff = i - q_min

    if p_min_diff >= q_min_diff and p_min_diff > 0:
        p.remove(p_min)
        p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        q.remove(q_min)
        q.append(i)

p = np.array(p)
q = np.array(q)
print(np.sum(p) + np.sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

N = int(input())
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
A = factorize(N)
if len(A) == 1:
    ans = N-1
else: 
    ans = 9999999999999999999999
    from itertools import permutations as P
    from functools import reduce
    for i in range(1,len(A)):
        l1 = list(P(A,i))
        for l1_temp in l1:
            l2 = list(filter(lambda x : x not in l1,A))
            ans_1 = reduce(lambda x,y:x * y,l1_temp)
            ans_2 = N//ans_1
            ans_temp = (ans_1 + ans_2 -2)
            ans = min(ans,ans_temp)
print(ans)

### FIXED CODE ###

from math import ceil, sqrt
N = int(input())
for i in range(ceil(sqrt(N)),0,-1):
    if N%i == 0:
        print(i + N//i -2)
        break