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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    # W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
used=set()
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
    used.add(L-1)
    used.add(R-1)

q=queue.Queue()
dist=[-1]*N

while used!=set():
    a=used.pop()
    q.put(a)
    dist[a]=0
    while not q.empty():
        From=q.get()
        if From in used:
            used.remove(From)
        for l in s[From]:
            To,w=l
            if dist[To]==-1:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")


### FIXED CODE ###

import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))

q=queue.Queue()
dist=[None]*N

for i in range(N):
    if dist[i]==None:
        dist[i]=0
        q.put(i)
    while not q.empty():
        From=q.get()
        for l in s[From]:
            To,w=l
            if dist[To]==None:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")
### BUGGY CODE ###

#D
#入力
n,a,b=map(int,input().split())

#処理
import math
Z=[[-1 for i in range(b+1)] for j in range(n+1)]

def comb(n,r):
    if r==0 or r==n:
        Z[n][r]=1
        return 1
    elif Z[n][r]>0:
        return Z[n][r]
    else:
        Z[n][r]=comb(n-1,r-1)+comb(n-1,r)
        return Z[n][r]
        

print((2**n-comb(n,a)-comb(n,b)-1)%(10**9+7))

### FIXED CODE ###

# D
#入力
n,a,b=map(int,input().split())

#諸関数
def pront(X):
    #デバッグ用プリント
    #環境変数としてdebugを確保して、それが1なら内容を出力
    if debug==0:
        print(X)

#デバッグ用
debug=1#0:本番,1:デバッグ中

#処理
#定数
base=(10**9)+7

#関数
    #10*9+7で割ったあまりを返し続ける
def add(a,b):#a+b
    return(((a%base)+(b%base))%base)
def sub(a,b):#a-b
    return (((a%base)-(b%base))%base)
def multi(a,b):#a*b
    return(((a%base)*(b%base))%base)
def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

#割り算はフェルマーの小定理に基づいて考える
def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

    #その他演算
def fact(m,n):#m~nの積(m<n)
    x=1
    for i in range(m,n+1):
        x=multi(x,i)
    return x
def comb(n,r):
    return div(fact(n-r+1,n),fact(1,r))
#処理
Z=sub(sub(sub(exp(2,n),comb(n,a)),comb(n,b)),1)
print(Z)
### BUGGY CODE ###

n, k, q = list(map(int, input().split()))
a = [int(input()) for i in range(q)]
p = [k - q] * n
'''
p = []
for i in range(n):
    p.append(k)
for i in range(q):
    for j in range(n):
        if(j + 1 == a[i]):
            pass
        else:
            p[j] = p[j] - 1
#print(p)
for i in range(n):
    if(p[i] > 0):
        print('Yes')
    else:
        print('No')
'''
for i in range(q):
    for j in range(n):
        if(j + 1 == a[i]):
            p[j] += 1
for i in range(n):
    if(p[i] > 0):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = list(map(int, input().split()))
a = [int(input()) for i in range(q)]
p = [k - q] * n
for i in range(q):
    p[a[i] - 1] += 1
for i in range(n):
    if(p[i] > 0):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
t=[(i+1)/2 for i in p]
a=[]
for i in range(n+1-k):
  a.append(sum(t[i:i+k]))
print(max(a))


### FIXED CODE ###

import itertools

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x:(x+1)/2,a))

a=[0]+list(itertools.accumulate(a))
ans=0

for i in range(n-k+1):
  ans=max(ans,a[i+k]-a[i])
  
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,k = map(int,input().split())
sl = [0]*n
dl = [0]*n
tree = [[] for i in range(n)]
mod = 10**9+7

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

def perm(n, k = 1):
  pdt = 1
  if n != int(n) or k != int(k):
    raise ValueError("perm() not defined for float object")
  elif k < 0:
    pdt = 0
  elif n < 0:
    pdt = 0
  else:
    for x in range(n, n-k, -1):
      pdt *= x
  return pdt

def dfs(x,depth,k):
  sl[x] = 1
  dl[depth] += 1
  child = 0
  ans = 1
  for i in tree[x]:
    if sl[i] == 0:
      ans *= dfs(i,depth+1,k)
      ans %= mod
      child += 1
  if depth == 0:
    ans *= perm(k-1,child)
    ans %= mod
  else:    
    ans *= perm(k-2,child)
    ans %= mod
  return ans

