Harryxun/stf_run huggingface dataset:
from collections import deque
import sys

sys.setrecursionlimit(1000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < n-1 :
    cost,(node1,node2) = s.popleft()
    if root(node1,par) != root(node2,par):
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)


### FIXED CODE ###

from collections import deque
import sys
 
sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
m = len(set(nodes))
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < m-1 :
    cost,(node1,node2) = s.popleft()
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)
n,a,b=map(int,input().split())if(b-a)%2==0:print((b-a)//2)else:print(min(a-1,n-b)+1+(b-a-1)//2)

### FIXED CODE ###

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

if (b - a) % 2 == 0:
    print((b - a) // 2)
else:
    print(min(a, n - b + 1) + (b - a - 1) // 2)
#include<iostream>

void cal_area(a,b){
    return a*b;
}
void cal_parimeter(a,b){
    return 2*(a+b);
}

output(a,b){
    print(a << " " << b);
}

void input(){
    int a, b;
    std::cin >> a >> b;
    output(cal_area(a,b), cal_parimeter(a,b));
}
int main(){
    input();
    return 0;
}


### FIXED CODE ###

a,b = map(int, input().split())
print(a*b, 2*(a+b))
r,g,b=map(int, input.split())
x=100*r+10*g+b
if x%4==0:
 print('YES')
else:
  print('NO')

### FIXED CODE ###

r,g,b=map(int, input().split())
x=100*r+10*g+b
if x%4==0:
 print('YES')
else:
  print('NO')
n,m=map(int,input().split())
if m-n=>2018:
  print(0)
else:
  l=[]
  for i in range(n,m+1):
    l.append(i%2019)
  l=sorted(l)
  print(l[0]*l[1])

### FIXED CODE ###

n,m=map(int,input().split())
if m-n>=2018:
  print(0)
else:
  l=[]
  for i in range(n,m+1):
    l.append(i%2019)
  t=10000
  for i in range(len(l)-1):
    for j in range(i+1,len(l)):
      if t>(l[i]*l[j])%2019:
        t=(l[i]*l[j])%2019
  print(t)
N, K = map(int, inpu().split())
print(N%K)

### FIXED CODE ###

N, K = map(int, input().split())
x = N % K

while x > K/2:
    x = abs(K-x)

print(x)
def bit_DP(N.Adj):
    dp=[[0]*N for i in range(1<<N)]
    dp[1][0]=1
    for S in range(1<<N):
        for v in range(N):
            if (S&(1<<v))==0:
                continue
            sub=S^(1<<v)
            
            for u in range(N):
                if (sub&(1<<u)) and (Adj[u][v]):
                    dp[S][v]+=dp[sub][u]
    ans=sum(dp[(1<<N)-1][u] for u in range(1,N))
    return ans
def main():
    N,M=map(int,input().split())
    Adj=[[0]*N for i in range(N)]
    for _ in range(M):
        a,b=map(int,input().split())
        Adj[a-1][b-1]=1
        Adj[b-1][a-1]=1
    ans=bit_dp(N,Adj)
    print(ans)
if __name__=='__main__':
    main()

### FIXED CODE ###

N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))
import sys
input=sys.stdin.readline

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An.sort()
          ans+=An.pop(len(An)) 
print(ans)


### FIXED CODE ###

import heapq
N , M = map(int , input().split())
jobs = [list(map(int , input().split())) for _ in range(N)]
jobs.sort()

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    #print(q)
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

print(ans)
import numpy as np
N = int(input())
A = list(map(int, input().split()))

# solve "mat * x = b" about x
x, y = np.identity(N), np.identity(N)
y0 = y[0]
y = np.reshape(np.append(np.delete(y, 0, 0), y0), (N, N))
mat = (x + y) / 2

b = np.array(A)

for i in range(len(mat) - 1):
    for j in range(i + 1, len(mat)):
        coef = mat[j][i] / mat[i][i]
        mat[j] -= mat[i] * coef
        b[j] -= b[i] * coef

for i in range(len(mat) - 1, 0, -1):
    b[i] /= mat[i][i]
    mat[i] /= mat[i][i]
    for j in range(i):
        b[j] -= b[i] * mat[j][i]
        mat[j][i] = 0

b = [int(n) for n in b]
b[0] += 1
print(" ".join(map(str, b)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = [0] * N

X[0] = sum(A) - 2 * (sum([A[i] for i in range(N) if i % 2 == 1]))

for i in range(N - 1):
	X[i + 1] = 2 * A[i] - X[i]

print(" ".join(map(str, X)))
k,s = [int(x) for x in input().split()]
a = 0
n = 0
while a <= k:
  b = 0
  while b <= k:
    z = s-a-b
    if 0<=z and z <= k:
      n += 1
    b += 1
  a += 1
print(n)


### FIXED CODE ###

print(input().replace(',',' '))
import fractions
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
for i in range(N-1):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[-i-1]))
MAX = 0
for i in range(N):
    MAX = max(MAX, gcd(L[i], R[-i-1]))
print(MAX)



### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
for i in range(N-1):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[-i-1]))
MAX = 0
for i in range(N):
    MAX = max(MAX, gcd(L[i], R[-i-1]))
