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

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for H, P in HPs:
    if dp[-1] != INF:
        dp += [INF]
    dp = list(map(min, zip([0] + [hgt + P if hgt <= H else INF for hgt in dp], dp)))

dp += [INF]
print(dp.index(INF) - 1)


### FIXED CODE ###

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for i, (H, P) in enumerate(HPs, 1):
    if dp[-1] != INF:
        dp += [INF]

    for j in range(1, len(dp))[::-1]:
        hgt = dp[j - 1]
        if hgt <= H:
            dp[j] = min(dp[j], hgt + P)

dp += [INF]
print(dp.index(INF) - 1)
### BUGGY CODE ###

a,b,n=map(int,input().strip().split())
t=0
for i in range(n+1):
    if (b-1)<=n:
        t=(a*(b-1)//b)
    else:
        t=(a*n)//b
    
   # t=max(t,((a*i)//b)-(a*(i//b)))
print(t)
    

### FIXED CODE ###

a,b,n=map(int,input().strip().split())
t=0
if (b-1)<=n:
        t=(a*(b-1)//b)
else:
        t=(a*n)//b
    
   # t=max(t,((a*i)//b)-(a*(i//b)))
print(t)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in marix and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n= int(input())
st=list(map(int,input().split()))
#print(st)
for i in range(n):
    list =[[0]*2 for i in range(n)]
    
for j in range(len(list)):
    list[j][0]=j+1
    list[j][1]=st[j]
    
list.sort(key=lambda x: x[1])
#print(list)

for k in range(len(list)):
    print(list[k][0],end=' ')

### FIXED CODE ###

n= int(input())
st=list(map(int,input().split()))
#print(st)
list =[[0]*2 for i in range(n)]
    
for j in range(len(list)):
    list[j][0]=j+1
    list[j][1]=st[j]
    
list.sort(key=lambda x: x[1])
#print(list)

for k in range(len(list)):
    print(list[k][0],end=' ')
### BUGGY CODE ###

INF = 1_000_000_007


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    a = n
    for i in range(n - 1, n - k, -1):
        a *= i
    b = 1
    for i in range(2, k + 1):
        b *= i
    return a // b


N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        res = 0
    else:
        _t = 0
        for i in range(t // 2 + 1):
            _t += comb(t - i, i)
        res *= _t
print(res % INF)


### FIXED CODE ###

MOD = 10 ** 9 + 7
N, M = list(map(int, input().split()))
B = [True] * (N + 1)
D = [1] + [0] * N
for _ in range(M):
    a = int(input())
    B[a] = False
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if B[j]:
            D[j] = (D[j] + D[i]) % MOD
print(D[N])
### BUGGY CODE ###

X = input()

idx = 0

while idx < len(X)-1:
    if X[idx] == 'S':
        if X[idx+1] == 'T':
            X = X[:idx] + X[idx+2:]
            idx = max(-1, idx-2)
    idx += 1

print(len(X))

### FIXED CODE ###

X = input()

s, t = 0, len(X)//2
cnt = 0
used = 0
for x in X:
    if x == 'S':
        s += 1
        if t-used > 0:
            cnt += 1
            used += 1
    else:
        used = max(0, used-1)
        t -= 1

print(len(X)-cnt*2)
### BUGGY CODE ###

K, S = map(int, input().split())
res = 0
for X in range(0, K+1):
    for Y in range(0, K+1):
        for Z in range(0, K+1):
            total = X + Y + Z
            if total == S:
                res += 1
print(res)

### FIXED CODE ###

K, S = map(int, input().split())
res = 0
for X in range(0, K+1):
    for Y in range(0, K+1):
            total = X + Y
            if S - total >=0 and S - total <= K:
                res += 1
print(res)
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
    l.append(input())

alp=[chr(_) for _ in range(97,97+26)]
res=[0]
res2=[0]
ans=0

for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    tmp2=0
    for z in range(len(res)):
        if aa==res[z]:
            tmp2+=res2[z]
            res2[z]+=1
    if tmp2==0:
        res.append(aa)
        res2.append(1)
    ans+=tmp2

print(int(ans))

### FIXED CODE ###

import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

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

import sys
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
i = 1
while i <= N:
  print(li.count(i))
  i += 1

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
li1 = [0]*N
for i in li:
  li1[i-1] += 1
for i in li1:
  print(i)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

import numpy as np

ans = 0
b = np.array(a[0])

for i in range(1,n):
    b-=1
    ans += np.count_nonzero(b == -a[i])
    b = np.append(b, a[i])

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

from collections import defaultdict
d = defaultdict(int)
ans = 0

for i in range(n):
    ans += d[i-a[i]]
    d[a[i]+i] += 1

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

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

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j]
        cost[i|move2] = min(cost[i|move2], cost[i]+a[j])

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])

