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

k = int(input())
number = 7
cnt = 1
if k % 2 == 0:
    print(-1)
    exit()
for i in range(k):
    if number % k == 0:
        print(cnt)
        exit()
    else:
        cnt += 1
        number = number + 7 * 10 ** (cnt - 1)
print(-1)

### FIXED CODE ###

k = int(input())
mod = 7 % k
cnt = 1
answer = -1

for i in range(k):
    if mod == 0:
        answer = cnt
        break
    else:
        cnt += 1
        mod = (mod * 10 + 7) % k
print(answer)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.full(n, np.inf)

dp[0] = 0
dp[1] = np.abs(h[1] - h[0])

def chmin(a, b):
    if a < b:
        return a
    else:
        return b

for i in range(2, n):
    # for j in range(1, k):
    #     dp[i] = chmin(dp[i], dp[i - j] + np.abs(h[i] - h[i - j]))
    tmp1 = dp[max(i - k, 0):i + 1 - 1]
    tmp2 = np.abs(h[i] - h[max(i - k, 0):i + 1 - 1])
    dp[i] = np.min(tmp1 + tmp2)

print(int(dp[-1]))


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.full(n, np.inf)

dp[0] = 0
dp[1] = np.abs(h[1] - h[0])

# def chmin(a, b):
#     if a < b:
#         return a
#     else:
#         return b

for i in range(2, n):

    # 1回目の投稿：for文。ほぼTLE。遅すぎ。
    # for j in range(1, k):
    #     dp[i] = chmin(dp[i], dp[i - j] + np.abs(h[i] - h[i - j]))
    # 2回目の投稿：ベクトル化。最後4つTLE。少し早いけどまだだめ。
    # tmp1 = dp[max(i - k, 0):i + 1 - 1]
    # tmp2 = np.abs(h[i] - h[max(i - k, 0):i + 1 - 1])
    # dp[i] = np.min(tmp1 + tmp2)
    # 3回目の投稿：
    start = max(i - k, 0)
    dp[i] = np.min(dp[start:i] + np.abs(h[i] - h[start:i]))

print(int(dp[-1]))
### BUGGY CODE ###

z = input().split()

al = int(z[0])
blue = int(z[1])
red = int(z[2])

ans = 0
k = 0

while k <= al - blue -red:
    ans += blue
    k += blue
    k += red

while k <= al-1:
    ans += 1
    k += 1

print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
ab = a + b
m = n // ab
n %= ab
print(m*a+min(n,a))
### BUGGY CODE ###

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

if N == 1:
    print(M)
    exit()

ans = 0
for i in range(1, M+1):
    d, m = divmod(M, i)
    if m == 0 and d >= N:
        ans = i
    if d < N:
        break

print(ans)


### FIXED CODE ###

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


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

K = divisor(M)

ans = 0
for k in K:
    if N * k <= M:
        ans = max(ans, k)


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

def main():
  n,k = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  ans = 0
  if k == 1:
    print(0)
  else:
    for i in range(k-1,n):
      if n-i+1<0:
        break
      if i == k-1:
        c = 1
        ans += (a[i]-a[n-i-1])*c
      else:
        c = c*i//(i-k+1)
        ans += (a[i]-a[n-i-1])*c
    print(ans%1000000007)
if __name__ == "__main__":
  main()

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

from operator import mul
from functools import reduce
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]  
factinv = [1, 1]
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if k == 1:
  print(0)
else:
  for i in range(1,n):
    if n-i < k-1:
      break
    ans += a[n-i]*cmb(n-i,k-1,p)
    ans -= a[i-1]*cmb(n-i,k-1,p)
  print(ans%1000000007)
### BUGGY CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)


### FIXED CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

x = sum(H) // (A+B*(N-1))
H = sorted(H)
 