print(MAX)
# -*- coding: utf-8 -*-
import math
N = int(input())
ans = 0
for i in range(int(math.log2(N))+1):
    ans += 2 ** i

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N = int(input())
ans = 0
for i in range(int(math.log(N, 2))+1):
    ans += 2 ** i

print(ans)
a = input()
print(a+a**2+a**3)


### FIXED CODE ###

a = int(input())
print(a+a**2+a**3)
#coding:utf-8

n = int(input())
power = 1

for i in range(0,n):
  power = ((i+1) * power) % (7 + 10＊＊９)

print(power)


### FIXED CODE ###

#coding:utf-8

n = int(input())
p = 1

for i in range(0,n):
  p = ((i+1) * p) % (10**9 + 7)

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


ka = k - a
if ka > 0:
    kb = ka - b
print(a*1+ka*0+kb*-1)



### FIXED CODE ###

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


ka = k - a

if ka > 0:
    kb = ka - b
elif ka <= 0:
    a = k
    ka = 0
    kb = 0
else:
    kb = 0
print(a*1+ka*0+kb*-1)
N=int(input())
L=[]
for i in range(N):
    x,y=map(int, input().split())
    L.append((x,y))

D={}
for i in range(N-1):
    t1=L[i]
    L2=L[i+1:]
    for t2 in L2:
        x1,y1=t1
        x2,y2=t2
        d1=(x2-x1,y2-y1)
        d2=(x1-x2,y1-y2)
        if d1 in D:
            D[(x2-x1,y2-y1)]+=1
        else:
            D[(x2-x1,y2-y1)]=1
        if d2 in D:
            D[(x1-x2,y1-y2)]+=1
        else:
            D[(x1-x2,y1-y2)]=1

print(max(N-max(D.values()),0))


### FIXED CODE ###

N=int(input())
L=[]
if N==1:
    print(1)
    exit()
for i in range(N):
    x,y=map(int, input().split())
    L.append((x,y))

D={}
for i in range(N-1):
    t1=L[i]
    L2=L[i+1:]
    for t2 in L2:
        x1,y1=t1
        x2,y2=t2
        d1=(x2-x1,y2-y1)
        d2=(x1-x2,y1-y2)
        if d1 in D:
            D[(x2-x1,y2-y1)]+=1
        else:
            D[(x2-x1,y2-y1)]=1
        if d2 in D:
            D[(x1-x2,y1-y2)]+=1
        else:
            D[(x1-x2,y1-y2)]=1

