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

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
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
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)


### FIXED CODE ###

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
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
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

count = int(input())
list = input().split(" ")
state = False
i = 0
num = int(list[i])
i += 1
limit = 10 ** 18

while i < count:
  num = num * int(list[i])   
  i += 1
if num > limit:
  print(-1)
else:
  print(num)

### FIXED CODE ###

count = int(input())
list = input().split(" ")
state = False
i = 0
num = int(list[i])
i += 1
limit = 10 ** 18
if "0" in list:
  num = 0
  count = 0

while i < count:
  num = num * int(list[i])

  if num > limit:
    print(-1)
    state = True
    break
    
  i += 1

if not state:
  print(num)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

ans = [0] * (N - 1)
for i in range(N):
    for j in range(i + 1, N):
        dist = min(abs(i - j), abs((X - 1) - i) + abs((Y - 1) - j) + 1, abs((Y - 1) - i) + abs((X - 1) - j) + 1)
        ans[dist - 1] += 1
        # print("i:{}, j:{}, dist:{}".format(i, j, dist))
for k in ans:
    print(k)


### FIXED CODE ###

N, X, Y = map(int, input().split())

X -= 1
Y -= 1

ans = [0] * (N - 1)
for i in range(N):
    for j in range(i + 1, N):
        dist = min(abs(i - j), abs(X - i) + abs(Y - j) + 1, abs(Y - i) + abs(X - j) + 1)
        ans[dist - 1] += 1
        # print("i:{}, j:{}, dist:{}".format(i, j, dist))
for k in ans:
    print(k)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

lr = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)

lr.sort(key=lambda x:(x[0],x[1]))
l = [z[0] for z in lr]

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp2 = [z[1] for z in lr[idxl:]]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

def gcd(a,b):
	c = a % b
	if c == 0:
		return b
	return gcd(b, c)

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

lis = []
ans = 0

for i in range(N):
	lis = []
	for j in range(N):
		if i != j:
			lis.append(A[j])
	tmp = lis[0]
	for i in range(len(lis)-1):
		tmp = gcd(tmp,lis[i+1])
	ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
 
l = [0]*(N+1)
r = [0]*(N+1)

for i in range(N):
	l[i+1] = gcd(l[i], A[i])
for i in reversed(range(N)):	
	r[i] = gcd(r[i+1],A[i])

ans = 0
for i in range(N):
	ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [tuple((int(_x), int(_y) if _c == "W" else int(_y) + k)) for (_x, _y, _c) in xyc]
xy = [tuple((_x % (2 * k), _y % (2 * k))) for (_x, _y) in xy]

ans = np.zeros((2 * k, 2 * k), dtype=np.int32)
for _x, _y in xy:
    if (_x - k + 0.5) * (_y - k + 0.5) > 0:
        _x %= k
        _y %= k
        ans[_x, _y] += 1
        ans[_x + k, _y] -= 1
        ans[_x, _y + k] -= 1
        ans[_x + k, _y + k] += 1
        ans[_x + k, _y + k] += 1
        ans[_x + k, 0] += 1
        ans[_x + k, _y] -= 1
        ans[0, _y + k] += 1
        ans[_x, _y + k] -= 1
        ans[0, 0] += 1
        ans[_x, 0] -= 1
        ans[0, _y] -= 1
        ans[_x, _y] += 1
    else:
        _x %= k
        _y %= k
        ans[_x, _y] -= 1
        ans[_x + k, _y] += 1
        ans[_x, _y + k] += 1
        ans[_x + k, _y + k] -= 1
        ans[_x + k, _y + k] -= 1
        ans[_x + k, 0] -= 1
        ans[_x + k, _y] += 1
        ans[0, _y + k] -= 1
        ans[_x, _y + k] += 1
        # ans[0, 0] -= 1
        ans[_x, 0] += 1
        ans[0, _y] += 1
        ans[_x, _y] -= 1
