Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
N = int(input())
a = [int(i) for i in input().split()]

ans = []
x = 0

for h in range(N):
    B = [0]
    for i in range(1,N+1):
        B.append(a[i-1] + B[i-1])

    for i in range(N):
        if B[N] - B[i] == B[i]:
            ans.append(x)
        else:
            a[h] += 1
            x += 1


for h in range(N):
    B = [0]
    for i in range(1,N+1):
        B.append(a[i-1] + B[i-1])

    for i in range(N):
        if B[N] - B[i] == B[i]:
            ans.append(x)
        else:
            a[h] -= 1
            x += 1

#print(ans)
print(min(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()] 

su = [0 for _ in range(n)] #鉄の棒の切れ目の座標
for i in range(n):
    su[i] = su[i-1] + a[i]
#print(su)

tmp = 2 * pow(10, 10) + 1
for i in su:
    if abs(i - su[-1]/2) < tmp:
        tmp = abs(i - su[-1]/2)
#print(su[-1]/2, tmp)

"""
#中心に一番近い鉄の棒の切れ目と中心との距離の差
l = 0
r = n-1
while (l - r) >= 1:
    c = (l + r) // 2
    #print(l, r, c)
    if su[c] < su[-1] / 2:
        l = c
    elif su[c] > su[-1] / 2:
        r = c
#print(su[l], su[r])
tmp = min(abs(su[l] - su[-1]/2), abs(su[r] - su[-1]/2))
print(tmp)
"""

ans = 2 * tmp
print(int(ans))
MOD=10**9+7

def powmod(a,n,m): #a^n mod m
    ans=1
    while n!=0:
        if n&1: ans=ans*a%m
        a=a*a%m
        n>>=1
    return ans%m

def fact(n):
    ans=1
    for i in range(n): ans=ans*(i+1)%MOD
    return ans

def fact(a,b):
    ans=1
    for i in range(a,b+1): ans*=ans*i%MOD
    return ans

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

ans=powmod(2,n,MOD)-1
ta1=fact(n-a+1,n)
tb1=fact(n-b+1,n)
ta2=pow(fact(a),MOD-2,MOD)
tb2=pow(fact(b),MOD-2,MOD)
a=ta1*ta2%MOD
b=tb1*tb2%MOD
print((ans-a-b)%MOD)

### FIXED CODE ###

MOD=10**9+7

def powmod(a,n,m): #a^n mod m
    ans=1
    while n!=0:
        if n&1: ans=ans*a%m
        a=a*a%m
        n>>=1
    return ans%m

def fact(a,b):
    ans=1
    for i in range(a,b+1): ans=ans*i%MOD
    return ans

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

ans=powmod(2,n,MOD)-1
ta1=fact(n-a+1,n)
tb1=fact(n-b+1,n)
ta2=pow(fact(1,a),MOD-2,MOD)
tb2=pow(fact(1,b),MOD-2,MOD)
a=ta1*ta2%MOD
b=tb1*tb2%MOD
print((ans-a-b)%MOD)
import collections
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    input_q = list(map(int, input().split()))
    B.append(input_q[0])
    C.append(input_q[1])
    
A_sum = sum(A)
CONST_MAX = 100000
count_list = [0] * CONST_MAX

for i in range(CONST_MAX):
    count_list[i] = A.count(i)

for i in range(Q):
    count_list[C[i]] += count_list[B[i]]
    A_sum += (C[i] - B[i]) * count_list[B[i]]
    count_list[B[i]] = 0

    print(A_sum)


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    input_q = list(map(int, input().split()))
    B.append(input_q[0])
    C.append(input_q[1])
    
A_sum = sum(A)
CONST_MAX = 100001
count_list = [0] * CONST_MAX

c = collections.Counter(A)
for k, v in c.items():
    # print(k, v)
    count_list[k] = v


for i in range(Q):
    count_list[C[i]] += count_list[B[i]]
    A_sum += (C[i] - B[i]) * count_list[B[i]]
    count_list[B[i]] = 0
    # print(count_list)

    print(A_sum)
40 90

### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
came=[set() for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    lst.add(b)
    came[b].add(a)

st=list(set(range(1,N))-lst)[0]
stack=deque([st])
lst=[0 for i in range(N+1)]


while stack:
    a=stack.popleft()
    for p in data[a]:
        came[p].remove(a)
        if not came[p]:
            lst[p]=a
            stack.append(p)

for i in range(1,N+1):
    print(lst[i])
#from sys import stdin

#input = stdin.readline
#inputRstrip = stdin.readline().rstrip

#x = input().rstrip()
#n = int(input())

#a,b,c = input().split()
#a,b,c = map(int, input().split())

ST = [input() for i in range(2)]
S = ST[0]
T = ST[1]
ans = len(T)

for i in range(len(S) - len(T) + 1):
	count = len(T)
	for j in range(len(T)):
		if(T[j] == S[i + j]):
			count -= 1
	if(ans > count):
		ans = count
print(ans)

### FIXED CODE ###


from sys import stdin

input = stdin.readline().rstrip

#x = input().rstrip()
#n = int(input())

#a,b,c = input().split()
#a,b,c = map(int, input().split())

D,T,S = map(int, input().split(" "))

if(T * S >= D):
	print("Yes")
else:
	print("No")
N,Q = map(int,input().split())
ablist = [[] for _ in range(N+1)]
anslist = [0]*(N+1)

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

pxlist = [list(map(int,input().split())) for _ in range(Q)]

for q,x in pxlist:
    anslist[q] += x

def dfs(nownode,oya=-1):
    for b in ablist[nownode]:
        if oya == b:
            continue
        anslist[b] += anslist[nownode]
        dfs(b,nownode)
dfs(1)
print(' '.join(map(str,anslist[1:])))

### FIXED CODE ###

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

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)

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

# def dfs(x, p):
#     for j in T[x]:
#         if j == p:
#             continue
#         X[j] += X[x]
#         dfs(j, x)
def dfs(nownode,oya=-1):
    for nextnode in T[nownode]:
        if oya == nextnode:
            continue
        X[nextnode] += X[nownode]
        dfs(nextnode,nownode)

dfs(0, -1)

print(*X)
def SsSl(): return list(map(lambda x: x, input()))

n = int(input())
#List = [s for s in input().split()]
List = SsSl()

if n%2==1:
    print("No")
else:
    if List[0:(n/2)]==List[(n/2):]:
        print("Yes")
    else:
        #print(List[0:(n/2)])
        #print(List[(n/2):])
        print("No")

### FIXED CODE ###

def SsSl(): return list(map(lambda x: x, input()))

n = int(input())
#List = [s for s in input().split()]
List = SsSl()

if n%2==1:
    print("No")
else:
    if List[0:(n//2)]==List[(n//2):]:
        print("Yes")
    else:
        #print(List[0:(n/2)])
        #print(List[(n/2):])
        print("No")
def solve(N, K, h):
	INF = 10000 * N * K + 10000
	cost = [INF for x in range(N)]
	cost[0] = 0
	for i in range(N):
		for j in range(min(N, i + 1), min(N, i + K + 1)):
			cost_ij = abs(h[i] - h[j]) + cost[i]
			cost[j] = min(cost[j], cost_ij)
	return cost[N - 1]


def main():
	N , K = list(map(int, input().split()))
	h = list(map(int, input().split()))
	assert len(h) == N
	assert N >= 2
	res = solve(N, K, h)
	print(res)


if __name__ == '__main__':
	main()

### FIXED CODE ###

def solve(h):
	best_p = abs(h[0] - h[1])
	best_pp = 0
	n = 2
	while n < len(h):
		cost1 = best_p + abs(h[n] - h[n-1])
		cost2 = best_pp + abs(h[n] - h[n-2])
		best = min(cost1, cost2)
		best_pp, best_p = best_p, best
		n = n + 1
	return best_p


def main():
	N = int(input())
	heights = list(map(int, input().split()))
	assert len(heights) == N
	assert N >= 2
	res = solve(heights)
	print(res)


if __name__ == '__main__':
	main()
N,M=map(int,input().split())
s=[0]*M
c=[0]*M
a=0
for i in range(M):
	s[i],c[i]=map(int,input().split())
ans=-1
for j in range(1,1000):
	value=str(j)
	if len(value)==N:
		if max(s)<=N:
			for S,C in zip(s,c):
				if int(value[S-1])==C:
					a+=1
			if a==M:
				ans=int(j)
				break
			else:
				a=0
		else:
			continue
	else:
		continue
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
s=[0]*M
c=[0]*M
a=0
for i in range(M):
	s[i],c[i]=map(int,input().split())
ans=-1
if M==0:
	ans=1*(10**(N-1))
	if ans==1:
		ans=0
	print(ans)
	exit()
if max(s)>N:
	print(ans)
	exit()
for j in range(0,1000):
	value=str(j)
	if len(value)==N:
		for S,C in zip(s,c):
			if int(value[S-1])==C:
				a+=1
		if a==M:
			ans=int(j)
			break
		else:
			a=0
	else:
		continue
print(ans)
N, T=map(int, input().split())
lst=[list(map(int, input().split())) for _ in range(N)]
MAXN, MAXT=3001, 3001
dp1=[[0 for _ in range(MAXT)] for _ in range(MAXN)]
dp2=[[0 for _ in range(MAXT)] for _ in range(MAXN)]
for i in range(1, N+1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp1[i][j]=max(dp1[i-1][j], dp1[i-1][j-A]+B) if j>=A else dp1[i-1][j]
for i in range(N, 0, -1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp2[i][j]=max(dp2[i+1][j], dp2[i+1][j-A]+B) if j>=A else dp2[i+1][j]
ans=dp1[N-1][T-1]+lst[-1][1]
for i in range(1, N):
  A, B=lst[i-1]
  for j in range(T):
    ans=max(ans, dp1[i-1][j]+dp2[i+1][T-1-j]+B)
print(ans)

### FIXED CODE ###

N, T=map(int, input().split())
lst=[list(map(int, input().split())) for _ in range(N)]
MAXN, MAXT=3001, 3001
dp1=[[0 for _ in range(MAXT)] for _ in range(MAXN+1)]
dp2=[[0 for _ in range(MAXT)] for _ in range(MAXN+1)]
for i in range(1, N+1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp1[i][j]=max(dp1[i-1][j], dp1[i-1][j-A]+B) if j>=A else dp1[i-1][j]
for i in range(N, 0, -1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp2[i][j]=max(dp2[i+1][j], dp2[i+1][j-A]+B) if j>=A else dp2[i+1][j]
ans=dp1[N-1][T-1]+lst[-1][1]
for i in range(1, N):
  A, B=lst[i-1]
  for j in range(T):
    ans=max(ans, dp1[i-1][j]+dp2[i+1][T-1-j]+B)
print(ans)
h, w, k = map(int,input().split())
c = [list(input()) for i in range(h)]
ans = 0
for p_h in range(2**h):
    for p_w in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (p_h>>i)&1==0 and (p_w>>j)&==0:
                    if c[i][j]=='#':
                        black += 1
        if black == k:
            ans += 1
print(ans)

### FIXED CODE ###

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for paint_h in range(2**h): #すべての行の塗りつぶし方を2進数で列挙する
 for paint_w in range(2**w): #すべての列の塗りつぶし方を2進数で列挙する
   cnt=0
   for i in range(h): #すべてのi行目j列目の要素についてみる
     for j in range(w):
       if (paint_h>>i)&1==0 and (paint_w>>j)&1==0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
         if board[i][j]=='#': #塗りつぶされないマスが黒マスであれば個数を+1する
           cnt+=1
   if cnt==k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
     ans+=1
print(ans)
import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1

def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '#':
                tmp += 1 
            
    return tmp

ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1

print(ans)   

### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1])

# print(hl)
# print(wl)


def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '#':
                tmp += 1 
            
    return tmp


ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1


print(ans)
from sys import stdin

def main():
    input = lambda: stdin.readline()[:-1]
    H, W, A, B = map(int, input().split())

    if all((A > 0 and H % A, B > 0 and W % B)):
        print('No')
        return

    grid = [[0] * W for _ in [0] * H]
    grid[0][0] = 1
    for h in range(H):
        i = h // B if h else 0
        for w in range(A):
            grid[h][w+i] = 1

    for s in grid:
        print(*s, sep='')

main()


### FIXED CODE ###

from sys import stdin

def main():
    input = lambda: stdin.readline()[:-1]
    H, W, A, B = map(int, input().split())

    grid = [[1] * A + [0] * (W - A) for _ in range(B)]
    grid += [[0] * A + [1] * (W - A) for _ in range(H - B)]
    for n in grid:
        print(*n, sep='')

main()
setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)


for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()

print("Yes")

### FIXED CODE ###

from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)


for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()

print("Yes")
# @author 

import sys

class DAnythingGoesToZero:
    def solve(self, tc=0):
        n = int(input())
        # n = 10 ** 5
        x = input().strip()
        cache = [-1] * (n + 1)
        cache[0] = 0
        for nb in range(n + 1):
            v = 0
            i = nb
            while cache[i] == -1:
                i %= bin(i).count('1')
                v += 1

            cache[nb] = v + cache[i]

        # print(cache[8191])

        def brem(N, D):
            n = len(N)
            R = 0
            for i in range(n - 1, -1, -1):
                R <<= 1
                R |= int(N[n - 1 - i])
                if R >= D:
                    R -= D
            return R

        x = list(x)
        ones = x.count('1')
        r1 = brem(x, ones + 1)
        r2 = brem(x, ones - 1)
        for i in range(n):
            if x[i] == '0':
                # print((r + pow(2, n - 1 - i, ones + 1)) % (ones + 1), '*')
                print(cache[(r1 + pow(2, n - 1 - i, ones + 1)) % (ones + 1)] + 1)
            else:
                print(cache[(r2 - pow(2, n - 1 - i, ones - 1)) % (ones - 1)] + 1)
            # x[i] = str(int(x[i]) ^ 1)
            # print(cache[brem(x, x.count('1'))] + 1)
            # x[i] = str(int(x[i]) ^ 1)

solver = DAnythingGoesToZero()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class DAnythingGoesToZero:
    def solve(self, tc=0):
        n = int(input())
        # n = 10 ** 5
        x = input().strip()
        cache = [-1] * (n + 1)
        cache[0] = 0
        for nb in range(n + 1):
            v = 0
            i = nb
            while cache[i] == -1:
                i %= bin(i).count('1')
                v += 1

            cache[nb] = v + cache[i]

        # print(cache[8191])

        def brem(N, D):
            n = len(N)
            R = 0
            for i in range(n - 1, -1, -1):
                R <<= 1
                R |= int(N[n - 1 - i])
                if R >= D:
                    R -= D
            return R

        x = list(x)
        ones = x.count('1')
        r1 = brem(x, ones + 1)
        r2 = brem(x, ones - 1) if ones > 1 else 0
        for i in range(n):
            if x[i] == '0':
                # print((r + pow(2, n - 1 - i, ones + 1)) % (ones + 1), '*')
                print(cache[(r1 + pow(2, n - 1 - i, ones + 1)) % (ones + 1)] + 1)
            else:
                if ones == 1:
                    print(0)
                    continue
                print(cache[(r2 - pow(2, n - 1 - i, ones - 1)) % (ones - 1)] + 1)
            # x[i] = str(int(x[i]) ^ 1)
            # print(cache[brem(x, x.count('1'))] + 1)
            # x[i] = str(int(x[i]) ^ 1)

solver = DAnythingGoesToZero()
input = sys.stdin.readline

solver.solve()
print(max([i*i for i in range(10001) if int(input())>=i]))

### FIXED CODE ###

print((lambda x:max([i*i for i in range(100001) if x>=i*i]))(int(input())))
N=int(input())
A=list(map(int, input().split()))
l = [0] * N
ans = ""
for i in range(N):
  sys.stdout.write(A.index(i+1)+1)
  sys.stdout.write(" ")
  


### FIXED CODE ###

N=int(input())
As=list(map(int, input().split()))
man = [""] * N
for i in range(N):
  man[As[i]-1] = str(i+1)
result = ' '.join(man)
print(result)
a=int(intput())
print(a+a^2+a^3)

### FIXED CODE ###

a=int(input())
print(a+a**2+a**3)
H, W = map(int, input().split())
s = []
for _ in range(H):
    s += [list(input())]

ls = [[0]*W for _ in range(H)]
ls[0][0] = int(bool(s[0][0]=="#"))

for i in range(1,H):
    ls[0][i] = ls[0][i-1]+ int(bool(s[0][i]=="." and s[0][i-1]=="#"))
    
for j in range(1,W):
    ls[j][0] = ls[j-1][0]+ int(bool(s[j][0]=="." and s[j-1][0]=="#"))

for i in range(1,H):
    for j in range(1,W):
        ls[j][i] = min(ls[j][i-1]+ int(bool(s[j][i]=="." and s[j][i-1]=="#")),
                       ls[j-1][i]+ int(bool(s[j][i]=="." and s[j-1][i]=="#")))
        
print(ls[-1][-1])


### FIXED CODE ###

H, W = map(int, input().split())
s = []
for _ in range(H):
    s += [list(input())]

ls = [[0]*W for _ in range(H)]
ls[0][0] = int(bool(s[0][0]=="#"))

for i in range(1,W):
    ls[0][i] = ls[0][i-1]+ int(bool(s[0][i]=="#" and s[0][i-1]=="."))
    
for j in range(1,H):
    ls[j][0] = ls[j-1][0]+ int(bool(s[j][0]=="#" and s[j-1][0]=="."))

for i in range(1,W):
    for j in range(1,H):
        ls[j][i] = min(ls[j][i-1]+ int(bool(s[j][i]=="#" and s[j][i-1]==".")),
                       ls[j-1][i]+ int(bool(s[j][i]=="#" and s[j-1][i]==".")))
        
print(ls[-1][-1])
n, a, b = map(int input().split())
print(min(a * n, b))

### FIXED CODE ###

n, a, b = map(int, input().split())
print(min(a * n, b))
n = int(input())
nums = [int(i) for i in input().split(" ")]

approved = True
for num in nums:
  if num%2 == 0:
    approved = (num%3 == 0) or (num%5 == 0)
if approved:
  print('APPROVED')
else:
  print('DENIED')
  

### FIXED CODE ###

a, b, c = map(int, input().split())

if (a == b) and (b == c):
  print('No')
elif (a == b) or (b == c) or (a == c):
  print('Yes')
else:
  print('No')
n, m = map(int,(input().split()))
d = {}
for i in range(n):
    a, b = map(int,(input().split()))
    d[a]=b
d = sorted(d.items())
ans = 0
for i in range(n):
    if d[i][1] >= m: # 残り本数 >= この値段の本数
        ans += d[i][0]*m
        print(ans)
        exit
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]


### FIXED CODE ###

n, m = map(int,(input().split()))
d = []
for i in range(n):
    a, b = map(int,(input().split()))
    d.append([a,b])
d = sorted(d)
ans = 0
for i in range(n):
    if d[i][1] >= m: # 残り本数 >= この値段の本数
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
        if m <= 0:
            break
print(ans)
NK=int(input())
ListNK=NK.split() #ListNK[0]=N,[1]=K
N=int(ListNK[0])
K=int(ListNK[1])
Listh=[]
ListQ=[]
for i in range(0,N,1):
  hi=int(input())
  Listh.append(hi)

Listh.sort() #Listhの要素を小さい順に並べる
for i in range(0,N-K,1):
  Q=int(Listh[K+i-1]-Listh[i]) #hmax-hminの候補.Qminを求めればよい
  ListQ.append(Q)
ListQ.sort()
print(ListQ[0])


### FIXED CODE ###

NK=input()
ListNK=NK.split() #ListNK[0]=N,[1]=K
N=int(ListNK[0])
K=int(ListNK[1])
Listh=[]
ListQ=[]
for i in range(0,N,1):
  hi=int(input())
  Listh.append(hi)

Listh.sort() #Listhの要素を小さい順に並べる
for i in range(0,N-K+1,1):
  Q=int(Listh[K+i-1]-Listh[i]) #hmax-hminの候補.Qminを求めればよい
  ListQ.append(Q)
ListQ.sort()
print(ListQ[0])
n = int(input())

ls = list(map(int, input().split()))

queue = []

for i in range(n)
	a = ls[i] - 1
  	queue[a] = i

    
print(queue)

### FIXED CODE ###

n = int(input())
 
ls = list(map(int, input().split()))
ans = []

for i in range(n):
  ans.append(0)
  
for i in range(n):
  ans[ls[i]-1] = i + 1
  
for i in range(n):
  print(ans[i], end = " ")
K,M = map(int,input().split())
if 500*K >= X:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

K,M = map(int,input().split())
if 500*K >= M:
    print("Yes")
else:
    print("No")
n = int(input())
a = list(map(int, input().split()))
jud = True
for i in range(n-1):
    if a[i]%2 == 0:
        if(a[i]%3 != 0 and a[i]%5 != 0):
            jud = False
            break
if judge:
    print('APPROVED')
else:
    print('DENIED')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
flg = True
for a in A:
  if a % 2 == 0:
    if a % 3 != 0 and a % 5 != 0:
      flg = False
      break
if flg:
  print('APPROVED')
else:
  print('DENIED')
attern = {
        0:["#", "."],
        1:[".", "#"],
    }

    while True:
        (H, W) = [int(i) for i in input().split())]
        if H == W == 0:
            break
        for j in range(H):
            p = pattern[j % 2]
            print (.join([p[i % 2] for i in range(W)]))
            print()

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            if (h + w) % 2 == 0:
                print('#', end='')
            else:
                print('.', end='')

        print()
    print()
x = int(input())
rad = (math.pi / 180) * x

cos = 0
sin = 0
k = 0
while True:
    cos += (math.cos(rad * k))
    sin += (math.sin(rad * k))
    k += 1
    if int(cos) ==0 and int(sin) == 0:
        break
if k == 359:
    k = 360
print(k)

### FIXED CODE ###

import math
from fractions import Fraction

x = int(input())


k = 0
while True:
    k += 1
    s = x * k
    if s % 360 == 0:
        break
print(k)
N,H=map(int,input().split())
ab=[input().split() for i in range(N)]
a = [int(ab[i][0]) for i in range(N)]
maxa = max(a)
b = np.array([int(ab[i][1]) for i in range(N)])
b_effective = b[b > maxa]
d = 0
if sum(b_effective) < Y:
    c = len(b_effective)
    rest = H - sum(b_effective)
    if rest % maxa == 0:
        d = rest//maxa
    else:
        d = rest//maxa + 1
else:
    b = np.sort(b_effective)[::-1]
    s = 0
    for i in range(len(b)):
        s += b[i]
        if s >= Y:
            c = i + 1
            d = 0
            break
print(c+d)

### FIXED CODE ###

import numpy as np
N,H=map(int,input().split())
ab=[input().split() for i in range(N)]
a = [int(ab[i][0]) for i in range(N)]
maxa = max(a)
b = np.array([int(ab[i][1]) for i in range(N)])
b_effective = b[b > maxa]
d = 0
if sum(b_effective) < H:
    c = len(b_effective)
    rest = H - sum(b_effective)
    if rest % maxa == 0:
        d = rest//maxa
    else:
        d = rest//maxa + 1
else:
    b = np.sort(b_effective)[::-1]
    s = 0
    for i in range(len(b)):
        s += b[i]
        if s >= H:
            c = i + 1
            d = 0
            break
print(c+d)