### FIXED CODE ###

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

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] > cost[i]+a[j]:
            cost[i|move2] = cost[i]+a[j]

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])
### BUGGY CODE ###

#input
r_1, c_1, r_2, c_2 = map(int, input().split())

#output
mod = 10**9 + 7

n_ = 2*10**6 + 1
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)

### FIXED CODE ###

#input
r_1, c_1, r_2, c_2 = map(int, input().split())

#output
mod = 10**9 + 7

n_ = 2*10**6 + 1
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

answer = 0
for j in range(c_1, c_2+1):
    answer += cmb(r_2+j+1, j+1) % mod - cmb(r_1+j, j+1) % mod

print(answer % mod)
### BUGGY CODE ###

import copy
import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)
 
m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: 
            m = n
    else:
        done.append(now)
        for i in range(d):
            if not i in done:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, done.copy())
 
for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-2):
    if n-i-1-a[i]>0:
        num1=i+a[i]
        for j in range(i+a[i]+1,n):
            if j-num1==a[j]:
                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1=[0]*(2*(10**5)+10)
num2=[0]*(2*(10**5)+10)
for i in range(n):
    if a[i]+i+1<2*(10**5)+5:
        num1[a[i]+i+1]+=1
    if a[i]+1<i+1:
        num2[-a[i]+i+1]+=1
ans=0
for i in range(len(num1)):
    ans+=num1[i]*num2[i]
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
# print(a)
# print(n)
ans = [0 for _ in range(n)]


for i_out in range(n):
    for i_in in range(i_out+1, n):  #
        if a[i_out] == a[i_in]:
            ans[i_out] = 1
            ans[i_in] = 1

        if i_out == i_in:
            continue
        # print(i_out, i_in)
        if int(a[i_in] / a[i_out]) == a[i_in] / a[i_out]:
            ans[i_in] = 1
            # print('!')

