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

# D - Ki
import sys
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def searchPar(now, par):
    parent[now] = par
    for gi in g[now]:
        if gi!=par:
            searchPar(gi, now)

def dfs(p, q):
    ans[p] += q
    for gi in g[p]:
        if parent[p]!=gi:
            dfs(gi, q)

# 各頂点の親を探す
parent = [0] * N
for i in range(N):
    searchPar(0, 0)

ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    dfs(p, x)
print(' '.join(map(str, ans)))

### FIXED CODE ###

# D - Ki

from collections import deque

n, q = map(int, input().split())

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

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

done = [-1]*n
done[0] = 1
d = deque()
d.append((0, 0))

while len(d)>0:
    v = d.popleft()
    cnt[v[0]] += v[1]
    done[v[0]] = 1
    for i in graph[v[0]]:
        if done[i]<0:
            d.append((i, cnt[v[0]]))

print(' '.join(map(str, cnt)))
### BUGGY CODE ###

N = int(input())

power = 1
for i in range(1, N+1):
  power *= i

print(power % (10 ** 9 + 7))


### FIXED CODE ###

N = int(input())

power = 1
for i in range(1, N+1):
  power = power * i % (10 ** 9 + 7)

print(power)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [None]*(2**n)
    d[0] = [(a[0], 0), (-1, -1)]
    ans = 0
    for i, t1 in enumerate(a[1:]):
        i += 1
        t2, t3, t4 = i, -1, -1
        for j in range(len(bin(i))-2):
            k = i & ~(1 << j)
            if k == i:
                continue
            (t5, t6), (t7, t8) = d[k]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 != t4:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [[(j, i), (-1, -1)] for i, j in enumerate(a)]
    ans = 0
    for i in range(1, 2**n):
        (t1, t2), (t3, t4) = d[i]
        for j in range(n):
            (t5, t6), (t7, t8) = d[i & ~(1 << j)]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 not in [t2, t4]:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()
### BUGGY CODE ###


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

mp = []
hp = [0] * h
wp = [0] * w

for i in range(m):
    l = list(map(int, input().split()))
    mp.append(l)
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1

hpdex = [i for i, x in enumerate(hp) if x == max(hp)]
wpdex = [i for i, x in enumerate(wp) if x == max(wp)]

for i in range(len(hpdex)):
    for j in range(len(wpdex)):
        if [hpdex[i] + 1, wpdex[j] + 1] not in mp:
            print(max(hp) + max(wp))
            exit()

print(max(hp) + max(wp) - 1)

### FIXED CODE ###

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

mp = set()
hp = [0] * h
wp = [0] * w

for i in range(m):
    a, b = map(int, input().split())
    mp.add((a, b))
    l = [a, b]
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1

maxhp = max(hp)
maxwp = max(wp)
hpdex = [i for i, x in enumerate(hp) if x == maxhp]
wpdex = [i for i, x in enumerate(wp) if x == maxwp]

for i in hpdex:
    for j in wpdex:
        if (i+1, j+1) not in mp:
            print(max(hp) + max(wp))
            exit()

print(max(hp) + max(wp) - 1)
### BUGGY CODE ###

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

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[{'str': '', 'len': 0} for _ in range(lent+1)] for _ in range(lens+1)]

for i in range(1, lens+1):
    for j in range(1, lent+1):
        if s[i-1] == t[j-1]:
            candidate = max(dp[i-1][j-1]['len']+1, dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j-1]['len']+1:
                dp[i][j] = {'str': dp[i-1][j-1]['str'] + s[i-1], 'len': candidate}
                continue
            elif candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}
        else:
            candidate = max(dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}

print(dp[lens][lent]['str'])


### FIXED CODE ###

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

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[0 for _ in range(lent+1)] for _ in range(lens+1)]

ans_index = []

