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

N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))  

### FIXED CODE ###

N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
q = int(input())
oper = [list(map(int, input().split())) for _ in range(q)]
a.sort()
res = sum(a)

for i in range(q):
    b, c = oper[i]
    if b in a:
        bCount = a.count(b)
        idx = a.index(b)

        a = a[:idx] + a[idx+1:]
        a.extend([c]*bCount)
        dif = c-b

        res += dif*bCount

    print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
q = int(input())
oper = [list(map(int, input().split())) for _ in range(q)]
dic = {}
for i in range(n):
    if a[i] in dic:
        dic[a[i]] += 1
    else:
        dic[a[i]] = 1
        
res = sum(a)

for i in range(q):
    b, c = oper[i]
    if b in dic:
        bCount = dic[b]
        del(dic[b])
        if c in dic:
            dic[c] += bCount
        else:
            dic[c] = bCount

        dif = c-b

        res += dif*bCount

    print(res)
### BUGGY CODE ###

#C
a, b, c, d = map(int, input().split())
count=0
for i in range(a, b + 1):
    if i % c!=0 and i % d!=0:
        count += 1
print(count)

### FIXED CODE ###

#C
import math
a, b, c, d = map(int, input().split())

def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        x, y = y, x % y
    return x

s = b - a + 1
cc = b // c - (a - 1) // c
dd = b // d - (a - 1) // d
cd = c * d // gcd(c, d)
cd = b // cd - (a - 1) // cd
s -= cc + dd - cd
print(s)
### BUGGY CODE ###

MAXN=5000
def deleteBlocks():
    i=MAXN-1
    while i>=0 and set(L[i])!=set([False]):
        if set(L[i])==set([True]):
            del L[i]
            L.insert(0,[False]*5)
        else:
            i-=1

def setBlocks(d,lng,pos):
    if d==1:
        for i in range(MAXN):
            if set(L[i][pos:pos+lng])!=set([False]):
                L[i-1][pos:pos+lng]=[True]*lng
                break
        else:
            L[i][pos:pos+lng]=[True]*lng
    elif d==2:
        for i in range(MAXN):
            if L[i][pos]:
                for j in range(i-lng,i):
                    L[j][pos]=True
                break
        else:
            for j in range(i-lng+1,i+1):
                L[j][pos]=True
    deleteBlocks()

while True:
    n=input()
    if n==0:break
    L=[[False]*5 for i in range(MAXN)]
    for i in range(n):
        d,p,q=map(int,raw_input().split())
        setBlocks(d,p,q-1)
    print sum(sum(i) for i in L)

### FIXED CODE ###

MAXN=5000
def setBlocks(d,lng,pos):
    if d==1:
        for i in range(MAXN):
            if set(L[i][pos:pos+lng])!=set([False]):
                L[i-1][pos:pos+lng]=[True]*lng
                if set(L[i-1])==set([True]):
                    del L[i-1]
                    L.insert(0,[False]*5)
                break
        else:
            L[i][pos:pos+lng]=[True]*lng
            if set(L[i])==set([True]):
                del L[i]
                L.insert(0,[False]*5)
    elif d==2:
        for i in range(MAXN):
            if L[i][pos]:
                for j in range(i-lng,i):
                    L[j][pos]=True
                for j in range(i-lng,i):
                    if set(L[j])==set([True]):
                        del L[j]
                        L.insert(0,[False]*5)
                break
        else:
            for j in range(i-lng+1,i+1):
                L[j][pos]=True
            for j in range(i-lng+1,i+1):
                if set(L[j])==set([True]):
                    del L[j]
                    L.insert(0,[False]*5)

while True:
    n=input()
    if n==0:break
    L=[[False]*5 for i in range(MAXN)]
    for i in range(n):
        d,p,q=map(int,raw_input().split())
        setBlocks(d,p,q-1)
    print sum(sum(i) for i in L)
### BUGGY CODE ###

import math

K = int(input())
result = 0
sum = 0




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

print(sum)            