while len(H):
    nH = [h - B*x for h in H]
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum([h//D + (h%D>0) for h in nH]) <= x:
        print(x)
        break
    else:
        x = max(x+1, sum(H) // (A+B*(N-1)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)
### BUGGY CODE ###

n,k=map(int,input().split())
if k==1 or n%k==0:
    ans=0
else:
    if n/2<k:
        x=abs(n-k)
        y=abs(x-k)
        ans=min(n,min(x,y))
    else:
        while 1:
            x=abs(n-k)
            y=abs(x-k)
            n=min(n,min(x,y))
            if n<k:
                x=abs(n-k)
                y=abs(x-k)
                ans=min(n,min(x,y))
                break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
if k==1 or n%k==0:
    ans=0
else:
    if n/2<k:
        x=abs(n-k)
        y=abs(x-k)
        ans=min(n,min(x,y))
    else:
        x=n%k
        y=abs(x-k)
        ans=min(x,y)
print(ans)
### BUGGY CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = []
for _ in range(M):
    ai = i_inpl()
    a.append(ai)

dp = [None] * (N+1)

dp[N] = 1
# print(dp)
for i in range(N-1, -1, -1):
    if i in a:
        dp[i] = 0
    else:
        if N-1 == i:
            dp[i] = 1
        else:
            if i+1 in a and i+2 in a:
                dp[i] = 0
            elif i+1 in a:
                dp[i] = dp[i+2]
            elif i+2 in a:
                dp[i] = dp[i+1]
            else:
                dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % 1000000007)

### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = { i_inpl(): True for _ in range(M)}
# for _ in range(M):
#     ai = i_inpl()
#     a.append(ai)

dp = [None] * (N+1)

dp[N] = 1
# print(dp)
for i in range(N-1, -1, -1):
    if i in a:
        dp[i] = 0
    else:
        if N-1 == i:
            dp[i] = 1
        else:
            if i+1 in a and i+2 in a:
                dp[i] = 0
            elif i+1 in a:
                dp[i] = dp[i+2]
            elif i+2 in a:
                dp[i] = dp[i+1]
            else:
                dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % 1000000007)
### BUGGY CODE ###

n,m = map(int, input().split())
a = 1
MOD = 1000000007
d = [1] * (n + 1)
for i in range(n):
  d[i+1] = ((m - n + i) * d[i] + i * d[i-1]) % MOD
  a *= (m - i) % MOD
print(a * d[n] % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
a = 1
d = [1] * (n + 1)
for i in range(n):
  d[i + 1] = ((m - n + i) * d[i] + i * d[i - 1]) % MOD
  a = a * (m - i) % MOD
print(a * d[n] % MOD)
### BUGGY CODE ###

K = int(input())
S = input()
s = len(S)
base = 10 ** 9 + 7

L26 = [ 1 for i in range(K+1)] # 26^i mod base 
for i in range(K):
  L26[i+1] = (L26[i] * 26) % base

T1 = 1
T2 = 1
ans = 0
for i in range( s, s+K+1):
  T3 = L26[K + s - i]
  #T4 = pow(26, K + s - i, base)
  #print(T3, T4)
  p = (T1 * T2) % base
  p = (p * T3) % base
  ans += p
  ans %= base
  #print(ans, T1, T2, T3)
  T1 *= 25
  T1 %= base
#  T2 = (T2 * i ) // (i+1-s) # T2 = (i, s-1) = (i-1, s-1) * i // (i+1-s)
  T2 *= i
  T2 %= base
  T2 *= pow(i+1-s, base-2, base)
  T2 %= base
  
print(ans % base)

### FIXED CODE ###

K = int(input())
S = input()
s = len(S)
base = 10 ** 9 + 7

L26 = [ 1 for i in range(K+1)] # 26^i mod base 
for i in range(K):
  L26[i+1] = (L26[i] * 26) % base

T1 = 1
T2 = 1
ans = 0
for i in range( s, s+K+1):
  T3 = L26[K + s - i]
  #T4 = pow(26, K + s - i, base)
  #print(T3, T4)
  p = (T1 * T2) % base
  p = (p * T3) % base
  ans += p
  ans %= base
  #print(ans, T1, T2, T3)
  T1 *= 25
  T1 %= base
#  T2 = (T2 * i ) // (i+1-s) # T2 = (i, s-1) = (i-1, s-1) * i // (i+1-s)
  T2 *= i
  T2 %= base
  T2 *= pow(i+1-s, base-2, base)
  T2 %= base
  
print(ans % base)
### BUGGY CODE ###

from operator import mul
from functools import reduce

# A, B = tuple(map(int, input().split()))
N = int(input())
list_A = list(map(int, input().split()))

result = reduce(mul, list_A)
threshold = 10 ** 18

if result > threshold:
    print(-1)
else:
    print(result)


### FIXED CODE ###

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

if 0 in list_A:
    print(0)
    exit()

result = 1
for a in list_A:
    result *= a
    if result > 1e18:
        print(-1)
        exit()

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

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


N, K = inp_list()
h = inp_list()
h = np.array(h)

dp = np.array([10 ** 9] * N)
dp[0] = 0

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

# print(dp)
print(dp[-1])


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


def lcm(x, y): return (x * y) // gcd(x, y)

N, K = inp_list()
h = inp_list()

dp = [INF] * N
dp[0] = 0 # initial condition
# 計算量: O(NK)
for i in range(N - 1):
    for j in range(i + 1, i + K + 1):
        if j > N - 1: break
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j])) # recurrence formula
    
