Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** m):
    bag = [0]*n
    cnt = 0
    for j in range(m):  
        if ((i >> j) & 1):  
            bag[j]+=1
    for l in range(m):
        res = 0
        for h in range(1,len(x[l])):
            res += bag[x[l][h]-1]
        if res%2!=p[l]:
            break
        else:
            cnt += 1
    if cnt==m:
        ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
    bag = []
    cnt = 0
    for j in range(n):  
        if ((i >> j) & 1):  
            bag.append(True)
        else:
            bag.append(False)
    for l in range(m):
        res = 0
        for h in x[l][1:]:
            if bag[h-1]:
                res += 1
        if res%2!=p[l]:
            break
        else:
            cnt += 1
    if cnt==m:
        ans += 1
print(ans)
S = input()
k = int(input())
goal = ord('z') + 1
ans = []
for c in S:
    if c == 'a': continue
    d = goal - ord(c)
    if k >= d:
        k -= d
        ans.append('a')
    else:
        ans.append(c)
last = (k + ord(ans[-1]) - ord('a')) % 26
ans[-1] = chr(ord('a') + last)
print(''.join(ans))


### FIXED CODE ###

S = input()
k = int(input())
goal = ord('z') + 1
ans = []
for c in S:
    if c == 'a':
        ans.append('a')
        continue
    d = goal - ord(c)
    if k >= d:
        k -= d
        ans.append('a')
    else:
        ans.append(c)
last = (k + ord(ans[-1]) - ord('a')) % 26
ans[-1] = chr(ord('a') + last)
print(''.join(ans))
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:            
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m and cover[ny][nx] < 0:
                q.append((ny, nx, step + 1))
    return cover

def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min(sc[y][x] for sc in scover):
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    if data == "0":
        break
    m, n = map(int, data.split())
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()

### FIXED CODE ###

#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)

while True:
    data = raw_input()
    m, n = map(int, data.split())
    if m == 0:
        break
    s = input()
    spos = [map(int, raw_input().split()) for _ in xrange(s)]
    t = input()
    tpos = [map(int, raw_input().split()) for _ in xrange(t)]
    print solve()
# ANSHUL GAUTAM
# IIIT-D
 
def get_all_substrings(input_string):
  length = len(input_string)
  return list([input_string[i:j+1] for i in range(length) for j in range(i,length)])


s = input()
K = int(input())  
l = get_all_substrings(s)
l = sorted(l)
L = []
for i in l:
	if(i not in L):
		L.append(i)
print(L[K-1])








### FIXED CODE ###

s = input()
K = int(input())
 
 
L = []
 
for i in range(1, K+1):
    for j in range(len(s)-i+1):
        L.append(s[j:j+i])
 
M = sorted(list(set(L)))
 
print(M[K-1])
n, m = map(int, input().split())
key_price = [0] * m
box_price = [(-1, [-1])] * (n+1)
box_key = [set([]) for _ in range(n+1)]
for key in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key_price[key] = a
    for i in c:
        if box_price[i][0] == -1:
            box_price[i] = (a, [key])
        elif box_price[i][0] > a:
            box_price[i] = (a, [key])
        elif box_price[i][0] == a:
            box_price[i] = (a, box_price[i][0] + [key])
        box_key[i].add(key)


def cost(using_keys):
    ret = 0
    for k, v in using_keys.items():
        if v >= 1:
            ret += key_price[k]
    return ret


from collections import defaultdict
keys = defaultdict(int)
kbx = {i: 0 for i in range(1, n+1)}
for i in range(1, n+1):
    keys[box_price[i][1][0]] += 1
    kbx[i] = box_price[i][1][0]

ans = cost(keys)

for key in range(m):
    for i in range(1<<n):
        ks = keys
        kbx1 = kbx
        for b in range(n):
            if i & (1 << b) and key in box_key[b+1]:
                ks[kbx[b+1]] -= 1
                ks[key] += 1
                kbx1[b+1] = key
        tmp = cost(ks)
        if ans > tmp:
            keys = ks
            kbx = kbx1
            ans = tmp

print(ans)



### FIXED CODE ###

n, m = map(int, input().split())
r = [2**i for i in range(n+1)]

price = [0] * m
mask = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    for box in map(int, input().split()):
        mask[i] += r[box-1]
    price[i] = a