#a = list(map(int, input().split()))
#ans = a[0]
#for i in range(1, N):
#    ans = fractions.gcd(ans, a[i])
#print(ans)

### FIXED CODE ###

K = int(input())
import math
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        value = math.gcd(i,j)
        for k in range(1, K+1):
            sum += math.gcd(value,k)
 
print(sum)
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split(' ')]
s = 0
for i in set(range(N-1)):
    for j in set(range(i, N)):
        xor = A[i]^A[j]
        s += xor
    
ans = s % (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(n) for n in input().split(' ')]
 
ans = 0
for i in range(60):
    x = 0
    for A_i in A:
        if A_i>>i&1:
            x += 1
    ans += x*(N-x)*2**i
ans = ans % (10**9+7)
print(ans)
### BUGGY CODE ###

N,A,B=map(int,input().split())
S=list(input())
ans=[]
for i in S:
    if i=='a':
        if ans.count('Yes')<A+B:
            ans.append('Yes')
        else:
            ans.append('No')
    elif i=='b':
        if ans.count('Yes')<A+B and S[0:len(ans)].count('b')<B:
            ans.append('Yes')
        else:
            ans.append('No')
    else:
        ans.append('No')

print('\n'.join(ans))



### FIXED CODE ###

N,A,B=map(int,input().split())
S=list(input())
cnt1=0
cnt2=0

for i in range(N):
    if S[i]=='c':
        print('No')
    elif S[i]=='a':
        if cnt1<A+B:
            print('Yes')
            cnt1+=1
        else:
            print('No')
    else:
        if cnt1<A+B and cnt2<B:
            print('Yes')
            cnt1+=1
            cnt2+=1
        else:
            print('No')
### BUGGY CODE ###

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

L = sorted(L)

# print(L)

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            a = L[i]
            b = L[j]
            c = L[k]
            if a < b + c and b < c + a and c < a + b:
                # print("a:{}, b:{}, c:{}".format(a, b, c))
                ans += 1

print(ans)


### FIXED CODE ###

import time
N = int(input())
L = list(map(int, input().split()))

L = sorted(L)

# print(L)

# 三角形なのでa>b>cになるように選べば, a+b>cとなる
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        # print("i:{}, j:{}".format(i, j))
        b = L[j]
        left = j+1
        right = N-1
        c = L[N-1]
        if a+b>c:
            # print("true - k:{}".format(N-1))
            # print("num_c:{}".format())
            ans += N-j-1
        else:
            mid = right
            while left < right:
                if mid == (left+right)//2:
                    break
                mid = (left+right)//2
                # print("left:{}, mid:{}, right:{}".format(left, mid, right))
                c = L[mid]
                if a+b>c:
                    left = mid
                else:
                    right = mid
                # time.sleep(0.05)
            # print("false - k:{}".format(mid))
            if a+b>c:
                # print("a+b>c:{}".format(True))
                ans += mid - j
            else:
                # print("a+b>c:{}".format(False))
                ans += mid - j - 1
        # print("ans of ({},{}): {}".format(i,j,ans))

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

n = int(input())
an = list(map(int, input().split()))
n_list = [0]*n

for i in range(n):
  n_list[an[i]-1] += 1

for j in range(n):
  n_list1 = n_list[:]
  n_list1[an[j]-1] -= 1
  print(int(sum(list(map(lambda x: x*(x-1)/2, n_list1)))))
  

### FIXED CODE ###

n = int(input())
an = list(map(int, input().split()))
n_list = [0]*n

for i in range(n):
  n_list[an[i]-1] += 1
n_sum = int(sum([x*(x-1)/2 for x in n_list]))

for j in range(n):
  n_remove = n_list[an[j]-1] - 1
  print(n_sum - n_remove)
### BUGGY CODE ###

N = int(input())
S = input()

def countHand(st, pos):
  left_b = st[:pos].count('#')
  right_w = st[pos:].count('.')
  count = left_b + right_w
  return count
  
minHand = 2 * 10 **5
for i in range(len(S)+1):
  ret = countHand(S, i) 
  if ret <= minHand:
    minHand = ret

