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


"""
dp[i] i番目に到達するときの最小値
遷移
送るDP
i-1段目まで下記を実施
dp[i+1] = min(dp[i+1], dp[i]+コスト)
if (一段飛ばしできる余地があれば): 
    dp[i+2] = min(dp[i+2],dp[i]+コスト)

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

INF = 10**12
dp = [INF]*101000
dp[0] = 0

for i in range(1,N):
    for j in range(1,K+1):
        if i-j >= 0:
            cost = abs(hs[i]-hs[i-j])
            dp[i] = min(dp[i],dp[i-j]+cost)

print(dp[N-1])

### FIXED CODE ###

N, K = map(int,input().split())
hs = [int(i) for i in input().split()]

dp = [1000000]*N
dp[0] = 0
for i in range(1,N):
    # for k in range(K+1):
    x = max(0, i-K)
    # dp[i] = min(dp[i], dp[min_ind]+abs(hs[min_ind]-hs[i]))
    dp[i] = min([dpj + abs(hs[i] - hj) for hj, dpj in zip(hs[x:i], dp[x:i])])
# print(dp)
print(dp[-1])
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)):
    if s[i] != 'A':
        continue
    for j in range(i + 1, len(s)):
        if s[j] == 'Z':
            ans = max(ans, j + 1 - i)
print(ans)


### FIXED CODE ###

s = input()
n = len(s)
a = float('INF')
z = 0
for i in range(n):
    if s[i] == 'A':
        a = min(a, i)
    elif s[i] == 'Z':
        z = max(z, i)
print(z + 1 - a)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    B = set(A)
    for a in B:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            left = bisect_left(A, d)
            right = bisect_right(A, d)
            if left != right and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(A):
    n = A[-1]
    is_nodiv = [True for _ in range(n+1)]

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a
        
    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

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

n = int(input())
l = list(map(int,input().split()))
new_l = []
q = 0
for i in l:
  new_l.append(i)
  a = min(new_l)
  if a==i:
    q += 1
print(q)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
q = 1
a = l[0]
for i in range(1,n):
  a = min(l[i],a)
  if l[i]<=a:
    q += 1
print(q)
### BUGGY CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
N_array = [K] * N
np = np.array(N_array)
for x in A:
    np -= 1
    np[x - 1] += 1
for z in np:
    if z > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
N_array = [K - Q] * N
for x in A:
    N_array[x - 1] += 1
for z in N_array:
    if z > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse = True)
    f = list(map(int, input().split()))
    f.sort()
    right = a[0]*f[-1]
    left = 0
    while right > left:
        middle = (right + left)//2
        b = 0
        
        for i in range(n):
            b += max(0, a[i] - middle//f[i])
        if b <= k:
            right = middle
        else:
            left = middle+1

    print(right)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    import numpy as np
    
    n, k = map(int, input().split())
    a = np.array(input().split(), np.int64)
    f = np.array(input().split(), np.int64)
    a.sort()
    a = a[::-1]
    f.sort()
    right = np.max(a*f)
    left = 0
    while right > left:
        middle = (right + left)//2
        b = 0
        
        if np.sum(np.maximum(a-middle//f, 0)) <= k:
            right = middle
        else:
            left = middle+1

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

N = int(input())
a=[]
cnt=0
for i in range(N):
  a.append(input())
for j in range(N):
  a[j]=list(sorted(a[j]))
for k in range(N):
  cnt += (a.count(a[k])-1)
  
print(int(cnt/2))

### FIXED CODE ###

# coding: utf-8

N = int(input())
alp = [chr(i) for i in range(97, 97+26)]
L = []
for i in range(N):
    s = list(input())
    L.append(s)
for i in range(N):
    L[i].sort()
L.sort()

ans = 0
cnt = 1
for i in range(N-1):
    if L[i]==L[i+1]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
if cnt > 1:
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

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

T=[[] for i in range(N)]

for i in range(N-1):
    a,b=map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

O=[0 for i in range(N)]

for i in range(Q):
    p,x=map(int,input().split())
    O[p-1]+=x

def dfs(n):
    for i in T[n]:
        if r[i]:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

T=[[] for i in range(N)]

for i in range(N-1):
    a,b=map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

O=[0 for i in range(N)]

for i in range(Q):
    p,x=map(int,input().split())
    O[p-1]+=x

def dfs(n):
    for i in T[n]:
        if r[i]:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)
### BUGGY CODE ###

from collections import OrderedDict

A, B, K = map(int, input().split())
L = []
res = []

for i in range(A, B+1):
    L.append(i)

if K > B-A:
    for i in L:
        print(i)
    exit()
else:
    for i in range(0, K):
        res.append(L[i])
    for i in range(len(L)-K, len(L)):
        res.append(L[i])

res_unique = list(set(res))
res_unique.sort()

for i in res_unique:
    print(i)

### FIXED CODE ###

from collections import OrderedDict

A, B, K = map(int, input().split())
L = []
res = []

if K > B-A:
    for i in range(A, B+1):
        print(i)
    exit()
else:
    for i in range(A, A+K):
        res.append(i)
    for i in range(B-K+1, B+1):
        res.append(i)

res_unique = list(set(res))
res_unique.sort()

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

n, k = map(int, input().split())
lis = []
while lis.count(abs(n-k)) == 0:
    lis.append(abs(n-k))
    n = abs(n-k)
print(min(lis))

### FIXED CODE ###

n, k = map(int, input().split())
a, b = divmod(n, k)
print(min(abs(n - k*(a+1)), b))
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
 
for i in range(R+1):
	dpi = dp[i]
	dpi2 = dp[i+1]
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dpi[nj][m] = max(dpi[nj][m], dpi[j][m])
			if m < 3:
				dpi[nj][m+1] = max(dpi[nj][m+1], dpi[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dpi2[nj][0] = max(dpi2[nj][0], dpi[j][m])
			dpi2[nj][1] = max(dpi2[nj][1], dpi[j][m]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)
### BUGGY CODE ###

import sys, collections, heapq
def input(): return sys.stdin.readline().strip()

def main():
    """
    スマートそうな別解を見つけたのでこちらも解読してみる
    https://atcoder.jp/contests/abc128/submissions/5654668
    """
    N, Q = map(int, input().split())
    add = []
    delete = []
    for i in range(N):
        S, T, X = map(int, input().split())
        add.append((S - X, X))
        delete.append((T - X, X))
    heapq.heapify(add)
    heapq.heapify(delete)

    """
    以下自力で思いつける気がしないぞ。工事一つずつ見て行って引っかかりうるものを検査している。
    d1,...,dQは昇順に並んでいるので、
        前の人で工事に引っかかりうる　→　次の人も工事に引っかかりうる
        前の人が実は工事に引っかからない　→　次の人も実は工事に引っかからない
    により、引っかかりうる工事の集合はQ回のループで使いまわせる。
    """

    active = []
    to_delete = collections.defaultdict(int)
    for _ in range(Q):
        x = int(input())
        while add and add[0][0] <= x: # xが工事に引っかかる可能性があれば、工事座標をactiveに追加
            S, X = heapq.heappop(add)
            heapq.heappush(active, X)

        while delete and delete[0][0] <= x: # xが工事終了後に工事現場を通過する場合、それをto_deleteに記録
            T, X = heapq.heappop(delete)
            to_delete[X] += 1

        while active and to_delete[active[0]] > 0: # 工事に引っかかる可能性のあるもので、実は工事に引っかからないものは除外
            to_delete[active[0]] -= 1
            heapq.heappop(active)

        print(active[0] if active else -1) # 一巡してもactiveは空になっていないことに注意


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    """
    計算量の落とし方が全くわからんので以下のコードを参考に写経。。。
    https://atcoder.jp/contests/abc128/submissions/7712981
    """
    N, Q = map(int, input().split())
    work = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        work.append((x, s - x, t - x))
    work.sort(key=lambda x: (x[0], x[1]))
    start = [int(input()) for _ in range(Q)]

    """
    工事箇所を原点にスライドさせる事で考察を易化しておく。
    各工事(x, s, t)に対して（既にs, tは原点への移動を考慮済み）s<=d<tなるdの個数を求めたい
    startは既に昇順に並んでいるので二分探索でs<=d_i<d_{i+1}<...<d_{j-1}<tなるi=left, j=rightを求める。

    そのあと[left, right)をxで埋めていくが、愚直に(right-left)回xを代入していくとO(Q)かかってTLEするので
    skip[left]=(以前に[left, right)を埋めたときのright)を格納しておく。
    これによりansの表を毎度全走査しなくてもよくなり書き込み範囲のオーバーラップがだいぶ削減される。

    しかしskipを使っても飛んだ先がまたskip命令入ってる可能性もあるから、AC出来るのはやや偶然感あり。。。
    """

    ans = [-1] * Q
    skip = [-1] * Q
    for x, s, t in work:
        left = bisect_left(start, s)
        right = bisect_left(start, t)
        while left < right:
            if skip[left] == -1:
                ans[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]

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




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

import re

def main():
    K = int(input())
    firstPlace = K % 10

    if firstPlace == 1:
        seed = 7
    elif firstPlace == 3:
        seed = 9
    elif firstPlace == 7:
        seed = 1
    elif firstPlace == 9:
        seed = 3
    else:
        return -1

    while True:
        verifiStr = str(K * seed)

        repattern = re.compile("^7+$")
        result = repattern.match(verifiStr)

        if result:
            return len(verifiStr)          

        seed = seed + 10

if __name__ == "__main__":
    answer = main()
    print(answer)

### FIXED CODE ###

def main():
    K = int(input())

    if K % 2 == 0:
        return -1
    elif K % 5 == 0:
        return -1

    an = 7
    counter = 1

    while True:
        modan = an % K

        if modan == 0:
            return counter

        an = modan * 10 + 7
        counter = counter + 1

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

def make_sosu_tbl():
    for i in range(2, MAX_N):
        if sos[i]:
            for j in range(i+i, MAX_N+1, i):
                sos[j] = 0
        if i**2 >= MAX_N:break

while 1:
    MAX_N = int(input())
    if not MAX_N: break
    sos = [1] * (MAX_N+1)
    make_sosu_tbl()

    for i in reversed(range(13,MAX_N+1)):
        if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
            print(i)
            break

### FIXED CODE ###

# from datetime import datetime

# measure_start = datetime.now()
move = [[[10, 10], [4, 4]], [[8, 2],[4, 2]]]

MAX_N = 10000000+1
sos = [1] * (MAX_N+1)
sos[0] = sos[1] = 0
for i in range(2, int(MAX_N**0.5)+1):
    if sos[i]:
        for j in range(i+i, MAX_N+1, i):
            sos[j] = 0

while 1:
    try:
        n = int(input())

        if not n: break
        n -= (n%2 == 0)
        while n >= 13:
            if sos[n] and sos[n-2] and sos[n-6] and sos[n-8]:
                print(n)
                break
            else:
                n -= move[sos[n-8]][sos[n-6]][sos[n-2]]
    # measure_stop = datetime.now()
    # print(measure_stop - measure_start)
    except:
        pass
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

R, C, k = map(int, input().split())
field = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1; c -= 1
    field[r][c] = v

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp0 = dp[0]; dp1 = dp[1]; dp2 = dp[2]; dp3 = dp[3]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        for k in range(4):
            ij = i * C + j
            ij1 = ij + 1
            i1j = ij + C
            item = field[i][j]
            # Use
            if item and k < 3:
                dp[k+1][ij1] = max(dp[k+1][ij1], dp[k][ij] + item) 
                dp0[i1j] = max(dp0[i1j], dp[k][ij] + item) 
            # No use down
            dp0[i1j] = max(dp0[i1j], dp[k][ij]) 
            # No use right
            dp[k][ij1] = max(dp[k][ij1], dp[k][ij]) 

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

R, C, k = map(int, input().split())
field = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1; c -= 1
    field[r][c] = v

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp0 = dp[0]; dp1 = dp[1]; dp2 = dp[2]; dp3 = dp[3]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        ij = i * C + j
        ij1 = ij + 1
        i1j = ij + C
        item = field[i][j]
        # Use
        if item:
            dp1[ij1] = max(dp1[ij1], dp0[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp0[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp0[ij]) 
        dp0[ij1] = max(dp0[ij1], dp0[ij]) 
        if item:
            dp2[ij1] = max(dp2[ij1], dp1[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp1[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp1[ij]) 
        dp1[ij1] = max(dp1[ij1], dp1[ij]) 
        if item:
            dp3[ij1] = max(dp3[ij1], dp2[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp2[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp2[ij]) 
        dp2[ij1] = max(dp2[ij1], dp2[ij]) 
        dp0[i1j] = max(dp0[i1j], dp3[ij]) 
        dp3[ij1] = max(dp3[ij1], dp3[ij]) 

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)
### BUGGY CODE ###

def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    A = [[]] * N
    for i in range(M):
        pp, ss = map(int, input().split())
        ss -= 1
        pp -= 1
        A[pp] = A[pp] + [H[ss]]
        A[ss] = A[ss] + [H[pp]]

    ans = 0
    for j in range(N):

        now = H[j]
        if (not A[j] or now > max(set(A[j]))):
            ans += 1

    print(ans)


resolve()

### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())
    hhh = list(map(int, input().split()))
    nice = [1] * n

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ha = hhh[a]
        hb = hhh[b]
        if ha <= hb:
            nice[a] = False
        if ha >= hb:
            nice[b] = False

    print(sum(nice))


resolve()
### BUGGY CODE ###

#!/usr/bin/env python

import sys

def getVertex(i,e):
    v= set()
    for v1 in e[i]:
        for v2 in e[v1]:
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )


### FIXED CODE ###

#!/usr/bin/env python

import sys

v1mask= set()
v2mask= set()

def getVertex(i,e):
    global v1mask, v2mask
    v= set()
    for v1 in e[i]:
        if v1 in v1mask: continue
        v1mask.add( v1 )
        for v2 in e[v1]:
            if v2 in v2mask: continue
            v2mask.add( v2 )
            for v3 in e[v2]: v.add( v3 )
    #
    return v
#
n,m = [ int(x) for x in sys.stdin.readline().split() ]
e = { i:[] for i in range(n) }
for _ in range(m):
    u,v = [ int(x) for x in sys.stdin.readline().split() ]
    e[u-1].append( v-1 )
s,t = [ int(x)-1 for x in sys.stdin.readline().split() ]
#
hop= 0
now = {s}
visit = {s}
while True:
    hop+= 1
    n= set()
    for i in now:
        n |= getVertex(i,e) - visit
        if t in n: break
    #
    if t in n: break
    if not n:
        hop= -1
        break
    now = n
    visit|= n
#
print( hop )
### BUGGY CODE ###

N, X = list(map(int, input().split()))
x = list(map(int, input().split()))

D = [pow(i, 2) for i in range(1, N + 2)]
L = [0] * N
DL = [0] * (N + 1)
t = 2
for i in range(N - 1, -1, -1):
  for j in range(t, N + 1):
    if (D[j] - D[j - 1] - 5) * x[i] > X:
      break
    t = j
  L[i] = t
  DL[t] += 1

least = 1
AD = [0] * (N + 1)

getNum = 0
for i in range(L[-1], N + 1):
  if DL[i] == 0:
    continue
  t = DL[i]
  for j in range(least, i):
    t -= (i - j) * AD[j]
    if t <= 0:
      break
  for j in range(DL[i]):
    if t >= 1:
      t -= i
      AD[1] += 1
      getNum += 1
    else:
      AD[least] -= 1
      AD[least + 1] += 1
      if AD[least] == 0:
        least += 1
FA = 1e20
for j in range(getNum, N + 1):
  least = 0
  Ans = X * (N + j)
  cnt = -1
  t = 0
  flag = False
  for i in x[::-1]:
    if flag:
      Ans += (D[least + 1] - D[least]) * x[cnt]    
    else:
      Ans += (D[0] + D[1]) * x[cnt]
    cnt -= 1
    t += 1
    if t == j:
      t = 0
      least += 1
      flag = True
    if Ans >= FA:
      break
  else:
    FA = Ans
    continue
print(FA)


### FIXED CODE ###

N, X = list(map(int, input().split()))
x = list(map(int, input().split()))

D = [pow(i, 2) for i in range(1, N + 2)]

ok = N
ng = 1
List = [-1 for i in range(N + 1)]
while abs(ok - ng) > 2:
  LR = [(ok - ng) // 3 + ng, 2 * (ok - ng) // 3 + ng]
  Ans = [0, 0]
  for j in range(2):
    if List[LR[j]] != -1:
      Ans[j] = List[LR[j]]
      continue
    least = 0
    Ans[j] = X * (N + LR[j])
    cnt = -1
    t = 0
    flag = False
    for i in x[::-1]:
      if flag:
        Ans[j] += (D[least + 1] - D[least]) * x[cnt]    
      else:
        Ans[j] += (D[0] + D[1]) * x[cnt]
      cnt -= 1
      t += 1
      if t == LR[j]:
        t = 0
        least += 1
        flag = True
    List[LR[j]] = Ans[j]
  if Ans[0] < Ans[1]:
    ok = LR[1]
  else:
    ng = LR[0]
 
FA = 1e20
for j in range(ng, ok + 1):
  if List[j] != -1:
    FA = min(FA, List[j])
    continue
  least = 0
  Ans = X * (N + j)
  cnt = -1
  t = 0
  flag = False
  for i in x[::-1]:
    if flag:
      Ans += (D[least + 1] - D[least]) * x[cnt]    
    else:
      Ans += (D[0] + D[1]) * x[cnt]
    cnt -= 1
    t += 1
    if t == j:
      t = 0
      least += 1
      flag = True
  FA = min(FA, Ans)
print(FA)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
c=0
for i in range(len(A)):
  c+=A[i]*(sum(A)-A[i])
print(c//2%MOD)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)
### BUGGY CODE ###

def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    mid = deque([])
    for K,L,R in KLR:
      x = L - R
      if x==0:
        mid.append([K-1,L,R,x])
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    ans = 0
    for klr in left:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
    for klr in mid:
      ans += klr[1]

    print(ans)
    
main()

### FIXED CODE ###

def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  from heapq import heapify,heappop,heappush
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K,L,R])
        ans += R
      else:
        right.append([K+1,L,R])
        ans += L

    left = sorted(left)
    right = sorted(right,reverse=True)
      
    S = []
    heapify(S)
    x = 1
    i = 0
    length = len(left)
    while x<=N:
      while i<length:
        klr = left[i]
        if klr[0]==x:
          heappush(S,klr[1]-klr[2])
          i += 1
          
        else:
          break
      
      y = len(S) - x
      if y<=0:
        x += 1
        continue
      else:
        for _ in range(y):
          heappop(S)
          
    ans += sum(S)
    
    S = []
    heapify(S)
    x = N+1
    i = 0
    length = len(right)
    while x>=0:
      while i<length:
        klr = right[i]
        if klr[0]==x:
          heappush(S,klr[2]-klr[1])
          i += 1
 
        else:
          break
      
      y = len(S) + x - N - 1
      if y<=0:
        x -= 1
        continue
      else:
        for _ in range(y):
          heappop(S)    
    ans += sum(S)
    print(ans)
    
main()
### BUGGY CODE ###

n=int(input())
ans=[]
for i in range(1,10**7):
    if i>=n:
        break
    elif n%i==0:
        ans.append(i+(n//i))
print(min(ans)-2)


### FIXED CODE ###

n=int(input())
ans=[]
for i in range(1,10**7):
    if i>=n:
        break
    elif n%i==0:
        ans.append(i+(n//i))
print(min(ans)-2)