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

import sys
import math
from collections import deque
from collections import defaultdict

def comb(n, r, mod):
    X, Y = 1, 1
    for i in range(r):
        X = X * (n - i)
        Y = Y * (r - i)
    return X * pow(Y, mod-2, mod)

def main():
    n,a,b = list(map(int,sys.stdin.readline().split()))
    mod = 10**9 + 7
    ans = pow(2, n, mod) - 1
    ans = (ans - comb(n, a, mod) - comb(n, b, mod)) % mod
    print(ans)

    return 0

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import defaultdict

def comb(n, r, mod):
    X, Y = 1, 1
    for i in range(r):
        X = X * (n - i) % mod
        Y = Y * (r - i) % mod
    return X * pow(Y, mod-2, mod)

def main():
    n,a,b = list(map(int,sys.stdin.readline().split()))
    mod = 10**9 + 7
    ans = pow(2, n, mod) - 1
    ans = (ans - comb(n, a, mod) - comb(n, b, mod)) % mod
    print(ans)
    return 0

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

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, y, x, q):
    s = stay[y, x]
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q + s:
                Q[ny, nx] = q + s
                dfs(N, Q, stay, ny, nx, q + s)


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.int32)
    
    for i in range(N):
        for j in range(N):
            Q[i, j] = min([i, j, N-1-i, N-1-j])

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        q = Q[y, x]
        stay[y, x] = 0
        ans += q
        dfs(N, Q, stay, y, x, q)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = np_solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))
### BUGGY CODE ###

N = int(input())
list_b = list(map(int, input().split()))
aaa = []
ans = []
for i in range(N):
  if i == 0:
    aaa.append(1)
    ans.append(1)
  elif i == 1:
    s = []
    f = []
    for h in range(i+1):
      a = aaa.copy()
      b = ans.copy()
      a.insert(h, h+1)
      b.append(h+1)
      s.append(a)
      f.append(b)
    aaa = s
    ans = f
  else:
    j = []
    f = []
    for d in range(len(aaa)):
      s = []
      t = []
      for k in range(i+1):
        a = aaa[d].copy()
        b = ans[d].copy()
        a.insert(k, k+1)
        b.append(k+1)
        s.append(a)
        t.append(b)
      j += s
      f += t
    aaa = j
    ans = f

if list_b in aaa:
  index = aaa.index(list_b)
  anser = ans[index]
  for i in range(N):
    print(anser[i])
else:
  print('-1')

### FIXED CODE ###

N = int(input())
list_b = list(map(int, input().split()))
ans = [0 for i in range(N)]

finish = False

for i in range(N-1, -1, -1):
  mx = -1
  for k in range(i+1):
    if list_b[k] == k+1:
      mx = max(mx, k+1)
  if mx == -1:
    finish = True
    break
  else:
    ans[i] = mx
    for j in range(mx-1, i):
      list_b[j] = list_b[j+1]
    
if not finish:
    for i in range(N):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
import copy
import math
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))

# 一度照らされると二度目以降は確実に照らされるはず。
for i in range(K):
    # j番目の電球を操作
    B = np.array([0] * N)
    for j in range(N):
        maxA = int(j + A[j] + 0.5)
        minA = math.ceil(j - A[j] - 0.5)

        for k in range(max(0, minA), min(N, maxA + 1)):
            B[k] += 1
    A = B.copy()