ans = minHand
print("{}".format(ans))

### FIXED CODE ###

N = int(input())
S = input()

# at position 0
l_b = 0
r_w = S.count('.')

needHand = l_b + r_w
for i in S:
  if i == '#': #black
    l_b += 1
  else:
    r_w -= 1  
  needHand = min(needHand, l_b + r_w)

ans = needHand
print("{}".format(ans))
### BUGGY CODE ###

import collections
N = int(input())
 
dic = {}
for i in range(N):
  S = input()
  if S in dic:
    dic[S] += 1
  else:
    dic[S] = 1
maxval = max(dic.values())
 
keys = [k for k, v in dic.items() if  v == max(dic.values())]
[print(sorted(keys)[i]) for i in range(len(keys))]

### FIXED CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]

if len(S) == len(set(S)):
  ans = S
else:
  ans = []
  c = collections.Counter(S)
  c_common = c.most_common()
  max_vote = c_common[0][1]
  for k in range(len(set(S))):
    if c_common[k][1]== max_vote:
      ans.append(c_common[k][0])
    else:
      break
[print(a) for a in sorted(ans)]
### BUGGY CODE ###

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

ans = set()

for i in range(M):
    L, R = map(int, input().split())
    
    if M == 1:
        print(R-L+1)
        break
        
    else:
        if i == 0:
            ans = set(list(range(L, R + 1)))
                
        else:
            s = set(list(range(L, R + 1)))
            ans = ans & s

else:
    print(len(ans))

### FIXED CODE ###

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

l = 0
r = N

for i in range(M):
    L, R = map(int, input().split())
    
    if L > l:
        l = L
            
    if R < r:
        r = R
                
    ans = r - l + 1
    if ans < 0:
        print(0)
        break

else:
    print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
aa=list(map(int,input().split()))
value=1
for i in range(k):
  value*=aa[i]
for i in range(k,n):
  a=int(value*aa[i]/aa[i-k])
  if value<a:
    print("Yes")
  else:
    print("No")
  value=a

### FIXED CODE ###

n,k=map(int,input().split())
aa=list(map(int,input().split()))
for i in range(k,n):
  if aa[i]/aa[i-k]>1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
import bisect
# 解説の二分探索
# あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になるXを探す
l,r=0,a[-1]*2
while r-l>1:
  x=(l+r)//2
  cnt=0
  for ai in a:
    cnt+=n-bisect.bisect_left(a,x-ai)
  # x以上がm個以上ある->xを増加
  [l,r]=[x,r] if cnt>=m else [l,x]
x=(l+r)//2
ans=[]
for ai in a:
  bi=bisect.bisect_left(a,x-ai)
  ans.extend([aj+ai for aj in a[bi:]])
ans.sort()
print(sum(ans[-m:]))


### FIXED CODE ###


import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。M個以上になる最大のXを探す
  # [l,r)半開区間
  l,r=0,a[-1]*2+1
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->x~r-1に求めるものがある
    if cnt>=m:
      l=x
    else:# x以上がm個未満ある->l~x-1に求めるものがある
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  print(ans+(m-cnt)*x)

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=np.array([np.array([float("inf") for i in range(maxV*(N+1))]) for j in range(N+1)])
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)


### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
### BUGGY CODE ###

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

MOD = 998244353

def solution(A, S):
    N = len(A)
    
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(S+1):
            dp[i][j] += 2*dp[i-1][j]
            dp[i][j] %= MOD
            if j >= A[i-1]:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= MOD
    return dp[N][S]

print(solution(A, S))

### FIXED CODE ###

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

MOD = 998244353

def solution(A, S):
    N = len(A)
    
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(S+1):
            dp[i][j] += 2*dp[i-1][j]
            dp[i][j] %= MOD
            if j >= A[i-1]:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= MOD
    return dp[N][S]

print(solution(A, S))
### BUGGY CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [N] * (N+1)
for w in range(N+1):
    dp[w] = max([N] + [dp[w-a] + b-a for a, b in zip(A, B) if w-a >= 0])