print(dfs(0,0,k)*k%mod)

### FIXED CODE ###

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

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())

ans=0
for i in range(1,N):
  ans+=i

print(ans)

### FIXED CODE ###

N=int(input())

print((N*(N-1))//2)
### BUGGY CODE ###

s = input()
n = len(s)
MOD = 1e9 + 7
dp = [[0] * 13 for _ in range(n)]
for i in range(10):
	if s[0] == "?":
		dp[0][i] = 1
	else:
		cur = ord(s[0]) - ord("0")
		dp[0][cur] = 1
for i in range(1, n):
	if s[i] != "?":
		cur = ord(s[i]) - ord("0")
		for j in range(13):
			dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
	else:
		for j in range(13):
			for cur in range(10):
				dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
#print(dp)
print(int(dp[n - 1][5] % MOD))

### FIXED CODE ###

s = input()
n = len(s)
MOD = 1e9 + 7
dp = [[0] * 13 for _ in range(n)]
for i in range(10):
	if s[0] == "?":
		dp[0][i] = 1
	else:
		cur = ord(s[0]) - ord("0")
		dp[0][cur] = 1
for i in range(1, n):
	if s[i] != "?":
		cur = ord(s[i]) - ord("0")
		for j in range(13):
			dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
	else:
		for j in range(13):
			for cur in range(10):
				dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
#print(dp)
print(int(dp[n - 1][5] % MOD))
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def GCM(a,b):
    while(a%b!=0):
        a,b = b,a%b
    return b

def calc(a,b):
    count_two_a = 0
    count_two_b = 0
    while(a%2==0):
        a //= 2
        count_two_a += 1
    while(b%2==0):
        b //= 2
        count_two_b += 1
    if count_two_a != count_two_b:
        return 0

    return pow(2,count_two_a) * a * b // GCM(a,b)





def main():
    N,M = LI()
    A = LI()

    count_two = 0
    while(A[0]%2==0):
        A[0] //= 2
        count_two += 1
    pow_two = pow(2,count_two)

    for i in range(1,N):
        if A[i]%pow_two != 0:
            print(0)
            return
        A[i] //= pow_two
        if A[i]%2 == 0:
            print(0)
            return

    gcm = A[0]

    for i in range(1,N):
        gcm = calc(gcm,A[i])

    ans = M//(gcm*pow_two//2)
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def GCM(a,b):
    while(a%b!=0):
        a,b = b,a%b
    return b

def main():
    N,M = LI()
    A = LI()

    count_two = 0
    while(A[0]%2==0):
        A[0] //= 2
        count_two += 1
    pow_two = pow(2,count_two)

    for i in range(1,N):
        if A[i]%pow_two != 0:
            print(0)
            return
        A[i] //= pow_two
        if A[i]%2 == 0:
            print(0)
            return

    tmp = A[0]

    for i in range(1,N):
        tmp = tmp * A[i] // GCM(tmp,A[i])
        if tmp > M:
            print(0)
            return

    ans = M//(tmp*pow_two//2)
    if ans%2==0:
        ans -= 1
    ans -= ans//2
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            # que.put(nv)
            q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

n = int(input())
s = input()

R = []
G = []
B = []

for i in range(n):
    if s[i] == "R":
        R.append(i)
    if s[i] == "G":
        G.append(i)
    if s[i] == "B":
        B.append(i)

ans = 0
for r in R:
    for g in G:
        for b in B:
            if r < g and g < b and (b - g) != (g - r):
                ans += 1
            elif r < b and b < g and (g - b) != (b - r):
                ans += 1
            elif g < b and b < r and (r - b) != (b - g):
                ans += 1
            elif g < r and r < b and (b - r) != (r - g):
                ans += 1
            elif b < r and r < g and (g - r) != (r - b):
                ans += 1
            elif b < g and g < r and (r - g) != (g - b):
                ans += 1 

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

R_cnt = s.count("R")
G_cnt = s.count("G")
B_cnt = s.count("B")

ans = R_cnt * G_cnt * B_cnt

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n: break
        if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
            ans -= 1

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

N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [0 for __ in range(N)] for _ in range(N)]
for path in P:
    A[path[1]-1][path[0]-1]=1
    A[path[0]-1][path[1]-1]=1