for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from fractions import Fraction
    n = int(readline())
    k = Fraction(4, n)
    kd = k - Fraction(1, 3500)

    for a in range(1, 3501):
        p = Fraction(1, a)
        for b in range(a, 3501):
            q = Fraction(1, b)
            x = p + q
            if x > kd:
                break
            ok = 3500
            ng = 0
            while abs(ng - ok) > 1:
                mid = (ok + ng) // 2
                y = x + Fraction(1, mid)
                if y > k:
                    ng = mid
                else:
                    ok = mid
            if x + Fraction(1, ok) == k:
                return print(a, b, ok)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())

    for a in range(1, 3501):
        for b in range(1, 3501):
            nu = n * a * b
            dn = 4 * a * b - n * (a + b)
            if dn > 0 and nu % dn == 0:
                return print(a, b, nu // dn)


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

N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

dp[1][0] = 100-p[1]
dp[1][1] = p[1]

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく


ans = 0

for k in range(-(-N//2), N+1):
    ans += dp[N][k]

print(ans/10**(2 * N))

### FIXED CODE ###

import numpy as np

N = int(input())
p = [0] + list(map(float, input().split()))

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

dp[1, 0] = 1-p[1]
dp[1, 1] = p[1]

for i in range(2, N + 1):
    dp[i] = np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (1-p[i])
    #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
    #つまり，dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i])
    #numpyを使ってベクトル漸化式と見ることで，for_loopを一層分解消。
    #print(i, j, dp[i][j])

ans = 0

for k in range(-(-N//2), N+1):
    ans += dp[N, k]

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

n=int(input())
a=list(input().split())
b=[]
if n%2==0:
    for i in range(n):
        if i==0:
            b.append(a[i])
        elif i%2==0:
            b.append(a[i])
        else:
            b.insert(0,a[i])
else:
    for i in range(n):
        if i==0:
            b.append(a[i])
        elif i%2==0:
            b.insert(0,a[i])
        else:
            b.append(a[i])
print(' '.join(b))


### FIXED CODE ###

n=int(input())
a=list(input().split())
b=a[::-2]+a[len(a)%2::2]
print(' '.join(b))
### BUGGY CODE ###

import itertools
n, m, q = map(int, input().split())
values = [list(map(int, input().split())) for _ in range(q)]

nums = []
for i in range(m):
    tmp = [i + 1] * n
    nums.extend(tmp)
ans = 0
for comb in itertools.combinations(nums, n):
    tmp = 0
    for a, b, c, d in values:
        if comb[b - 1] - comb[a - 1] == c: tmp += d
    ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

import itertools
n, m, q = map(int, input().split())
values = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp = 0
    for a, b, c, d in values:
        if comb[b - 1] - comb[a - 1] == c: tmp += d
    ans = max(tmp, ans)
print(ans)
### BUGGY CODE ###

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


floor_num=[]

if N >=B:
    floor_num.append(int(A*(B-1)/B))
else:  
    for x in range(0,N+1):

        floor_num.append(int(A*x/B)-A*int(x/B))

    if N >=B:
        floor_num.append(int(A*(B-1)/B))

print(max(floor_num))


### FIXED CODE ###

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


floor_num=[]

if N >=B:
    floor_num.append(int(A*(B-1)/B))
else:  

        floor_num.append(int(A*N/B))


print(max(floor_num))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 1001001001
dp = [inf for _ in range(n + 1)]

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

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


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 1001001001
dp = [inf] * (n+1)

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

for i in range(n):
    for j in range(k):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], dp[i-1] + abs(h[i+j] - h[i-1]))
print(dp[n-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.append(0)
a.insert(0,0)
diff=[]
for i in range(0,n+1):
	diff.append(a[i+1]-a[i])
for i in range(0,n):
	ans = 0
	for j in range(0,n+1):
		if j==i+1:
			continue
		if j==i:
			ans+=abs(diff[j]+diff[j+1])
		else:
			ans+=abs(diff[j])
	print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.append(0)
a.insert(0,0)
diff=[]
sum=0
for i in range(0,n+1):
	diff.append(a[i+1]-a[i])
	sum+=abs(diff[i])
for i in range(0,n):
	ans=sum+abs(diff[i]+diff[i+1])-(abs(diff[i])+abs(diff[i+1]))
	print(ans)
### BUGGY CODE ###

from copy import deepcopy
def main():
  h,w,k=map(int,input().split())
  grid=[list(input()) for _ in range(h)]
  def score(t):
    total=0
    for i in range(1,h):
      for j in range(w-1):
        cnt=1
        ten=int(gc[i][j])
        while gc[i][j+1]==gc[i][j]:
          cnt+=1
          j+=1
          if j==w-1:
            break
        if cnt>=k:
          total+=2**t*(ten*cnt)
          gc[i][j-cnt+1:j+1]=['0']*cnt
    return total
  def upd():
    while 1:
      ok=True
      for i in range(1,h):
        for j in range(w):
          if gc[i][j]=='0' and gc[i-1][j]!='0':
            x=gc[i-1][j]
            gc[i-1][j]='0'
            gc[i][j]=x
            ok=False
      if ok:
        return
  ans=0
  for i in range(1,h):
    for j in range(w):
      gc=deepcopy(grid)
      gc[i][j]='0'
      t=0
      res=0
      while 1:
        upd()
        total=score(t)
        if total==0:
          break
        t+=1
        res+=total
      ans=max(ans,res)
  return print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

from copy import deepcopy
import sys
def main():
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  grid=[]
  for _ in range(h):
    s=input().rstrip()
    s=list(s)
    s=list(map(int,s))
    grid.append(s)
  def score(t):
    total=0
    for i in range(1,h):
      for j in range(w-1):
        cnt=1
        ten=gc[i][j]
        while gc[i][j+1]==gc[i][j]:
          cnt+=1
          j+=1
          if j==w-1:
            break
        if cnt>=k:
          total+=2**t*(ten*cnt)
          gc[i][j-cnt+1:j+1]=[0]*cnt
    return total
  def upd():
    while 1:
      ok=True
      for i in range(1,h):
        for j in range(w):
          if gc[i][j]==0 and gc[i-1][j]!=0:
            x=gc[i-1][j]
            gc[i-1][j]=0
            gc[i][j]=x
            ok=False
      if ok:
        return
  ans=0
  for i in range(1,h):
    for j in range(w):
      gc=deepcopy(grid)
      gc[i][j]=0
      t=0
      res=0
      while 1:
        upd()
        total=score(t)
        if total==0:
          break
        t+=1
        res+=total
      ans=max(ans,res)
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import math
import collections


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))

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

cnt = collections.Counter(a)
ans = {}
for key1 in cnt.keys():
    ans[key1] = sum(nc2(value) if key1 != key2 else nc2(value-1) for key2, value in cnt.items())
for v in a:
    print(ans[v])


### FIXED CODE ###

import math
import collections


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))


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

cnt = collections.Counter(a)
each_ans = {}
for key, value in cnt.items():
    t = nc2(value)
    each_ans[key] = (t, t-value+1)
all_sum = sum(value[0] for _, value in each_ans.items())
ans = {}
for key in cnt.keys():
    ans[key] = all_sum - each_ans[key][0] + each_ans[key][1]
for i in a:
    print(ans[i])
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
import numpy as np

n = int(input())
a =[int(i) for i in input().split()] 

A = 0
for i in range(n):
  aa = np.asarray(a)
  a_del = np.delete(a, i, 0)
  List = list(a_del)
  
  G = reduce(gcd,List)
  #print(G)
  A = max(A,G)
print(A)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = [int(x) for x in input().split(' ')]

L=[0]
for i in range(n):
  L.append(gcd(L[i],a[i]))

R=[0]
for i in range(n):
  R.append(gcd(R[i],a[n-i-1]))
  
M=[0]
for i in range(n):
  M.append(gcd(L[i],R[n-i-1]))
  
print(max(M))
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [input() for i in range(H)]
dp_holi = [[0] * W for i in range(H)]
dp_ver = [[0] * W for i in range(H)]


#まずは水平方向について数える
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            if j - 1 < 0 or maze[i][j -1] == "#":
                tmp = 0
                flag = False
                for k in maze[i][j:]:
                    if k == ".":
                        tmp += 1
                        flag = True
                    else:
                        dp_holi[i][j] = tmp
                        break
                if flag:
                    dp_holi[i][j] = tmp
            elif maze[i][j - 1] == ".":
                dp_holi[i][j] += dp_holi[i][j - 1]

#垂直方向にも同じことをする
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            if i - 1 < 0 or maze[i -1][j] == "#":
                tmp = 0
                flag = False
                for k in range(i, H):
                    if maze[k][j] == ".":
                        tmp += 1
                        flag = True
                    else:
                        dp_ver[i][j] += tmp
                        flag = False
                        break
                if flag:
                    dp_ver[i][j] += tmp
            elif i - 1 < 0:
                continue
            elif maze[i - 1][j] == ".":
                dp_ver[i][j] += dp_ver[i - 1][j]

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp_holi[i][j] + dp_ver[i][j] - 1)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
maze = [input() for i in range(H)]
dp_holi = [[0] * W for i in range(H)]
dp_ver = [[0] * W for i in range(H)]