M = max(dp)
dp = [M] * (M+1)
for w in range(M+1):
    dp[w] = max([M] + [dp[w-b] + a-b for a, b in zip(A, B) if w-b >= 0])

print(max(dp))


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
  elif j == 0:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

#ABC077 C - Snuke Festival
from bisect import bisect_left, bisect_right
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N = ni()
A = nl()
B = nl()
C = nl()

A.sort()
B.sort()
C.sort()
ans = 0

for i in range(N):
    t = 0
    tt = 0
    t = bisect_left(B,C[i])
    for j in range(t,0,-1):
        tt = bisect_left(A,B[j-1])
        ans += tt

print(ans)


### FIXED CODE ###

#ABC077 C - Snuke Festival
from bisect import bisect_left, bisect_right
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N = ni()
A = nl()
B = nl()
C = nl()

A.sort()
C.sort()

ans = 0

for i in range(N):
    t = 0
    tt = 0
    t = bisect_left(A,B[i])
    tt = N-bisect_right(C,B[i])
    ans += t*tt

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

import bisect
n,m=map(int,input().split())
pl=[[] for i in range(n)]
cl=[]
for i in range(m):
    p,y=list(map(int,input().split()))
    cl+=[[p,y]]
    bisect.insort(pl[p-1],y)
for p,y in cl:
    print('{0:06d}{1:06d}'.format(p,pl[p-1].index(y)+1))

### FIXED CODE ###

n,m=map(int,input().split())
py=[list(map(int,input().split()))+[i] for i in range(m)]
py.sort(key=lambda x:x[1])
ans=[]
cnt=[0]*n
for p,y,i in py:
    ans.append(['{0:06d}{1:06d}'.format(p,cnt[p-1]+1),i])
    cnt[p-1]+=1
ans.sort(key=lambda x:x[1])
for a,i in ans:
    print(a)
### BUGGY CODE ###

N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = [list(map(int, input().split())) for _ in range(N-1)]
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)
### BUGGY CODE ###

N = int(input())


for a in range(N // 100 + 1):
  for b in range(N // 101 + 1):
    for c in range(N // 102 + 1):
      for d in range(N // 103 + 1):
        for e in range(N // 104 + 1):
          for f in range(N // 105 + 1):
            if a * 100 + b * 101 + c * 102 + d * 103 + e * 104 + f * 105 == N:
              print(1)
              exit()
print(0)




### FIXED CODE ###

N = int(input())


for a in range(N // 100 + 1):
  for b in range(N // 101 + 1):
    for c in range(N // 102 + 1):
      for d in range(N // 103 + 1):
        for e in range(N // 104 + 1):
          for f in range(N // 105 + 1):
            if a * 100 + b * 101 + c * 102 + d * 103 + e * 104 + f * 105 == N:
              print(1)
              exit()
print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q=map(int,input().split())
g=[[]for _ in range(n)]
res=[0 for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    res[p-1]+=x
    


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)

### FIXED CODE ###

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

n,q=map(int,input().split())
g=[[]for _ in range(n)]
res=[0 for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    res[p-1]+=x
    


def my_add(v,par):
    for vn in g[v]:
        if vn==par:
            continue
        res[vn]+=res[v]
        my_add(vn,v)

my_add(0,-1)
print(*res)
### BUGGY CODE ###

N=input()

r=1
for i in xrange(N):
    r=r*(i+1)

print r%(10**9 + 7)


### FIXED CODE ###

N=input()
 
r=1
for i in xrange(N):
    r=r*(i+1)
    r=r%(10**9 + 7)
 
print r
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = defaultdict(int)
    dp[0] = 1
    for i in range(n)[::-1]:
        if i == m:continue
        ai = a[i]
        d = list(dp.keys())
        for j in d:
            dp[j+ai] = 1
            if k_ <= j+ai < k:
                r = m
                break
        else:
            continue
        break
    else:
        l = m
print(r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma+1,k-ai))[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T