# print(ans)
print(n - sum(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
maxa = max(a)
a_s = set(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        for j in range(i, maxa+1, i):
            s.add(j)
        ans += 1

print(ans - len(same_s))
### BUGGY CODE ###

def solve(i,m,A):
    global n
    if m == 0 :
        return True
    elif i >= n :
        return False
    else:
        return (solve(i+1,m,A) or solve(i+1,m-A[i],A))

global n
n = int(input())
st = input()
A = list(map(int,st.split()))
# dont use q(num of ans patarn) dumping!
input()
st = input()
ans = list(map(int,st.split()))

for x in ans:
    if(solve(0,x,A) == True):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

n = int(input())
S = {}
for i in range(n):
    s = input()
    if s in S:
        S[s] += 1
    else:
        S[s] = 1

L = sorted([kv[0] for kv in S.items() if kv[1] == max(S.values())])
for i in range(len(L)):
    print(L[i])


### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

L = Counter(S)
m = 0
for v in L.values():
    m = max(m, v)
ans = []
for k, v in L.items():
    if v == m:
        ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

N = int(input())
s = [input() for i in range(N)]

l = []
ans = 0
for i in range(N):
    if sorted(s[i]) in l:
        ans += l.count(sorted(s[i]))
    l.append(sorted(s[i]))

print(ans)

### FIXED CODE ###

import collections
N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

ans = 0
cnt = collections.Counter(s)
for i in cnt.values():
    if i > 1:
        ans += i*(i-1)//2

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

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count=0
    a,b=map(int,(input().split()))
    if a==b:
        if is_prime(a) and is_prime((a+1)/2):
            count+=1
    for i in range(a,b,2):
        if is_prime(i) and is_prime((i+1)/2):
            count+=1
    print(count)



### FIXED CODE ###

from sys import stdin
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99991:99999]=[oppai[99990]]*8
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)
### BUGGY CODE ###

import itertools
from functools import reduce

N = int(input())

def prime_f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
    
A = prime_f(N)

F = []
L = []

distance = []

C = []

if len(A) == 1:
  print(N - 1)
else:
  for i in range(1,len(A)):
    C = list(itertools.combinations(A,i))
    for j in range(0,len(C)):
      totalC = reduce(lambda x,y:x*y,C[j])
      div = int(N / totalC)
      distance.append(div + totalC)

  print(min(distance) - 2)

### FIXED CODE ###

n = int(input())

distance = 10 ** 12

i = 1

while i * i <= n:
  if n % i == 0:
    m = int(n / i)
    move = (m - 1) + (i - 1)
    if move < distance:
      distance = move
  i += 1

print(distance)
### BUGGY CODE ###

from collections import deque, _heapq
N, K = map(int, input().split())
V = deque(map(int, input().split()))

class Money:
    def __init__(self):
        self.yen = 0
        self.red = []

    def value(self):
        return self.yen + sum(self.red)

    def add(self, yen):
        if yen >= 0:
            self.yen += yen
        else:
            self.red.append(yen)

    def remove(self, yen):
        if yen >= 0:
            self.yen -= yen
        else:
            self.red.remove(yen)

#mny = Money()
def get(cnt, mny, lstop, rstop):
    ans = mny.value()

    if cnt <= 0:
        return ans

    if len(V) > 0:

        if lstop == 0:
            w = V.popleft()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, lstop, rstop))
            mny.remove(w)
            V.appendleft(w)
        elif lstop > 0:
            lstop -= 1

        if rstop == 0:
            w = V.pop()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, -1, rstop))
            mny.remove(w)
            V.append(w)

    if len(mny.red) > 0:
        w = min(mny.red)
        mny.red.remove(w)

        V.appendleft(w)
        ans = max(ans, get(cnt-1, mny, -1, -1))
        V.popleft()

        V.append(w)
        ans = max(ans, get(cnt-1, mny, -1, -1))
        V.pop()

        mny.red.append(w)    

    return ans

print(get(K, Money(), 0, 0))


### FIXED CODE ###

from collections import deque, _heapq
N, K = map(int, input().split())
V = deque(map(int, input().split()))

class Money:
    def __init__(self):
        self.yen = 0
        self.red = []

    def value(self):
        return self.yen + sum(self.red)

    def add(self, yen):
        if yen >= 0:
            self.yen += yen
        else:
            self.red.append(yen)

    def remove(self, yen):
        if yen >= 0:
            self.yen -= yen
        else:
            self.red.remove(yen)

#mny = Money()
def get(cnt, mny, lstop, rstop):
    ans = mny.value()

    if cnt <= 0:
        return ans

    if len(V) > 0:

        if lstop == 0:
            w = V.popleft()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, lstop, rstop))
            mny.remove(w)
            V.appendleft(w)
        elif lstop > 0:
            lstop -= 1

        if rstop == 0:
            w = V.pop()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, -1, rstop))
            mny.remove(w)
            V.append(w)

    if len(mny.red) > 0:
        w = min(mny.red)
        mny.red.remove(w)

        V.appendleft(w)
        ans = max(ans, get(cnt-1, mny, -1, -1))
        V.popleft()

        mny.red.append(w)    

    return ans

print(get(K, Money(), 0, 0))
### BUGGY CODE ###

N , K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf] * N
if K == 1:
    ans = 0
    for i in range(N - 1):
        ans += abs(h[i + 1] - h[i])
    print(ans)
    exit()