inf = 10**9
dp = [[inf] * (1 << n) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for j in range(1 << n):
        dp[i+1][j | mask[i]] = min(
            dp[i][j] + price[i],
            dp[i+1][j | mask[i]]
        )
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = dp[m][(1 << n) - 1]
if ans == inf:
    print(-1)
else:
    print(ans)
max = 0
i = 0
j = 0
k = 0
n_max = 19

price = []
for k in range(n_max):
    price.attend(int(raw_input())
    
for i in range(n_max):
    for j in range(k, n_max):
        if max <= price[j] - price[i]:
            max = price[j] - price[i]
print max

### FIXED CODE ###

import sys

n = int(raw_input())

min_R = int(raw_input())
nums = map(int, sys.stdin.readlines())

ans = -10**9

for num in nums:
    if num - min_R > ans:
        ans = num - min_R
    if num < min_R:
        min_R = num
        
print ans
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        tmp = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

ans = 0
for i in range(1,N+1):
    ans = max(ans,distance(i))
print(ans)
N, M = map(int, input().split())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    c[i] = -c[i]
    
INF = 10 ** 10
dist = [INF] * N

dist[0] = 0

for loop in range(N-1):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]

ans = dist[N-1]

nega = [0] * N

for loop in range(N):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]
            nega[b[i]-1] = 1
        if nega[a[i]-1] == 1:
            nega[b[i]-1] = 1

if nega[N-1]:
    print('inf')
else:
    print(-ans)

### FIXED CODE ###

N, M = map(int, input().split())
a = [0] * M
b = [0] * M
c = [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    c[i] = -c[i]
    
INF = 10 ** 13
dist = [INF] * N

dist[0] = 0

for loop in range(N-1):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]

ans = dist[N-1]

nega = [0] * N

for loop in range(N):
    for i in range(M):
        if dist[a[i]-1] == INF:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]
            nega[b[i]-1] = 1
        if nega[a[i]-1] == 1:
            nega[b[i]-1] = 1

if nega[N-1]:
    print('inf')
else:
    print(-ans)
N,M = map(int,input().split())
A,B = [],[]
for i in range(N):
    A_next, B_next = map(int,input().split())
    A.append(A_next)
    B.append(B_next)
shop = list(zip(A,B))
shop.sort(key=lambda x:x[0])
def count(i,M):
    if(M==0):
        return 0
    elif(shop[i][1]<=M):
        return count(i+1,M-shop[i][1])+shop[i][0]*shop[i][1]
    else:
        return M*shop[i][0]
a = count(0,M)
print(a)

### FIXED CODE ###

N,M = map(int, input().split())
A,B = [],[]
for i in range(N):
    A_next, B_next = map(int,input().split())
    A.append(A_next)
    B.append(B_next)
l = sorted(list(zip(A,B)), key=lambda x:x[0])
count = 0
value = 0
i = 0
while(count<M):
    if(M-count<l[i][1]):
        value = value + l[i][0]*(M-count)
        break
    else:
        value = value + l[i][0]*l[i][1]
        count = count + l[i][1]
        i = i + 1
print(value)
n = int(input())
a = [1]

if n % 2 == 1:
    n -= 1

if n % 2 == 0:
    for i in range(int(n / 2)):
        a.append(2 * a[i])

print(a[-1]*2 - 1)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 0
if a % b ==0:
    ans = a//b
else:
    ans = a//b + 1

print(ans)
n = int(input())
s = input()

dp = [[-1]*n for _ in range(n)]

def calc(x, y):
    if x >= n or y >= n:return 0
    if dp[x][y] != -1:return dp[x][y]
    if s[x] != s[y]:
        dp[x][y] = 0
        return dp[x][y]
    dp[x][y] = calc(x+1, y+1) + 1
    return dp[x][y]
        
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans = max(ans, min(calc(i, j), j-i))

print(ans)

### FIXED CODE ###

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

A = 1234567
MOD = 10000000000000007

def ok(length):
    rolling_hash = 0
    head = pow(A, length, MOD)
    occurence = {}
    for i in range(n):
        rolling_hash = (rolling_hash * A + ord(s[i])) % MOD
        if i - length >= 0:
            rolling_hash = (rolling_hash - head * ord(s[i-length])) % MOD
        if rolling_hash not in occurence:
            occurence[rolling_hash] = []
        occurence[rolling_hash].append(i)

    for key in occurence:
        if occurence[key][-1] - occurence[key][0] >= length:
            return True
    return False

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid):bottom = mid
    else: top = mid

print(bottom)
#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)

#constant
H, W = list(map(int,input().split()))
S = [input() for _ in range(H)]

#variable