print(dp[N - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 0
for i in range(n):
  m += a[i]*sum(a[i+1:])
  m = m%(10**9+7)
print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sum([(i**2) for i in a])
print(((sum(a)**2-b)//2)%(10**9+7))
### BUGGY CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline

# sys.setrecursionlimit(100000)


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

    dp = [[-1 for _ in range(N+1)] for _ in range(W+1)]

    def knapsack(capacity, value, idx):
        if dp[capacity][idx] != -1:
            return dp[capacity][idx]
        if idx < 0 or W < 0:
            return value
        if items[idx][0] > capacity:
            dp[capacity][idx] = knapsack(capacity, value, idx - 1)
            return dp[capacity][idx]
        else:
            dp[capacity][idx] = max(
                knapsack(capacity, value, idx - 1),
                knapsack(capacity - items[idx][0],
                         value, idx-1) + items[idx][1]
            )
            return dp[capacity][idx]

    knapsack(W, 0, N - 1)
    return max(dp[-1])


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


### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


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

N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
  else:
    ki = dps.index(d)
    break
RP = (N-ki) // len(dps[ki:])
mod = (N-ki) % len(dps[ki:])
rt = sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod])
print(rt)

### FIXED CODE ###

n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
### BUGGY CODE ###

N,T = input().split(' ')
p = input().split(' ')

def E_cal(i):
    return (i*(i+1))/(2*i)

Es=[]

for i in p:
    Es.append(E_cal((int)(i)))
#print(Es)
TEs_max = 0
for j in range((int)(N)-(int)(T)+1):
    sum_E=0
    for k in range((int)(T)):
        sum_E+=Es[k+j]

    if TEs_max<sum_E:
        TEs_max = sum_E
    #print(sum_E)

print(TEs_max)

### FIXED CODE ###

N,T = input().split(' ')
ps = input().split(' ')
N=(int)(N)
T=(int)(T)

def E_cal(i):
    return (i+1)/2

Es=[]

ruiseki_sum=[0]

for i,p in enumerate(ps):
    Es.append(E_cal((int)(p)))
    ruiseki_sum.append(Es[i]+ruiseki_sum[i])

#print(Es)
#print(ruiseki_sum)
TEs_max = 0

for j in range(N-T+1):
    now = ruiseki_sum[j+T]-ruiseki_sum[j]
    if now>TEs_max:
        TEs_max=now
    #print(now)
print(TEs_max)
### BUGGY CODE ###

def strKey(key):
    if key == 0:
        return '000'
    if 1<= key <= 9:
        return '00' + str(key)
    if 10<= key <=99:
        return '0' + str(key) 
    return str(key)

N = int(input())
s  = input().strip()

cnt = 0
for key in range(1000):
    key = strKey(key)    #; print(key)
    isFlag = False
    for i0 in range(N-2):
        if isFlag == False and s[i0] == key[0]:
            for i1 in range(i0+1, N-1):
                if isFlag == False and s[i1] == key[1]:
                    for i2 in range(i1+1, N):
                        if s[i2] == key[2]:
                            cnt += 1     #; print(i0, i1, i2, key)
                            isFlag = True
                            break
                        
print(cnt)            

### FIXED CODE ###

N = int(input())
s  = input().strip()

cnt = 0
for key in range(1000):
    key = '{:0>3}'.format(str(key))    #; print(key)
    i0 = s.find(key[0])
    if 0 <= i0 < N-2:
        i1 = s.find(key[1], i0+1)
        if 0 < i1 < N-1:
            i2 = s.find(key[2], i1+1)
            if i2 != -1:
                cnt += 1
            else:
                continue
        else:
            continue        
    else:
        continue
                                   
print(cnt)
### BUGGY CODE ###

import math
K = int(input())
ans = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        t = math.gcd(a,b)
        for c in range(1,K+1):
            ans += math.gcd(t,c)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())

cost = [[float('inf')]*n for _ in range(n)]
for a,b,c in abc:
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

def dijkstra(start,num_v,cost):
    d = [float('inf')]*n
    used = [False]*n
    d[start] = 0

    while 1:
        v = -1
        for i in range(num_v):
            if not used[i] and v == -1:
                v = i
            elif not used[i] and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j],d[v] + cost[v][j])
    return d