print(max(N-max(D.values()),0))
N,M,X,Y=map(int, input().split())
Xs=list(map(int, input().split()))
Ys=list(map(int, input().split()))
if max([X,Xs]) < min([Y,Ys]):
  print("No War")
else:
  print("War")

### FIXED CODE ###

N,M,X,Y=map(int, input().split())
Xs=list(map(int, input().split()))
Ys=list(map(int, input().split()))
if max([X,max(Xs)]) < min([Y,min(Ys)]):
  print("No War")
else:
  print("War")
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()
c0, c1 = [], []
if S[0] == '1':
    c0.append(0)
i = 0
while i < N:
    p = S[i]
    c = 1
    i += 1
    while i < N and S[i] == p:
        i += 1
        c += 1
    if p == '0':
        c0.append(c)
    else:
        c1.append(c)
if S[N-1] == '0':
    c1.append(0)
l0 = len(c0)
for i in range(1, l0):
    c0[i] += c0[i-1]
    c1[i] += c1[i-1]
l = l0 - K + 1
ans = c0[K-1] + c1[K-1]
for i in range(1, l):
    tmp = c0[i+K-1] - c0[i-1] + c1[i+K-1] - c1[i-2]
    if ans < tmp:
        ans = tmp
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()
c0, c1 = [], []
if S[0] == '1':
    c0.append(0)
i = 0
while i < N:
    p = S[i]
    c = 1
    i += 1
    while i < N and S[i] == p:
        i += 1
        c += 1
    if p == '0':
        c0.append(c)
    else:
        c1.append(c)
if S[N-1] == '0':
    c1.append(0)
l0 = len(c0)
if l0 < K:
    K = l0
ans = sum(c0[0:K]) + sum(c1[0:K])
for i in range(1, l0):
    c0[i] += c0[i-1]
    c1[i] += c1[i-1]
l = l0 - K + 1
if l0 == 2 and S[0] == '1':
    ans = N
else:
    for i in range(1, l):
        tmp = c0[i+K-1] - c0[i-1] + c1[i+K-1]
        if i - 2 >= 0:
            tmp -= c1[i-2]
        if ans < tmp:
            ans = tmp
print(ans)
def check(x, y, S):

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S:
      count += 1
print(count)


### FIXED CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S and x + y + K >= S:
      count += 1
print(count)
import pdb
import sys
sys.setrecursionlimit(10000)

def eat(n, x):
    ret = 0

    if x == 0:
        return 0, x

    if n == 0:
        x -= 1
        return 1, x

    if allnum[n] <= x:
        x -= allnum[n]
        return pnum[n], x
        
    
    x -= 1 # eat bread
    if x == 0:
        return 0, x

    # eat n-1 beager
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    # eat patty
    x -= 1
    ret += 1
    if x == 0:
        return ret, x

    # eat n-1 beager
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    x -= 1 # eat bread
        
    return ret, x


def main():
    tmp = input().split()
    n = int(tmp[0])
    x = int(tmp[1])
    global pnum
    global allnum
    pnum = [1]
    allnum = [1]
    for i  in range(1, 52):
        pnum.append(pnum[i-1] * 2 + 1)
        allnum.append(allnum[i-1] * 2 + 3)

    ans, tmp = eat(n, x)

    print("%d" % ans)

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import pdb


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

    ans = ""
    
    if num == 25:
        ans = "Christmas"
    elif num == 24:
        ans = "Christmas Eve"
    elif num == 23:
        ans = "Christmas Eve Eve"
    elif num == 22:
        ans = "Christmas Eve Eve Eve"
        
    print(ans)

        
if __name__ == '__main__':
    main()
def dense(a, b):
	return b / (a+b)