#print(A)
depth_list = [0 for _ in range(N)]
next_generation = set([0])
depth = 0
old_generation = set()
direction = [0 for _ in range(N)]
while len(next_generation)!=0:
    #print('next_gen',next_generation)
    current = next_generation
    [old_generation.add(node) for node in next_generation]
    next_generation = set()
    for index in current:
        depth_list[index]=depth
    for node in current:
        #print('node',node,':',A[node])
        
        #print('old',old_generation)
        for i,neighbor in enumerate(A[node]):
            #print("trm",neighbor)

            if neighbor == 1 and i not in old_generation:
                #print("unseen",i)
                next_generation.add(i)
                direction[i]=node+1
    depth+=1
if len(old_generation) != N:
    print('No')
else:
    print('Yes')
    for d in direction[1:]:
        print(d)
#print(depth_list)
        

### FIXED CODE ###

from collections import deque
N, M = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(M)]
A = [ [] for _ in range(N)]
#node_info = [{'node':d,'connect':[],'depth':-1,'dir':-1} for d in range(N)]

for path in P:
    A[path[1]-1].append(path[0]-1)
    A[path[0]-1].append(path[1]-1)
#print(A)

previous = [-1 for i in range(N)]
previous[0]=0

que = deque([0])

while len(que) != 0:
    v = que.popleft()
    for v_i in A[v]:
        if previous[v_i] != -1:
            continue
        else:
            que.append(v_i)
            previous[v_i] = v
for i in range(N):
    if previous[i] == -1:
        print('No')
        exit()
