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

(n, k), p, c = [[*map(int, i.split())] for i in open(0)]
 
def solve(x, t):
    visit = [0] * n
    visit[x] = 1
    loop = [0] * n
    count = 0
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        x = p[x] - 1
        if l:
            if visit[x]:
                if loop[x]:
                    ln = sum(loop)
                    if t > ln:
                        sub += (t//ln -1)*count*(count>0)
                        t %= ln
                        t += ln
                    l = False
                count += c[x]
                loop[x] = 1
            visit[x] = 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)
        if t < 1:
            return ans
 
 
print(max(solve(i, k) for i in range(n)))

### FIXED CODE ###

(n, k), p, c = [[*map(int, i.split())] for i in open(0)]

def solve(x, t):
    visit = [0] * n
    visit[x] = 1
    loop = [0] * n
    count = 0
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        x = p[x] - 1
        if l:
            if visit[x]:
                if loop[x]:
                    ln = sum(loop)
                    if t > l:
                        sub += (t//ln -1)*count*(count>0)
                        t %= ln
                        t += ln
                    l = False
                count += c[x]
                loop[x] = 1
            visit[x] = 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)
        if t < 1:
            return ans


print(max(solve(i, k) for i in range(n)))
### BUGGY CODE ###

N,M=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

_A=[sum(A[:i:]) for i in range(N+1)]

count=0
for l in range(N+1):
    for r in range(l+1,N+1):

        if (_A[r]-_A[l])%M==0:
                count+=1


print(count)


### FIXED CODE ###

N,M=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]

_A=[0]
sum=0
d={0:1}
key=[0]
for i in range(N):
    sum=(sum+A[i])%M
    try:
        d[sum]+=1
    except KeyError:
        d[sum]=1
        key.append(sum)

count=0
for i in key:
    _count=d[i]

    count+=(_count-1)*_count/2
print(int(count))
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = [list(input()) for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            a[i][j] = int(a[i][j])
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        right,bl,yorn = 0,[0 for _ in range(l)],True
        while right < W:
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
                right += 1
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def dfs(graph, N, start=0):
    visited = [False] * N
    visited[start] = True
    stack = [start]
    res = [start]
    while stack:
        index = stack.pop()
        for node in graph[index]:
            if not visited[node]:
                stack.append(node)
                visited[node] = True
                res.append(node)
    return res

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(lambda i: int(i)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)

    ans = 0
    for i in range(N):
        res = dfs(graph, N, start=i)
        ans = max(ans, len(res))

    print(ans)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, N):
        self.N = N
        self.r = [-1] * (N+1)

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x, y = y, x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -self.r[self.root(x)]

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

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(lambda i: int(i)-1, input().split())
        uf.unite(A, B)

    ans = 0
    for i in range(N):
        ans = max(ans, uf.size(i))

    print(ans)

main()
### BUGGY CODE ###

s = list(input())
k =  int(input())
s.append((''))
Dict = {}
dict_keys = []
for left in range(len(s)):
    for right in range(left+1,len(s)):
        string = ''.join(s[left:right])
        if string not in Dict.keys():
            Dict[string] = True
Dict = sorted(Dict.keys())
print(Dict[k-1])

### FIXED CODE ###

s = list(input())
k =  int(input())
s.append((''))
Dict = {}
dict_keys = []
for left in range(len(s)):
    for right in range(left+1,len(s)):
        string = ''.join(s[left:right])
        if len(string)>k:
            break
        if string not in Dict.keys():
            Dict[string] = True
Dict = sorted(Dict.keys())
print(Dict[k-1])
### BUGGY CODE ###

s = list(input())
n = len(s)

mod = 10**9 + 7

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

for i in range(n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j] 
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])


### FIXED CODE ###

s = list(input())
n = len(s)

mod = 10**9 + 7

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

for i in range(n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j] 
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	RW.append( (max(0,s-x) , max(0,t-1-x),x) )

RW.sort(key=lambda x:(x[0],x[1]) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)
		elif d<s:
			break

	try:
		print hq[0]
	except:
		print -1


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

from bisect import bisect_right,bisect_left