def resolve():
	a, b, c, d, e, f = map(int, input().split())
	ws = set()
	ss = set()
	for i in range(31):
		for j in range(31):
			if a*100*i + b*100*j <= f:
				ws.add(a*100*i + b*100*j)
	for i in range(3001):
		for j in range(3001):
			if c*i + j*d <= f:
				ss.add(c*i + j*d)
	ans_w, ans_s = -1, 0
	lim = e / (100+e)
	for wv in ws:
		for sv in ss:
			if wv + sv > f:
				continue
			if wv + sv == 0:
				continue
			if lim >= dense(wv, sv):
				if dense(ans_w, ans_s) <= dense(wv, sv):
					ans_w, ans_s = wv, sv
	print(ans_w + ans_s, ans_s)
resolve()

### FIXED CODE ###

def resolve():
	n = int(input())
	a = int(input())
	print(n**2 - a)
resolve()
a,b=map(int,input().split())
print(math.floor((a+b)/2))

### FIXED CODE ###

a,b=map(int,input().split())
import math
print(math.ceil((a+b)/2))
n, k = map(int, input().split())
h = list(map(int, input().split()))+[float('inf')]*(10001-n)
dp = [float('inf')]*100001
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        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()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])
N=int(input())
S=input()
ans=0

for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            for k in range(1,2*j-i):
                if S[j]!=S[k] and S[k]!=S[i]:
                    ans+=1
            for k in range(2*j-i+1,N):
                if S[j]!=S[k] and S[k]!=S[i]:
                    ans+=1
         
                
print(ans)

### FIXED CODE ###

N=input()
if '7' in N:
    print("Yes")
else:
    print("No")
array = list(map(int, input().split()))                                                        
  
sort_array = array.sort()
 
for i in range(len(array)):
    if i == 0 and array[i] == 5:
        continue
    elif  i==0 and not(array[i]) == 5:
        print("No")
        break
 
    if i==1 and array[i] == 5:
        continue
    elif  i==1 and not(array[i]) == 5:
        print("No")
        break
 
 
    if i==2 and array[i] == 7:
        print("Yes")
    elif  i==2  and not(array[i]) == 7:
        print("No")
        break
~                        


### FIXED CODE ###

array = list(map(int, input().split()))                                                        
  
array.sort()

if array[0] == 5 and array[1] == 5 and array[2] == 7:
  print("YES")
else:
  print("NO")
S = int(input())
h = S//3600
m = S%3600//60
s = S%60
print("h":"m":"s")



### FIXED CODE ###

S = int(input())
h = S//3600
m = S%3600//60
s = S%60
print(f"{h}:{m}:{s}")
import math as mh
import fractions as fr
from functools import reduce as rd

n, p = (int(_) for _ in input().split())
x = list(int(_) for _ in input().split())

lmin = abs(p - min(x))
lmax = abs(p - max(x))

d = fr.gcd(lmin, lmax)
exgcd = rd.reduce(fr.gcd, [d,lmin,lmax])

print(exgcd)

### FIXED CODE ###

import math as mh
import fractions as fr
from functools import reduce

n, p = (int(_) for _ in input().split())
x = list(int(_) for _ in input().split())
x.append(p)
x.sort()

dx = []
for i in range(1,len(x)):
    dx.append(x[i] - x[i-1])

exgcd = reduce(fr.gcd, dx)
print(exgcd)
N,K = map(int,input.split())
p = map(int,input.split())