#function
@lru_cache(maxsize=None)
def L(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == 1:
            return 1
        else:
            return L(i,j-1) + 1

@lru_cache(maxsize=None)
def R(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == W:
            return 1
        else:
            return R(i,j+1) + 1

@lru_cache(maxsize=None)
def U(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == 1:
            return 1
        else:
            return U(i-1,j) + 1

@lru_cache(maxsize=None)
def D(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == H:
            return 1
        else:
            return D(i+1,j) + 1

#class

#main function
def main():
    maxScore = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            score = L(i,j)+R(i,j)+U(i,j)+D(i,j)-3
            if score > maxScore:
                maxScore = score
    print(maxScore)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129D-Lamp.py

#import list
import sys
import numpy as np

#main function
def main():
    buffer = sys.stdin.buffer
    H, W = list(map(int,buffer.readline().split()))
    S = np.frombuffer(buffer.read(H*(W+1)), dtype="B") == ord(".")
    S = S.reshape((H,W+1))[:,:-1]
    L = np.empty((H,W), dtype="i4")
    R = np.empty((H,W), dtype="i4")
    U = np.empty((H,W), dtype="i4")
    D = np.empty((H,W), dtype="i4")

    L[:,0] = S[:,0]
    for i in range(1,W):
        L[:,i] = (L[:,i-1] + 1) * S[:,i]

    R[:,-1] = S[:,-1]
    for i in range(1,W):
        R[:,-1-i] = (R[:,-i] + 1) * S[:,-1-i]

    U[0] = S[0]
    for i in range(1,H):
        U[i] = (U[i-1] + 1) * S[i]

    D[-1] = S[-1]
    for i in range(1,H):
        D[-1-i] = (D[-i] + 1) * S[-1-i]

    score = L + R + U + D - 3
    print(int(score.max()))


if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = 0
popcount_X = 0

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

def f_func(n):
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  X_10 += int(X[i]) * 2 ** j
  if X[i] == '1':
    popcount_X += 1

popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
fX_plus = X_10 % popcount_X_plus
fX_minus = X_10 % popcount_X_minus

for i in range(N):
  j = N - (i + 1)
  
  Xi = 0
  f = 0
  popcnt = 0
  ans = 1
  
  if X[i] == '0':
    Xi = X_10 + 2**j
    popcnt = popcount_X + 1
    f = (fX_plus + 2**j % popcount_X_plus) % popcount_X_plus
    
  elif X[i] == '1':
    Xi = X_10 - 2**j
    popcnt = popcount_X - 1
    f = (fX_minus - 2**j % popcount_X_minus) % popcount_X_minus
  
  while f > 0:
    f = f_func(f)
    ans += 1
  print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
X = input()
X_10 = int(X, 2)
popcount_X = X.count("1")
popcount_X_plus = popcount_X + 1
popcount_X_minus = popcount_X - 1
f_plus = X_10 % popcount_X_plus
f_minus = X_10 % popcount_X_minus if popcount_X_minus != 0 else 0

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

def f(n):
  if n == 0:
    return 0
  return n % popcount(n)

for i in range(N):
  j = N - (i + 1)
  n = 0
  ans = 1
  
  if X[i] == '0':
#    n = (f_plus + (2**j % popcount_X_plus)) % popcount_X_plus
    n = (f_plus + pow(2, j, popcount_X_plus)) % popcount_X_plus
  else:
    if popcount_X_minus == 0:
      print(0)
      continue
    else:
#      n = (f_minus - (2**j % popcount_X_minus) + popcount_X_minus) % popcount_X_minus
      n = (f_minus - pow(2, j, popcount_X_minus) + popcount_X_minus) % popcount_X_minus
  
  while n > 0:
    n = f(n)
    ans += 1
  print(ans)
N = int(input())
a = []
for i in range(N):
    a.append(map(int, input())
N = N+1
for i in range(N):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j = j-1
        a[j+1] = v
    print(a) 


### FIXED CODE ###

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


for i in range(N):
    v = b[i]
    j = i-1
    while j>=0 and b[j]>v:
        b[j+1] = b[j]
        j = j-1
        b[j+1] = v
    print(" ".join([str(n) for n in b]))
n=int(input())
l=list(map(int,input().split()))
ll=list(set(l))
n=len(l)
nn=len(ll)
if n==nn:
    print("YES")
else:
    print("NO")
    


### FIXED CODE ###

s,t=map(str,input().split())
a,b=map(int,input().split())
u=str(input())
l=[]
if s==u:
    l=[a-1,b]
elif t==u:
    l=[a,b-1]
else:
    l=[a,b]
print(l[0],l[1])
H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]
black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            black_list.append((i, j))


queue = deque([])
# 黒の周辺4方向のうち、白だったら黒にする
while black_list:
    tmp = []
    for x, y in black_list:
        # 上
        if x-1 > -1 and checked[x-1][y] == -1:
            checked[x-1][y] = checked[x][y] + 1
            tmp.append((x-1, y))
        # 下
        if x+1 < H and checked[x+1][y] == -1:
            checked[x+1][y] = checked[x][y] + 1
            tmp.append((x+1, y))
        # 左
        if y-1 > -1 and checked[x][y-1] == -1:
            checked[x][y-1] = checked[x][y-1] + 1
            tmp.append((x, y-1))

        # 右
        if y+1 < W and checked[x][y+1] == -1:
            checked[x][y+1] = checked[x][y+1] + 1
            tmp.append((x, y+1))

    black_list = tmp


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)
S = input()
K = input()

print(S[1])

if S[0] != "1":
    print(S[0])
else:
    if S[1] != "1":
        print(S[1])
    else:
        if S[2] != "1":
            print(S[2])
        else:
            if S[3] != "1":
                print(S[3])
            else:
                print(1)




### FIXED CODE ###

S = input()
K = input()

for i in range(int(K)):
    if S[i] != "1":
        print(S[i])
        break
else:
    print(1)
import math

N  = int(raw_input())

T, A = map(float, raw_input().split())

for i in range(N - 1):
    t, a = map(float, raw_input().split())

    s1 = math.ceil(T / t)

    s2 = math.ceil(A / a)

    s = max(s1, s2)

    T = s * t
    A = s * a

print "%d" % T + A

### FIXED CODE ###

N  = int(raw_input())

ans = [0, 0]
T, A = [0] * 1001, [0] * 1001

for i in range(N):
    T[i], A[i] = map(int, raw_input().split())

    if i != 0 and T[i - 1] - T[i] > 0 or A[i - 1] - A[i] > 0:

        if (T[i  - 1] / T[i]) > (A[i - 1] / A[i]):
            m  = T[i  - 1] / T[i]
            if T[i - 1] % T[i] != 0:
                m += 1 

        else:
            m = A[i - 1] / A[i]
            if A[i - 1] % A[i] != 0:
                m += 1

        T[i] *= m
        A[i] *= m

    ans = [T[i], A[i]]

print sum(ans)
import sys
import numpypy as np

rl = sys.stdin.readline

n, k = map(int, rl().split())

li = list(map(int, rl().split()))

dp = np.full(n, 1<<60)

dp[0] = 0
dp[1] = abs(li[0] - li[1])

if k < n:    
    for i in range(2, k):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
    for i in range(k, n):
        for j in range(i-k, i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
else:
    for i in range(n):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
        
print(int(dp[-1]))




### FIXED CODE ###

import sys

rl = sys.stdin.readline

n, k = map(int, rl().split())

li = list(map(int, rl().split()))

dp = [1<<60]*n

dp[0] = 0
dp[1] = abs(li[0] - li[1])

if k < n:    
    for i in range(2, k):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
    for i in range(k, n):
        for j in range(i-k, i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
else:
    for i in range(n):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
        
print(int(dp[-1]))
# はやい
def e():
    import numpy as np

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

    dp = np.zeros(W+1, dtype=np.int64)

    for _ in range(N):
        w, v = map(int, input().split())
        print('_, dp[:-w]+v, dp[w:], out=dp[w:] = {}, {}, {}, {}'.format(_,
                                                                         dp[:-w]+v, dp[w:], dp[w:]))
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

    print(dp[-1])


##########
if __name__ == "__main__":
    e()


### FIXED CODE ###

def b():
    def solve(N, W, V, wv):
        dp = [10**10] * (V+1)
        dp[0] = 0

        for i in range(N):
            wi = wv[i][0]
            vi = wv[i][1]

            # 降順でやらないと複数回アイテムをカウントしちゃう（j1 + wi をやった後に j2 + wi をやると、 j1 + wi == j2 のときに2カウントになってしまう）
            for v in range(V - vi, -1, -1):
                if dp[v] == -1:
                    continue
                if dp[v+vi] > dp[v] + wi:
                    dp[v+vi] = dp[v] + wi

        light = [i for i, w in enumerate(dp) if w <= W]
        return light[-1]

    N, W = map(int, input().split())
    wv = []
    V = 0

    for i in range(N):
        w, v = map(int, input().split())
        wv.append([w, v])
        V += v

    print(solve(N, W, V, wv))

if __name__ == "__main__":
    b()
n, x = map(int, input().split())
l = list(map(int, input().split()))

d = 0
count = 0
i = 1
while d <= x:
    d = d + l[i - 1]
    count += 1
    i += 1

print(count)

### FIXED CODE ###

import itertools
import math
n, x = map(int, input().split())
l = list(map(int, input().split()))

d = 0
count = 0
i = 1
while d <= x and i <= n:
    d = d + l[i - 1]
    count += 1
    i += 1
if d <= x:
    count += 1

print(count)