d = dijkstra(k-1,n,cost)
for _ in range(q):
    x,y = map(int,input().split())
    print(d[x-1] + d[y-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())

g = [[] for _ in range(n)]
for a,b,c in abc:
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))

que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

for _ in range(q):
    x,y = map(int,input().split())
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=max(L[:d])-min(L[:d])
for i in range(c-d+1):
    if max(L[i:i+d])-min(L[i:i+d])<x:
        x=max(L[i:i+d])-min(L[i:i+d])
print(x)

### FIXED CODE ###

a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=L[d-1]-L[0]
for i in range(c-d+1):
    if L[d+i-1]-L[i]<x:
        x=L[d+i-1]-L[i]
print(x)
### BUGGY CODE ###

n = int( raw_input() )
A = map( int , raw_input().strip().split(' ') )
q = int( raw_input() )
mi = map( int , raw_input().strip().split(' ') )

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

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

### FIXED CODE ###

n = input()
A = map( int , raw_input().split() )
q = input()
mi = map( int , raw_input().split() )

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

  res = solve( i+1 , m ) or solve( i+1 , m-A[i] )
  return res

for m in mi:
  if solve( 0 , m ): print "yes"
  else: print "no"
### BUGGY CODE ###

import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            else:
                battle_dict.pop(i)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            else:
                battle_dict.pop(j)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

import numpy as np

def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    
    dp = [float("inf")] * (H+1)
    dp[0] = 0

    for i in range(N):
        for j in range(H+1):
            if j + A[i] <= H:
                dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])
            else:
                dp[H] = min(dp[H], dp[j]+B[i])

    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    
    dp = [float("inf")] * (H+1)
    dp[0] = 0

    for i in range(N):
        for j in range(H+1):
            if j + A[i] <= H:
                dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])
            else:
                dp[H] = min(dp[H], dp[j]+B[i])

    print(dp[H])


if __name__ == "__main__":
    main()