print(np.max(ans.cumsum(axis=1).cumsum(axis=0)))


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}


def create_bound(p, K, ub):
    if p - K + 1 >= 0:
        return [(p - K + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - K + 1) % ub, ub)]


for i in range(N):
    x, y, c = input().split()
    nx = int(x) % ub
    ny = (int(y) + ADD[c]) % ub
    for add in [0, K]:
        for xlb, xub in create_bound((nx + add) % ub, K, ub):
            for ylb, yub in create_bound((ny + add) % ub, K, ub):
                b[xlb][ylb] += 1
                b[xlb][yub] -= 1
                b[xub][ylb] -= 1
                b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
    b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
    b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
### BUGGY CODE ###

import sys
def main():
	S=input()
	Q=int(sys.stdin.readline())
	flag=0
	for i in range(Q):
		qu=input()
		if qu[0]=='1':
			if flag==0:
				flag+=1
			else:
				flag=0
		else:
			if qu[2]=='1' and flag==0:
				S=qu[4]+S
			elif qu[2]=='1' and flag==1:
				S+=qu[4]
			elif qu[2]=='2' and flag==0:
				S+=qu[4]
			else:
				S=qu[4]+S
	if flag==1:
		S=S[::-1]
	print(S)
if __name__=='__main__':
	main()

### FIXED CODE ###

import sys
from collections import deque
S=[input()]
S=deque(S)
Q=int(sys.stdin.readline())
flag=0
for i in range(Q):
	qu=tuple(input().split())
	if qu[0]=='1':
		if flag==0:
			flag+=1
		else:
			flag=0
	else:
		if qu[1]=='1' and flag==0:
			S.appendleft(qu[2])
		elif qu[1]=='1' and flag==1:
			S.append(qu[2])
		elif qu[1]=='2' and flag==0:
			S.append(qu[2])
		elif qu[1]=='2' and flag==1:
			S.appendleft(qu[2])
if flag==1:
	S=''.join(S)
	S=S[::-1]
	print(S)
	exit()