#まずは水平方向について数える
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            if j - 1 < 0 or maze[i][j -1] == "#":
                tmp = 0
                flag = False
                for k in maze[i][j:]:
                    if k == ".":
                        tmp += 1
                        flag = True
                    else:
                        dp_holi[i][j] = tmp
                        break
                if flag:
                    dp_holi[i][j] = tmp
            elif maze[i][j - 1] == ".":
                dp_holi[i][j] += dp_holi[i][j - 1]

#垂直方向にも同じことをする
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            if i - 1 < 0 or maze[i -1][j] == "#":
                tmp = 0
                flag = False
                for k in range(i, H):
                    if maze[k][j] == ".":
                        tmp += 1
                        flag = True
                    else:
                        dp_ver[i][j] += tmp
                        flag = False
                        break
                if flag:
                    dp_ver[i][j] += tmp
            elif i - 1 < 0:
                continue
            elif maze[i - 1][j] == ".":
                dp_ver[i][j] += dp_ver[i - 1][j]

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp_holi[i][j] + dp_ver[i][j] - 1)
print(ans)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)

for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        q = heapq.heappop(A)
        if q < c:
            heapq.heappush(A, c)
        else:
            heapq.heappush(A, q)
            break
print(sum(A))

### FIXED CODE ###

import  heapq

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