for i in range(1, lens+1):
    for j in range(1, lent+1):
        if s[i-1] == t[j-1]:
            candidate = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j-1]+1:
                dp[i][j] = dp[i-1][j-1]+1
                continue
            elif candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
        else:
            candidate = max(dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
                continue
            else:
                dp[i][j] = dp[i][j-1]

i, j = lens, lent
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, K = MAP()
	A = LIST()
	F = LIST()

	A.sort(reverse=True)
	F.sort()

	time = [A[i]*F[i] for i in range(N)]
	# print(F)
	# print(time)

	sum_A = sum(A)

	def is_ok(x):  # 時間をx以下にできるか？
		tmp = [0]*N
		for i in range(N):
			tmp[i] = min(A[i], x//F[i])
		return sum_A - sum(tmp) <= K

	min_ = -1
	max_ = 10**18
	while min_ + 1 != max_:
		search = (min_+max_)//2
		# print(min_, max_, search)
		if is_ok(search):
			max_ = search
		else:
			min_ = search

	print(max_)


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G > N:
            break
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
 
ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G > N:
            break
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    ans = 0
    for i in range(n-2):
        a = l[i]  # 最小の辺の長さ
        for j in range(i + 1, n-1):
            b = l[j]  # 真ん中の辺の長さ
            ans += bisect_left(l[j+1:], a+b)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from bisect import bisect_left


n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        cnt += bisect_left(l, a+b) - j - 1
        # bisec_left(l, x)でlの中にxを挿入できる点を探す
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return (count < K)

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 0
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = 0
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

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

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=deque()
for i in range(Q):
    kari=input().split()
    kouho.append(kari)
for j in range(len(kouho)):
    if kouho[j][0]=="1":
        S_list=list(S_list)
        S_list.reverse()
        S_list=deque(S_list)
    else:
        if kouho[j][1]=="1":
            S_list.appendleft(kouho[j][2])
        else:
            S_list.append(kouho[j][2])
print(*S_list,sep="")

### FIXED CODE ###

from collections import deque
S=input()
S_list=deque()
for k in range(len(S)):
    S_list.append(S[k])
Q=int(input())
kouho=[input().split() for i in range(Q)]
"""for i in range(Q):
    kari=input().split()
    kouho.append(kari)"""
hanten=[]
count=0
flaag=["sonomama","hantai"]

for j in range(Q):
    flag=flaag[count%2]
    if kouho[j][0]=="1":
        count+=1
    else:
        if flag=="sonomama":
            if kouho[j][1]=="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
        else:
            if kouho[j][1]!="1":
                S_list.appendleft(kouho[j][2])
            else:
                S_list.append(kouho[j][2])
for k in range(count%2):
    S_list.reverse()
print(*S_list,sep="")
### BUGGY CODE ###

from collections import defaultdict
d = defaultdict(int)

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

for i in range(1, 1000+1):
  t = 0
  for s in range(1, i+1):
    t += s * (1 / i)

  d[i] = t

ans = 0

for index, i in enumerate(li):
  if index + K > N:
    break

  t = 0
  for k in range(K):
    t += d[li[index+k]]

  if ans < t:
    ans = t

print(ans)

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

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

for i in range(1, 1000+1):
  t = 0
  for s in range(1, i+1):
    t += s * (1 / i)

  d[i] = t

ans = 0
t = 0

for index, i in enumerate(li):
  t += d[i]

  if index > K-1:
    t -= d[li[index-K]]

  if ans < t:
    ans = t

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

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

p_likelihood = [0] * N
for i in range(N):
    p_likelihood[i] = (p[i] + 1) / 2

ans = 0
for i in range(N-K+1):
    res = sum(p_likelihood[i:i+K])
    ans = max(ans, res)

print(ans)


### FIXED CODE ###

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

res = sum(p[:K])
res_max = res
i_max = 0
for i in range(1, N-K+1):
    res += p[i+K-1] - p[i-1]
    if res > res_max:
        res_max = res
        i_max = i

ans = 0
for j in range(K):
    ans += (p[i_max + j] + 1) / 2
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())
pool = set()
n = 0
slist = list(s)

for i in range(26):
  c = s.count(chr(97+ i))
  for j in range(c):
    index = slist.index(chr(97+ i))
    slist[index] = ""
    for k in range(len(s)- index):
      pool.add(s[index:index+ k+ 1])
  if(len(pool)>= K):
    newlist = list(pool)
    newlist.sort()
    print(newlist[K- 1])
    break

### FIXED CODE ###

s = input()
K = int(input())
pool = set()
n = 0
slist = list(s)

for i in range(26):
  c = s.count(chr(97+ i))
  for j in range(c):
    index = slist.index(chr(97+ i))
    slist[index] = ""
    for k in range(len(s)- index):
      pool.add(s[index:index+ k+ 1])
      if(k>= K):
        break
  if(len(pool)>= K):
    newlist = list(pool)
    newlist.sort()
    print(newlist[K- 1])
    break
### BUGGY CODE ###

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

for i in range(1,n+1):
    a.append(1+lis.index(i))

print(*a)


### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
a = [0]*n

for i, item in enumerate(lis):
    a[item - 1] = i + 1

print(*a)
### BUGGY CODE ###

import numpy as np
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v.append('-')
        tmp = []
        nc = ''
        nn = 0
        for c in v:
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        v = ['-']
        tmp = []
        nc = ''
        nn = 0
        for i in range(h+1):
            if i == h:
                c = '-'
            else:
                c = s[i][j]
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                nc = c
                nn = 1
        res.append(tmp)
    return res

tate = np.asarray(calc2(S)).T
yoko = np.asarray(calc(S))
print((tate + yoko).max() - 1)


### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

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

# 数値Aの頻度
ndic = {}
for i in A:
    if i in ndic:
        ndic[i] += 1
    else:
        ndic[i] = 1

# 2つの同じ数値Aの選び方
cdic = {}
mem = {}
for j in ndic:
    if ndic[j] == 1:
        continue
    
    if j in mem:
        cdic[j] = mem[j]
    else:
        cdic[j] = int((ndic[j] * (ndic[j] -1)) / 2)
        mem[j] = cdic[j]

for i in A:
    cmb = 0
    for j in cdic:
        if i == j and cdic[j] > 0:
            cmb += cdic[j] - (ndic[j] - 1)
        else:
            cmb += cdic[j]
    print(cmb)

### FIXED CODE ###

import collections

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

# 数値Aの頻度
ndic = collections.Counter(A)

mem = {}
tcmb = 0
for j in ndic:
    if ndic[j] == 1:
        continue
    
    if ndic[j] in mem:
        tcmb += mem[ndic[j]]
    else:
        mem[ndic[j]] = int((ndic[j] * (ndic[j] -1)) / 2)
        tcmb += mem[ndic[j]]
        
for i in A:
    cmb  = tcmb - (ndic[i] - 1)
    print(cmb)
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))