print(''.join(S))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
dp=[[-10**18]*n for _ in range(m)]
if n%2==0:
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+a[j])
else:
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    #print(j)
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+a[j])
print(max(dp[-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
if n%2==0:
    dp=[[-10**18]*2 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j%2]=max(dp[i][j%2],dp[i-1][k%2]+a[j])
else:
    dp=[[-10**18]*3 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    dp[i][j-2*i]=max(dp[i][j-2*i],dp[i-1][k-2*(i-1)]+a[j])
print(max(dp[-1]))
### BUGGY CODE ###

N = int(input())

r = 0

for i in range(N):
    m = i + 1
    j = int(N/(m))
    r = r + int(m*j*(1+j)/2)

print(r)    

### FIXED CODE ###

N = int(input())
M = 0
r = 0
if N>1000000:
    M = N


for i in range(min(N,1000000)):
    m = i + 1
    j = int(N/(m))
    r = r + int(m*j*(1+j)/2)

if M!=0:
    for i in range(10):
        k = int(M/(i+1))
        if k > 1000000:
            r = r + (i+1)*int((k-1000000)*(k+1000001)/2)

print(r)
### BUGGY CODE ###

def duplicate_check(value, value_list):
	if value_list.count(value) == 2:
		while value in value_list: value_list.remove(value)
	return (value_list)

value_list = []
result_list = []
number_of_test = int(input())
while True:
	try:
		value = int(input())
		value_list.append(value)
		result_list = duplicate_check(value, value_list)
	except EOFError:
		break
print(len(result_list))


### FIXED CODE ###

import collections

cnt = int(input())
array = []
for i in range(cnt):
    array.append(int(input()))
cnt_dict = collections.Counter(array)

res = 0
for j in cnt_dict.values():
    if j % 2 != 0:
        res += 1
print(res)
### BUGGY CODE ###

from collections import defaultdict
from itertools import product

n = int(input())
if n < 3:
    print(0)
else:
    rt = int(n ** 0.5)
    factors = defaultdict(int)
    N = n
    n_div = 2
    while n > 1:
        while not n % n_div:
            factors[n_div] += 1
            n = n // n_div
        n_div += 1
        if (n_div == rt+ 2) and (n == N):
          factors[N] += 1
          break
    lis = [1]
    for k, v in factors.items():
        facts = [k ** i for i in range(v + 1)]
        it = product(lis, facts)
        lis = [a * b for a, b in it]
    nums = [l - 1 for l in lis if l - 1]
    nums = [i for i in nums if (N //i) == (N % i)]
    print(sum(nums))


### FIXED CODE ###

from collections import defaultdict
from itertools import product

n = int(input())
if n < 3:
    print(0)
else:
    rt = int(n ** 0.5)
    factors = defaultdict(int)
    N = n
    n_div = 2
    while n > 1:
        if n_div == int(n ** 0.5) + 2:
            factors[n] += 1
            break
        while not n % n_div:
            factors[n_div] += 1
            n = n // n_div
        n_div += 1
    lis = [1]
    for k, v in factors.items():
        facts = [k ** i for i in range(v + 1)]
        it = product(lis, facts)
        lis = [a * b for a, b in it]
    nums = [l - 1 for l in lis if l - 1]
    nums = [i for i in nums if (N //i) == (N % i)]
    print(sum(nums))
### BUGGY CODE ###

N, Y = map(int,input().split())
t = Y//1000+1
counter = 0
if counter==0:
    
    for i in range(t):
        if counter==0:
        
            for j in range(t):
                if counter==0:
                    for k in range(t):
                        if (10000*i+5000*j+1000*k)==Y and (i+j+k)==N and counter == 0:
                            counter+=1
                            print(i, j, k)
                            break

            
if counter == 0:
    print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int,input().split())#調べる要素が少ないものからループしないと実行時間が間に合わない。
counter = 0
if counter==0:
    for i in range(Y//10000+1):
        if counter==0:   
            for j in range((Y-10000*i)//5000+1):
                    if (10000*i+5000*j+1000*(N-i-j))==Y and counter == 0 and N-i-j>=0:
                        counter+=1
                        print(i, j, (N-i-j))
                        break
if counter == 0:
    print(-1, -1, -1)
### BUGGY CODE ###

import queue
def main():
    n,m,k=map(int,input().split())
    root=[[0]*n for i in range(n)]
    for i in range(n):
        root[i][i]=2
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1][b-1]=1
        root[b-1][a-1]=1
    for i in range(k):
        a,b=map(int,input().split())
        root[a-1][b-1]=-float("inf")
        root[b-1][a-1]=-float("inf")
    toVis=queue.Queue()
    Visted=[]
    
    checkOK=[0]*n
    OK={}
    checkVis=[0]*n
    checkVinit=[0]*n
    for i in range(n):
        if checkOK[i]==5:
            continue
        checkVis=checkVinit
        Visted=[i]
        checkVis[i]=5
        toVis=queue.Queue()
        
        for j in range(len(root[i])):
            nex=root[i][j]
            if checkVis[j]!=5 and nex==1:
                toVis.put(j)

        while toVis.empty()==False:
        
            now=toVis.get()

            if checkVis[now]==5:
                continue

            Visted.append(now)
            checkVis[now]=5
            for j in range(n):#len(rooot[now]
                nex=root[now][j]
                if nex==1 and checkVis[j]!=5:
                    toVis.put(j)
    
        for j in Visted:
            OK[j]=Visted
            checkOK[j]=5
    ans=[]
    for i in range(n):
        num=0
        for value in OK[i]:
            if root[i][value]==0:
                num+=1
        ans.append(num)
    print(" ".join(map(str,ans)))
if __name__=="__main__":
    main()

    

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
mod = 998244353

facs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac

s = 0
for i in range(K+1):
    d = facs[N-1] * pow(facs[i], mod-2, mod) * pow(facs[N-1-i], mod-2, mod) \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

### FIXED CODE ###

N, M, K = map(int, input().split())
mod = 998244353

facs = [1] * N
invs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

s = 0
for i in range(K+1):
    d = facs[N-1] * invs[i] * invs[N-1-i] \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)
### BUGGY CODE ###

n=int(input())
v=input().split()
o=[("0",0)]
e=[("0",0)]
for i in range(n//2):
    for j in range(len(o)):
        if v[2*i]==o[j][0]:
            o[j]=(o[j][0],o[j][1]+1)
            break
        elif j==len(o)-1:
            o.append((v[2*i],1))
    for k in range(len(e)):
        if v[2*i+1]==e[k][0]:
            e[k]=(e[k][0],e[k][1]+1)
            break
        elif k==len(e)-1:
            e.append((v[2*i+1],1))
o.sort(key=lambda x:x[1])
e.sort(key=lambda x:x[1])
if o[-1][0]==e[-1][0]:
    if o[-1][1]<e[-1][1]:
        m=e[-1][1]+o[-2][1]
    else:
        m=o[-1][1]+e[-2][1]
else:
    m=o[-1][1]+e[-1][1]
print(n-m)


### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
o={0:0}
e={0:0}
n=1
for i,v in enumerate(V):
    if n:
        if v in o.keys():
            o[v]+=1
        else:
            o[v]=1
    else:
        if v in e.keys():
            e[v]+=1
        else:
            e[v]=1
    n=1-n
O=sorted(o.items(),key=lambda x:-x[1])
E=sorted(e.items(),key=lambda x:-x[1])
if O[0][0]==E[0][0]:
    m=max(O[0][1]+E[1][1],E[0][1]+O[1][1])
else:
    m=O[0][1]+E[0][1]
print(N-m)
### BUGGY CODE ###

k, s = map(int, input().split())
x = [n for n in range(0, k+1)]
y = [m for m in range(0, k+1)]
z = [l for l in range(0, k+1)]
cnt = 0

for i in range(k+1):
    for j in range(k+1):
        for t in range(k+1):
            if(x[i] + y[j] + z[t] == s):
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - (x+y)
        if(z >= 0 and z <= k):
            cnt += 1
print(cnt)
### BUGGY CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
    
dp = [[10**50 for i in range(10**10)]for j in range(N+100)]
dp[0][v[0]] = m[0]
for i in range(N):
    for j in range(sum(v)+1):
        if j == 0:
            dp[i][j] = 0
        if dp[i][j] != 10**50:
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break


### FIXED CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]

tree = {i:[] for i in range(1, N+1)}
for a, b in ab:
    tree[a].append(b)
    tree[b].append(a)

stree = sorted(tree.items(), key=lambda x: -len(x[1]))
print(len(stree[0][1]))
start = stree[0][0]

colormap = {i:[0]*(N+1) for i in range(1, N+1)}
from collections import deque
q = deque([start])
visited = {start}
while q:
    n = q.popleft()
    for p in tree[n]:
        if p in visited:
            continue
        i = 1
        while True:
            if i not in colormap[n] and i not in colormap[p]:
                colormap[n][p] = i
                colormap[p][n] = i
                break
            i += 1
        if p not in visited:
            q.append(p)
            visited.add(p)

for a, b in ab:
    print(colormap[a][b])


### FIXED CODE ###

from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) # パス先, パスの色でキューに追加
while q:
    v, pc = q.popleft()
    nc = 0 # 使用する色
    for nv, edge in tree[v]: # nv=パス先 edge=abでの順番
        nc += 1
        if nc == pc: # 渡ってきたパスの色と同じなら+1した色にする
            nc += 1
        color[edge] = nc # 使用する色を答えのリストに格納
        q.append((nv, nc))

print(max(color))
print(*color, sep="\n")
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if a[mi-1] >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)