print(sum(sorted(p)[:K]


### FIXED CODE ###

N, K = map(int, input().split())
p = map(int, input().split())

print(sum(sorted(p)[:K]))
n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [0 for i in range(n)]
cost[1] = abs(h[1]-h[0])
min_cost = 10000
for i in range(1,n-1):
    for j in range(k):
        if i >= j:
            min_cost = min(min_cost, cost[i-j]+abs(h[i+1]-h[i-j]))
    cost[i+1] = min_cost

print(cost[i+1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [float('inf') for i in range(n)]
cost[0] = 0
for i in range(1,n):
    for j in range(1, k+1):
        if i >= j:
            cost[i] = min(cost[i], cost[i-j]+abs(h[i]-h[i-j]))

print(cost[n-1])
def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in range(1, len(dic)):
        count += (dic[j] - j) if dic[j] > j else dic[j]
    print(count)


if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in dic.items():
        count += j[1] - j[0] if j[1] >= j[0] else j[1]
    print(count)


if __name__=="__main__":
    main()
import math
from functools import reduce

n=int(input())

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

num_list=[]
for _ in range(n):
    num_list.append(int(input()))
print(lcm(*num_list))

### FIXED CODE ###

n=int(input())

# 最上公倍数を考える
from fractions import gcd
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

num_list=[]
for _ in range(n):
    num_list.append(int(input()))
print(lcm(*num_list))
N,X = (input().split())
L = list(map(int, input().split()))
x = int(X)
n = int(N)+1
position = 0
count = 0
if n > count:
    while position < x:
        position += L[count]
        count += 1
    print(count)
else:
    print(n)


### FIXED CODE ###

n, x = list(map(int, input().split()))
li = list(map(int, input().split()))

ans = 1
pos = 0
for i in range(n):
	pos = pos + li[i]
	if pos <= x:
		ans += 1
print(ans)
from math import pi
r = int(input())
print(pi*r**2, 2*pi*r)

### FIXED CODE ###

from math import pi
r = float(input())
print(pi*r**2, 2*pi*r)
#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
for p,x in PX:
    counter[p] += x

def bfs(graph,counter,edge):
    for e in graph[edge]:
        if check[e]:
            continue
        else:
            counter[e] += counter[edge]
            check[e] = True
            bfs(graph,counter,e)

bfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)


### FIXED CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
parent = [None for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

### FIXED CODE ###

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()
#配るDP
N=int(input())
h=[int(i) for i in input().split()]

#DPテーブル＆最小化問題なのでINFに初期化
dp = [float("inf")]*N
#初期条件
dp[0] = 0
#ループ
for i in range(N):
    dp[i+1] = min(dp[i],dp[i]+abs(h[i]-h[i+1]))
    if i>1:
        dp[i+2] = min(dp[i],dp[i]+abs(h[i]-h[i+2]))

print(dp[-1])


### FIXED CODE ###

N=int(input())
h=[int(i) for i in input().split()]

#DPテーブル＆最小化問題なのでINFに初期化
dp = [float("inf")]*N
#初期条件
dp[0] = 0
#ループ
for i in range(N):
    dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
    if i>1:
        dp[i] = min(dp[i],dp[i-2]+abs(h[i]-h[i-2]))

print(dp[-1])
# -*- coding: utf-8 -*-

h,w = map(int, input().split())

a = [list(input()) for _ in range(h)]

a_new = []
for row in a:
    cache = set(row)
    if (len(cache) == 1) and (row[0] == "."):
        pass
    else:
        a_new.append(row)

n_h = len(a_new)
n_w = len(a_new[0])

b_new = [["" for _ in range(n_h)] for _ in range(n_w)]

for i in range(n_h):
    for j in range(n_w):
        b_new[j][i]=a_new[i][j]


a = b_new

a_new = []
for row in a:
    cache = set(row)
    if (len(cache) == 1) and (row[0] == "."):
        pass
    else:
        a_new.append(row)


n_h = len(a_new)
n_w = len(a_new[0])

b_new = [["" for _ in range(n_h)] for _ in range(n_w)]

for i in range(n_h):
    for j in range(n_w):
        b_new[j][i]=a_new[i][j]


ans = ""

for i in range(n_h):
    for j in range(n_w):
        ans += b_new[i][j]
    ans += "\n"

print(ans)

### FIXED CODE ###

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

h, w = map(int, input().split())
a = [""]*h
for i in range(h):
    a[i] = input()

row = [False] * h
col = [False] * w


for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            row[i] = True
            col[j] = True


for i in range(h):
    if row[i]:
        for j in range(w):
            if col[j]:
                print(a[i][j], end = "")

        print()