ans = 0
for i, a in enumerate(L):
    for j, b in enumerate(L[i+1:]):
        j=i+1+j
        #print(a+b, abs(a-b), i, j)
        #for k, c in enumerate(L[j+1:]):
        #    if abs(a-b) < c and c < a+b:
        #        ans += 1
        #    if c >= a+b:
        #        break
        l = bisect_right(L[j+1:], abs(a-b))
        r = bisect_left(L[j+1:], a+b)
        #print(r-l)
        ans += r-l
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

from bisect import bisect_right,bisect_left

ans = 0
for i, a in enumerate(L[:-2]):
    for j, b in enumerate(L[i+1:-1]):
        j=i+1+j
        #print(a+b, abs(a-b), i, j)
        #for k, c in enumerate(L[j+1:]):
        #    if abs(a-b) < c and c < a+b:
        #        ans += 1
        #    if c >= a+b:
        #        break
        l = bisect_left(L, abs(a-b),j+1)
        r = bisect_left(L, a+b,j+1)
        #print(r-l)
        ans += r-l
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
i = 0
for h in range(N):
   i += 1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
### BUGGY CODE ###

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

# 計算はimos法でできそう
# O(N*K)になってしまう
for _ in range(K):
    tmp = [0] * (N+1)
    for i in range(N):
        tmp[max(0, i-A[i])] += 1
        tmp[min(N-1, i+A[i]) + 1] -= 1

    ans = [0]*N
    A[0] = tmp[0]
    for i in range(1, N):
        A[i] = A[i-1] + tmp[i]

    # print(*A)
    if sum(A) == N*N:
        break
print(*A)


### FIXED CODE ###

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

for _ in range(K):
    tmp = [0] * (N+1)
    for i in range(N):
        tmp[max(0, i-A[i])] += 1
        tmp[min(N-1, i+A[i]) + 1] -= 1

    ans = [0]*N
    A[0] = tmp[0]
    for i in range(1, N):
        A[i] = A[i-1] + tmp[i]

    # print(*A)
    if sum(A) == N*N:
        break