def check(k, r, g, b):
    # 仮定: r < g < b
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 の関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

n,y=map(int,input().split())

flag=0
for i in range(y//10000 + 1):
    for j in range(y//5000 + 1):
        if y-(10000*i + 5000*j)>=0 and (y-(10000*i + 5000*j))//1000 + i + j==n:
            print(i,j,(y-(10000*i + 5000*j))//1000)
            flag=1
            break
    if flag==1:
        break
if flag==0:
    print(-1,-1,-1)

### FIXED CODE ###

n,y=map(int,input().split())

flag=0
for i in range(n+1):
    for j in range(n-i+1):
        if y-(10000*i + 5000*j)>=0 and (y-(10000*i + 5000*j))//1000 + i + j==n:
            print(i,j,(y-(10000*i + 5000*j))//1000)
            flag=1
            break
    if flag==1:
        break
if flag==0:
    print(-1,-1,-1)
### BUGGY CODE ###

N,K = map(int,input().split())
a = [0]*110
a[1:] = list(map(int,input().split()))
MOD = 10**9+7
dp = [[0]*110000 for _ in range(110)]
dp_sum = [[0]*110000 for _ in range(110)]
dp[0][0] = 1
for i in range(K+1):
    dp_sum[0][i] = 1

for i in range(1,N+1):
    for j in range(K+1):
        dp[i][j] = dp_sum[i-1][j]
        if j - a[i]-1 >= 0:
            dp[i][j] -= dp_sum[i-1][j-a[i]-1]

        if j-1 >= 0:
            dp_sum[i][j] = dp_sum[i][j-1] + dp[i][j]
        else:
            dp_sum[i][j] = dp[i][j]
        dp[i][j] %= MOD
        dp_sum[i][j] %= MOD
print(dp[N][K])
# for i in range(N+1):
#     print(dp[i])

### FIXED CODE ###

N,K = map(int,input().split())
a = [0]*110
a[1:] = list(map(int,input().split()))
MOD = 10**9+7
dp = [[0]*110000 for _ in range(110)]
dp_sum = [[0]*110000 for _ in range(110)]
dp[0][0] = 1
for i in range(K+1):
    dp_sum[0][i] = 1

for i in range(1,N+1):
    for j in range(K+1):
        dp[i][j] = dp_sum[i-1][j]
        if j - a[i]-1 >= 0:
            dp[i][j] -= dp_sum[i-1][j-a[i]-1]

        if j-1 >= 0:
            dp_sum[i][j] = dp_sum[i][j-1] + dp[i][j]
        else:
            dp_sum[i][j] = dp[i][j]
        dp[i][j] %= MOD
        dp_sum[i][j] %= MOD
print(dp[N][K])
# for i in range(N+1):
#     print(dp[i])
### BUGGY CODE ###

while True:
  t = []
  b = 0
  try:
    a = int(input())
    for n in range(2,10000):
      for x in range(2,n):
        if n % x == 0:
          break
      else:
        t.append(n)

    for b in range(1000):
      if t[b] > a:
        print len(t[0:b])
        break
  except EOFError:
    break

### FIXED CODE ###


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env python
import sys
 
list=1000000*[1]
 
list[0] = 0
list[1] = 0
for i in range(1,1000000):
    if list[i] == 1:
        for j in range(i*i,1000000,i):
            list[j] = 0
 
for i in range(2,1000000):
    list[i] += list[i-1]
     
for line in sys.stdin:
    a = int(line)
    print list[a]