for i in range(N):
    if i == 0:
        min_cost = 0
    elif i == 1:
        min_cost = abs(h[1] - h[0])
    elif i == 2:
        min_cost = min(abs(h[2] - h[0]) + dp[0], abs(h[2] - h[1]) + dp[1])
    else:
        tmp_min = min(abs(h[i] - h[i - K]) + dp[i - K] , abs(h[i] - h[i - K + 1]) + dp[i - K + 1])
        for j in range(K - 2):
            tmp_min = min(abs(h[i] - h[i - K + 2 + j]) + dp[i - K + 2 + j], tmp_min)
        min_cost = tmp_min
    dp[i] = min_cost
#print(dp)
print(dp[N - 1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N , K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf] * N
if K == 1:
    ans = 0
    for i in range(N - 1):
        ans += abs(h[i + 1] - h[i])
    print(ans)
    exit()

for i in range(N):
    if i == 0:
        min_cost = 0
    elif i == 1:
        min_cost = abs(h[1] - h[0])
    else:
        current = h[i]
        tmp_min = min(abs(current - h[i - K]) + dp[i - K] , abs(current - h[i - K + 1]) + dp[i - K + 1])
        for j in range(K - 2):
            tmp_min = min(abs(current - h[i - K + 2 + j]) + dp[i - K + 2 + j], tmp_min)
        min_cost = tmp_min
    dp[i] = min_cost
#print(dp)
print(dp[N - 1])
### BUGGY CODE ###

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

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

for i in range(a):
    if c[i] != []:
        c[i].sort()

#print(z)
x =''
y = ''
for j in range(b):                    
    x = str(z[j][0])
    x = '0' * (6 - len(x)) + x
    y = str(c[z[j][0] - 1].index(z[j][1]) + 1)
    y = '0' * (6 - len(y)) + y
    print(x + y)

### FIXED CODE ###

import bisect
a,b = map(int,input().split())

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

for i in range(a):
    if c[i] != []:
        c[i].sort()

x =''
y = ''
for j in range(b):                    
    x = str(z[j][0])
    x = '0' * (6 - len(x)) + x
    y = str(bisect.bisect(c[z[j][0] - 1], z[j][1]))
    y = '0' * (6 - len(y)) + y
    print(x + y)
### BUGGY CODE ###

n=int(input())

X=list(map(int,input().split()))

for i in range(n):
    S=X[:i]+X[i+1:]
    S.sort()
    print(S[int(n/2)-1])

### FIXED CODE ###

n=int(input())

X=list(map(int,input().split()))
sort_X=sorted(X)
for i in range(n):
    if X[i]<sort_X[int(n/2)]:
        print(sort_X[int(n/2)])
    else:
        print(sort_X[int(n/2)-1])
### BUGGY CODE ###

k,s=map(int,input().split())
x=[0]*k
for i in range(0,k):
  x[i]=i
x.append(k)
a=int(s/3)-1
#y=x[-a:]
count=0
for i in range(0,len(x)):
  for j in range(0,len(x)):
    if s-x[i]-x[j] in x:
      count=count+1
print(count)


### FIXED CODE ###

k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))
### BUGGY CODE ###

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

while k > 0:
  if b < a:
    b *= 2
    k -= 1
  elif c < b:
    c *= 2
    k -= 1

if a < b and b < c:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

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

if b > a:
  multiplier = 2 ** k
  if c * multiplier > b:
    ans = 'Yes'
  else:
    ans = 'No'
else:
  while b <= a:
    b *= 2
    k -= 1
  multiplier = 2 ** k
  if c * multiplier > b:
    ans = 'Yes'
  else:
    ans = 'No'

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

# -*- coding: utf-8 -*-
import sys

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


mod=10**9+7

T=[1]
for n in range(N):
	W=[0]		#WA:累積和
	L=T
	l=len(L)
	a=A[n]
	for j,x in enumerate(L):
		if j==0:	W.append(x)
		else:	W.append( W[-1]+x )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

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


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0