print(*A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil


def solve(N, K):
    getcontext().prec = 30
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
C - Dice and Coin
https://atcoder.jp/contests/abc126/tasks/abc126_c

"""
import sys


from decimal import *
from math import log2, ceil

#TLE
def __solve(N, K):
    getcontext().prec = 30
    ans = Decimal(0)
    for i in range(1, N+1):
        if i >= K:
            t = Decimal (1/N)
        else:
            t = Decimal(1/N/2**ceil(log2(K/i)))
        ans += t
    return ans


def solve(N, K):
    ans = 0
    for i in range(1, N+1):
        if i >= K:
            t = 1 / N
        else:
            t = 1/N/2**ceil(log2(K/i))
        ans += t
    return ans


def main(args):
    N, K = map(int, input().split())
    ans = solve(N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

n = int(input())

d = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    u,v,w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = warshall_floyd(d)

for i in range(n):
    print(d[0][i]%2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
n = int(input())
# n = 10000
d = [set() for i in range(n)]
cost = {}
for i in range(n-1):
    u,v,w = map(int,input().split())
    # u,v,w = i,i+1,i
    d[u-1].add(v-1)
    d[v-1].add(u-1)
    cost[(u-1,v-1)] = w%2
    cost[(v-1,u-1)] = w%2

visited = [False for i in range(n)]
colors = [0 for i in range(n)]

stack = []
def dfs(v,c):
    visited[v] = True
    colors[v] = c%2
    for i in d[v]:
        if not visited[i]:
            dfs(i,c+cost[(v,i)])

dfs(0,0)

for i in range(n):
    print(colors[i])
### BUGGY CODE ###

N = int(input())
X = input()

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    if B1 == 0:
        print(0)
        continue
    else:
        B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

### FIXED CODE ###

N = int(input())
X = input()

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])
### BUGGY CODE ###

n, m = map(int, input().strip().split())

num = [0]*n
nn = []
WA = 0
AC = 0

for i in range(m):
  text = input().strip().split()
  p = int(text[0])
  s = text[1]
  
  if p not in nn:
    if s == 'AC':
      AC += 1
      WA += num[p-1]
      nn.append(p)
    elif s == 'WA':
      num[p-1] += 1
      
print(AC, WA)

### FIXED CODE ###

n, m = map(int, input().strip().split())

num = [0]*n
nn = [-1]*n
WA = 0
AC = 0

for i in range(m):
  text = input().strip().split()
  p = int(text[0])
  s = text[1]
  
  if nn[p-1] == -1:
    if s == 'AC':
      AC += 1
      WA += num[p-1]
      nn[p-1] = 1
    elif s == 'WA':
      num[p-1] += 1
      
print(AC, WA)
### BUGGY CODE ###

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

def s(x):
    return (1+x)/2

wa=0
for i in range(N-K+1):
    temp=sum(P[i:i+K])
    if wa <= temp:
        wa=temp

ans=s(wa+K-1)
print(ans)

### FIXED CODE ###

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

def s(x):
    return (1+x)/2


wa=sum(P[0:K])
temp=sum(P[0:K])
for i in range(N-K):
    wa+=P[i+K]
    wa-=P[i]
    if temp <= wa:
        temp=wa

ans=s(temp+K-1)
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a_s = list(map(int, input().split()))
bs = list(map(int, input().split()))
cs = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
minlist = 0
for a in a_s:
    if minlist > (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist > (a + b + cs[0]):
            break
        for c in cs:
            list.append(a + b + c)
            i += 1
            if  i > k:
                minlist = min(list)
            if minlist > list[i]:
                break
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
now = 1

sum = [0 for i in range(60)]
for i in a:
    ii = i
    for j in range(60):
        if ii%2 == 1:
            sum[j] += 1
        ii //= 2
        if ii == 0:
            break

for i in range(60):
    k = (sum[i]*(n-sum[i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc147/submissions/12994515を見た

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7
m2 = [1 for i in range(60)]
for i in range(1,60):
    m2[i] = (m2[i-1]*2)%mod

ans = 0
for i in range(60):
    ni = np.count_nonzero(a&1)
    ans = (ans+ni*(n-ni)%mod*m2[i])%mod
    a >>= 1

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

A,B,N=[int(s) for s in input().split()]
x=B-1
ans=set()
while x<N:
  ans.add((A*x)//B-A*(x//B))
  x+=B
ans.add((A*N)//B-A*(N//B))
print(max(ans))
  

### FIXED CODE ###

import time
start=time.time()
A,B,N=[int(s) for s in input().split()]
x=((N+1)//B)*B-1
ans=set()
ans.add((A*N)//B-A*(N//B))
while x>0:
  ans.add((A*x)//B-A*(x//B))
  x-=B
  if (time.time()-start)>1.7:
    break
print(max(ans))
### BUGGY CODE ###

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

AB.sort()
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[0][0]<=latest:
    a,b=AB[0][0],AB[0][1]
    AB=AB[1:]
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)


### FIXED CODE ###

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

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

from collections import defaultdict
import math
 
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
A=list(map(int,input().split()))
md=defaultdict(int)
for a in A:
  md[a]+=1
md2={}
md3={}
for key,value in md.items():
  if value>1:
    md2[key]=combinations_count(value,2)
  else:
    md2[key]=0
  value-=1
  if value>1:
    md3[key]=combinations_count(value,2)
  else:
    md3[key]=0
s_md2=sum(md2.values())
for a in A:
  print(s_md2-md2[a]+md3[a])
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
from collections import defaultdict
import math
 
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
A=list(map(int,input().split()))
md={}
for a in A:
  if a in md:
    md[a]+=1
  else:
    md[a]=1
md2={}
md3={}
for key,value in md.items():
  if value>1:
    md2[key]=combinations_count(value,2)
  else:
    md2[key]=0
  value-=1
  if value>1:
    md3[key]=combinations_count(value,2)
  else:
    md3[key]=0
s_md2=sum(md2.values())
for a in A:
  print(s_md2-md2[a]+md3[a])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    for i in range(N):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    break
                if (dp0[i]>>j)&1:
                    if (dp1[i]<<j)&mask2:
                        break
            else:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=1)
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    return True
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        return True
        else:
            return True
        return False
    
    res=nibutan(-1,N)
    print(N-1-res)
    


if __name__ == '__main__':
    main()