heapq.heapify(A)
B_C_list = []
for i in range(M):
    B, C = map(int, input().split())
    B_C_list.append((B, C))

B_C_list.sort(reverse=True, key=lambda x: x[1])
# print(B_C_list)

for B_C in B_C_list:
    a = heapq.heappop(A)
    if a >= B_C[1]:
        heapq.heappush(A, a)
        break
    else:
        heapq.heappush(A, a)
        for j in range(B_C[0]):
            a = heapq.heappop(A)
            if a >= B_C[1]:
                heapq.heappush(A, a)
                break
            heapq.heappush(A, B_C[1])
print(sum(A))
### BUGGY CODE ###

import numpy as np
n, m, k = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]
B = [int(n) for n in input().split()]

A = np.cumsum([0] + A)
B = np.cumsum([0] + B)
n_read = 0
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B):
        if a + b > k:
            break
        if n_read < i + j:
            n_read = i + j
print(n_read)

### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
D = [sum(p[i:i+K]) for i in range(N-K+1)]
print(max(D) / 2 + 0.5 * K)

### FIXED CODE ###

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

import sys
from collections import deque
from collections import  Counter
import statistics
import math

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, len(s)):
        if s[i:j+1] not in li:
            li.append(s[i:j+1])
li.sort()
print(li[k-1])

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
k = ni()
li = []
for i in range(len(s)):
    for j in range(i, i+k+1):
        li.append(s[i:j+1])
li = list(set(li))
li.sort()
print(li[k-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
# 大きい方から試したいので逆順でループ回す
for i in range((1 << len(aN2))-1, -1, -1):
    # 全部合わせても足りないようじゃ論外
    if sum(aN2) < K:
        break
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
    # 最後まで足りなかったら、これ以降も足りないので終了
    else:
        break
print(need.count(False))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

o=lambda:map(int,raw_input().split())
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if ~l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print a


### FIXED CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
T,F=True,False
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=T
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=T
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(T)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[F]*n;dfs(i,j);ans=min(ans,dfs(j,i))
else:
    for i in range(n):vis=[F]*n;ans=min(ans,dfs(i,-1))
print ans