print('Yes')
for i in range(1,N):
    print(previous[i]+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

n= int(input())
A = [int(a) for a in input().split()]

A = np.array(A)

for i in range(n-1):
    A = A - 1
    print(n-1 -np.nonzero(A)[0].size)
print("0")


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [int(a) for a in input().split()]

sub_list = [0] *n

for a in A:
  sub_list[a-1] +=1

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

#coding:utf-8

n = int(input())
s = input()

count = 0
r, g, b = 0, 0, 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    elif i == 'B':
        b += 1

count = r * g * b

for i in range(n-2):
    si = s[i]
    for j in range(i+1,n-1):
        sj = s[j]
        if si == sj:
            continue
        c_set = {'R','G','B'}
        c_set = c_set - {si,sj}
        nk = 2 * j - i
        if not nk < n:
            continue
        if not nk > j:
            continue
        if s[nk] in c_set:
            count -= 1

print("{}".format(count))

### FIXED CODE ###

#coding:utf-8

n = int(input())
s = input()

count = 0
r, g, b = 0, 0, 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    elif i == 'B':
        b += 1

count = r * g * b

for i in range(n-2):
    si = s[i]
    for j in range(i+1,n-1):
        sj = s[j]
        nk = 2 * j - i
        if not nk < n:
            break
        snk = s[nk]
        if {si, sj, snk} == {'R','G','B'}:
            count -= 1

print("{}".format(count))
### BUGGY CODE ###

#encoding: utf-8
import sys

input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

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

# 入力の網羅は 30,000C3 の組み合わせとなり全探索は不可能
# 出力は000〜999までの10**3であり、3*10**4とのかけあわせで
# O(10**7)であれば、制限時間内に計算が可能（出力全探索による貪欲法）

# PIN[0]に該当する文字が入力Sから見つかった場合、
# そのSを利用するのが最も効果的であるので貪欲法が利用できる
# (最初に見つかったものを使うとのちのちの制約に引っかかる、というような場合はDPなどを考慮)

# s in S に対し、PIN[0]に該当するsがあれば PIN[1]に該当するsを探索、、という繰り返しで3桁分見つかればans+=1

ans = 0
for i in range(1000):
	pin = str(i).zfill(3)
	cnt = 0 # 該当するsのカウント
	idx = 0 # 探索するPINのインデックス
	for s in S:
		if s==pin[idx]:
			cnt += 1 # カウントアップ
			idx += 1 # インデックスをPINの次の文字へ送る
			if idx == 3:
				break
	if cnt == 3:
		#print(pin)
		ans += 1
				
print(ans)

### FIXED CODE ###

#encoding: utf-8
import sys

input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

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

# 入力の網羅は 30,000C3 の組み合わせとなり全探索は不可能
# 出力は000〜999までの10**3であり、3*10**4とのかけあわせで
# O(10**7)であれば、制限時間内に計算が可能（出力全探索による貪欲法）

# PIN[0]に該当する文字が入力Sから見つかった場合、
# そのSを利用するのが最も効果的であるので貪欲法が利用できる
# (最初に見つかったものを使うとのちのちの制約に引っかかる、というような場合はDPなどを考慮)

# s in S に対し、PIN[0]に該当するsがあれば PIN[1]に該当するsを探索、、という繰り返しで3桁分見つかればans+=1

ans = 0
for i in range(1000):
	pin = str(i).zfill(3)
	cnt = 0 # 該当するsのカウント
	idx = 0 # 探索するPINのインデックス
	for s in S:
		if s==pin[idx]:
			cnt += 1 # カウントアップ
			idx += 1 # インデックスをPINの次の文字へ送る
			if idx == 3:
				break
	if cnt == 3:
		#print(pin)
		ans += 1
				
print(ans)
### BUGGY CODE ###

def main():
  S = input()
  Q = int(input())
  import sys
  que = [list(sys.stdin.readline().split()) for _ in range(Q)]
  judge = False
  for l in que:
    if int(l[0])==1:
      if judge:
        judge = False
      else:
        judge = True

    elif int(l[0])==2:
      f,c = int(l[1]),l[2]
      if judge:
        if f==1:
          f=2
        elif f==2:
          f=1
      if f==1:
        S=c+S
      elif f==2:
        S=S+c

  if judge:
    S=S[::-1]
  print(S)
  
main()

### FIXED CODE ###

def main():
  S = input()
  Q = int(input())
  import sys
  que = [list(sys.stdin.readline().split()) for _ in range(Q)]
  pre=''
  post=''
  judge = False
  for l in que:
    if int(l[0])==1:
      if judge:
        judge = False
      else:
        judge = True

    elif int(l[0])==2:
      f,c = int(l[1]),l[2]
      if judge:
        if f==1:
          f=2
        elif f==2:
          f=1
      if f==1:
        pre = ''.join([pre,c])
      elif f==2:
        post = ''.join([post,c])

  pre = pre[::-1]
  S = pre+S+post
  if judge:
    S=S[::-1]
  print(S)
  
main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]
# V = [set() for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    # V[a].add(b)
    V[a].append(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

N, Q = [int(x) for x in input().split()]
# V = [set() for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    # V[a].add(b)
    V[a].append(b)

C = [0] * N

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

ANS = [0] * N


def dfs(n, val):
    ANS[n] += (val + C[n])
    for next in V[n]:
        dfs(next, val + C[n])


def main():
    dfs(0, 0)
    print(" ".join([str(x) for x in ANS]))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,S = inputIL()
l = inputIL()

dp = [[[0,0] for s in range(4000)] for r in range(4000)]

for r in range(N):
  for s in range(S):
    if s == 0:
      dp[r][s] = [1,r+2]
    if r == 0:
      if s == l[r]:
        dp[r][s] = [1,1]
      else:
        dp[r][s] = [0,0]
    else:
      dp[r][s] = [dp[r-1][s][0] + dp[r-1][s][1] + dp[r-1][s-l[r]][1],dp[r-1][s][1]+dp[r-1][s-l[r]][1]]


print(dp[N-1][S][0])

### FIXED CODE ###

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

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

N,W = map(int, input().split())
dp = [0]*(W+1)

for i in range(1,N+1):
    w,v = map(int,input().split())
    dp[w:W+1] = [max(dp[i+w],dp[i]+v) for i in range(W-w+1)]

print(dp[-1])

### FIXED CODE ###

N, W = map(int, input().split())
 
import numpy as np
dp = np.zeros(W + 1, dtype='int64')
 
for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)
 
print(dp[-1])