Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(100000)

N,A,B,K = map(int, raw_input().split())
mod=998244353

memo={}
memo[(0,0)]=1
memo[(1,A)]=1
memo[(1,B)]=1
memo[(1,A+B)]=1



def func(i,k):
	if (i,k) in memo:
		return memo[(i,k)]
	if i<=0 or k<0: return 0
	#print i-1, k-A,i-1,k-B,i-1, k-(A+B),i-1,k
	result=func(i-1, k-A)%mod+func(i-1, k-B)%mod+func(i-1, k-(A+B))%mod+func(i-1,k)%mod
	result=result%mod

	memo[(i,k)]=result
	return result


print func(N,K)

### FIXED CODE ###

N,A,B,K = map(int, raw_input().split())


mod=998244353
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))


def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

y=0
ans=0
for x in range(N+1):
	if (K-A*x)%B==0:
		if K-A*x<0: break
		y=(K-A*x)/B
		if y>N: continue
		ans+=(ncr(N,x))%mod*(ncr(N,y))%mod

print ans%mod
x, y = map(int, input().split())
print('>' if x>y else '<' if x<y else '=')

### FIXED CODE ###

x, y = input().split()
print('>' if x>y else '<' if x<y else '=')
N=input()
j=input()
print N-j+1 

### FIXED CODE ###

N,j= map(int,raw_input().split())
print N-j+1
N,M = map(int,input().split())
H=list(map(int,input().split()))
ABmap=[[0 for i in range(N)] for i in range(N)]
count=0
for i in range(M):
    A,B=map(lambda x:x-1,map(int,input().split()))
    ABmap[A][B]=H[B]
    ABmap[B][A]=H[A]
    ABmap[A][A]=H[A]
    ABmap[B][B]=H[B]
    #print(ABmap[A])
    
for i in range(M):
    if max(ABmap[i])==H[i]:
        count+=1
print(count)
        
    

### FIXED CODE ###

N,M = map(int,input().split())
H=list(map(int,input().split()))
ABmap=[[] for i in range(N)]
count=0
for i in range(M):
    A,B=map(lambda x:x-1,map(int,input().split()))
    ABmap[A].append(H[B])
    ABmap[B].append(H[A])
        
for i in range(N):
    if len(ABmap[i])==0:
        count+=1
    elif max(ABmap[i])<H[i]:
        count+=1
   # print(ABmap[i])
print(count)
S = list(input())
All = list("abcdefghijklmnopqrstuvwxyz")
res = list(set(S) ^ set(All))
print(res[0])

### FIXED CODE ###

S = list(input())
All = list("abcdefghijklmnopqrstuvwxyz")
res = list(set(S) ^ set(All))
if len(res) > 0:
    print(res[0])
else:
    print("None")
while True:
    h,w=map(int, input().split())
    if h==w== 0:break
    print('#' * w + '\n' +'#' + '.'*(w-2) + '#\n')*(h-2) +'#'* w + '\n')

### FIXED CODE ###

while True:
    h,w=map(int, input().split())
    if h==w== 0:break
    print('#' * w + '\n' + ('#' + '.' * (w-2) + '#\n')*(h-2) +'#'* w + '\n')
A,B =input().split()
print(int(A*(B*100)/100))

### FIXED CODE ###

A,B =map(str,input().split())
B_100=int(B.replace('.',''))
print(int(A)*(B_100)//100)
import sys
import itertools

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())
l=list(range(1,N+1))
m=list(itertools.permutations(range(1,N+1)))
le=len(m)
a=0
ans=0

for j in range(le):
	for i in range(N):
		a+=l[i]%m[j][i]
		
	if a>ans:
		ans=a
	a=0

print(ans)
	

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())

print((N*(N-1))//2)
h, w= map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
B = [list(map(int, input().split())) for _ in range(h)]

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

d = 3200
D = 2*d+1
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][k-C[i+1][j]] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][k-C[i][j+1]] = 1
ans = d
for i in range(d, D):
    if dp[-1][-1][i] != 0:
        ans = min(ans, i-d)
for i in reversed(range(d)):
    if dp[-1][-1][i] != 0:
        ans = min(ans, d-i)
print(ans)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
A = [0]*h
B = [0]*h
for _ in range(h):
  A[_] = list(map(int, input().split()))
  
for _ in range(h):
  B[_] = list(map(int, input().split()))

C = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    C[i][j] = abs(A[i][j]-B[i][j])
    
dp = [[0]*w for _ in range(h)]
D = 80 * (h + w)
L = 2*D + 1
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][D+C[0][0]] = 1
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue
    x = np.zeros(L, np.bool)
    if i != 0:
      x[C[i][j]:] |= dp[i-1][j][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i-1][j][C[i][j]:]
    if j != 0:
      x[C[i][j]:] |= dp[i][j-1][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i][j-1][C[i][j]:]
    dp[i][j] = x
    
temp = np.where(dp[-1][-1]>0)[0]-D
temp = np.abs(temp)
print(np.min(temp))
X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
ans = 0
p.sort()
q.sort()
r.sort()
for i in range(X):
    if p[-1] >= r[-1]:
        ans += p[-1]
        del p[-1:]
        
    elif r[-1] > p[-1] >= q[-1]:
        
        ans += p[-1]
        del p[-1:]
    else:
        ans += r[-1]
        del r[-1:]    
         
for i in range(Y):
    if q[-1] >= r[-1]:
        ans += q[-1]
        del q[-1:]
        
    else:
        ans += r[-1]
        del r[-1:]
                   

print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

ans = p[:X]+q[:Y]+r[:X+Y]
ans.sort(reverse=True)
su = sum(ans[:X+Y])

print(su)
n = int(input())
s = [input() for _ in range(n)]
t = []
for i in range()



from collections import Counter

N = int(input())
S = [input() for _ in range(N)]
cl = [Counter(s) for s in S]

ans = ""
for i in range(26):
  s = chr(ord("a")+i)
  val = min([c[s] for c in cl])
  ans += s*val
print(ans)


### FIXED CODE ###


from collections import Counter

N = int(input())
S = [input() for _ in range(N)]
cl = [Counter(s) for s in S]

ans = ""
for i in range(26):
  s = chr(ord("a")+i)
  val = min([c[s] for c in cl])
  ans += s*val
print(ans)
def SME(Part,L):
    A = {}
    B = []
    ANS = {}
    count = 0
    N = len(Part)
    for i,x in enumerate(Part):
        B.append(x)
        if x in A : A[x] += [i]
        else : A[x] = [i]
    for i in sorted(A) :
        for j in A[i] :
            for k in range(L) :
                if j + k not in ANS :
                    ANS[j+k] = i
                    count += 1
        if count > N * 0.99 : break
    for i in range(L):
        if i not in ANS : ANS[i] = min(B[:i+1])
    for i in range(L,N):
        if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
    return ANS


[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = {}
M = int(N**0.3)
K = N//M
for i in range(M):
    if i == 0:
        ANS.update(SME(Whole[:K], L))
    elif i == M-1:
        ANS.update(SME(Whole[i*K-L+1:], L))
    else:
        ANS.update(SME(Whole[i*K-L+1:K-L+1+K], L))

for i in range(L-1,N-1) :print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input.split()))

a, b = [0], [0]
for i in range(n):
    a.append(a[i] + A[i])
for j in range(m):
    b.append(b[i] + B[i])

ans, j = 0, m
for i in range(n + 1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(n):
    a.append(a[i] + A[i])
for i in range(m):
    b.append(b[i] + B[i])

ans, j = 0, m
for i in range(n + 1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
X,Y = map(int,input().split())

for i in range(X+1):
    if 2*i + 4*(X-i) == Y:
        print('YES')
    if i == X:
        prinnt('NO')

### FIXED CODE ###

import sys
X,Y = map(int,input().split())


for i in range(X+1):
    if 2*i + 4*(X-i) == Y:
        print('Yes')
        sys.exit()
print('No')
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    for a in A[x]:
        if a[0] == pre:
            continue

        cnt = 1
        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N = int(input())

M = [set() for _ in range(N)]

A = [[] for _ in range(N)]
ans = [0] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    A[a - 1].append((b - 1, i))
    A[b - 1].append((a - 1, i))

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

print(max(ans))
for a in ans:
    print(a)
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

### FIXED CODE ###


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

a,b=map(int,input().split())
a,b=max(a,b),min(a,b)
print(a*b//fx(a,b))
n,m,x=map(int,input().split())
for i in range(m):
    a=map(int,input().split())
s=sum(int(i)<x for i in a)
print(min(s,m-s))
    

### FIXED CODE ###

n,m,x=map(int,input().split())
s=sum(int(i)<x for i in input().split())
print(min(s,m-s))
n,m = map(int,input().split())

a = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
    a_tmp = list(map(int,input().split()))
	for j in range(m):
	    a[i][j] = a_tmp[j]

b=[]
for i in range(m):
    b.append(int(input()))
    
for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j]*b[j]
    print(c)

### FIXED CODE ###

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

a = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
    a_tmp = list(map(int,input().split()))
    for j in range(m):
        a[i][j] = a_tmp[j]

b=[]
for i in range(m):
    b.append(int(input()))
    
for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j]*b[j]
    print(c)
N, K = map(int, input().split())
H = sorted(list(map(int, input().split())))
print(sum([0] + H[:-K]) if K > 0 else sum(H))


### FIXED CODE ###

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

ans = 0

while H>0:
	ans += 1
	H -= A

print(ans)
a = list(map(input().split()))

if a[0] =< a[1] =< a[2]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###


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

if a[0] < a[1] < a[2]:
    print('Yes')
else:
    print('No')
s=input() #数値入力 「N」だけの入力のとき
t=input()  #数値入力 「N」だけの入力のとき
sa=list(s)
ta=list(t)
ans2
x=0
y=0
ans= [[] for i in range(26)]
for i in range(len(s)):
    ans[ord(sa[i])-96-1].append(i)
print(ans)
for i in range(len(t)):
    if len(ans[ord(ta[i])-97])==0:
        ans2=-1
        break;
    else:
        x_old=x
        for j in ans[ord(ta[i])-97]:
            if j>x:
                x=j
        if x_old==x:
            x=0
            y+=1
            for j in ans[ord(ta[i])-97]:
                if j>x:
                    x=j
print(y*len(s)+x+1)



### FIXED CODE ###

import bisect

s,t=input(),input()
ls=len(s)
lt=len(t)
A=[[] for i in range(26+1)]
L=[0 for i in range(26+1)]

for i in range(ls):
  A[ord(s[i])-96].append(i+1)
  L[ord(s[i])-96]+=1
#print(A)

tmp=0
ans=0
for i in range(lt):
  ii=ord(t[i])-96

  if L[ii]==0:
    print(-1)
    exit()
  else:
    iii=bisect.bisect(A[ii],tmp)
    #print(t[i],A[ii],tmp,iii,ans)
    if iii==L[ii]:
      ans+=ls-tmp+A[ii][0]
      tmp=A[ii][0]
    else:
      ans+=A[ii][iii]-tmp
      tmp=A[ii][iii]
print(ans)
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

b = [a[x] for x in range(n - p)]

total = sum(b)

vote=(v - p) * m

ans = p

for n, i in enumerate(b):
    if (total - i + vote) // (len(b) - 1) <= i + m:
        ans += len(b) - n - 1
        break

print(ans)

### FIXED CODE ###

from math import ceil
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)[p - 1:]
l = 0
r = n - p

while l != r:
    k = ceil((l + r) / 2)
    b = a[k] + m
    if b < a[0] or (v - (n - k)) * m > (k * b - sum(a[:k])):
        r = k - 1
    else:
        l = k
print(p+l)
n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  if b==0:
    c=c+a
  elif a>0:
    B.append[(b,-1*a)]
  else:
    A.append([-1*b,a])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c+B[i][0]<0:
    f=1
  c=c-A[i][1]
for i in range(len(A)):
  if c-A[i][0]<0:
    f=1
  c=c+A[i][1]
if c!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  b=b*-1
  if b==0:
    c=c+a
  elif a>=0:
    B.append([b,-1*a])
  else:
    A.append([b+a,a])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c-B[i][0]<0:
    f=1
  c=c-B[i][1]
d=0
for i in range(len(A)):
  if d-A[i][0]<0:
    f=1
  d=d-A[i][1]
if c!=d:
  f=1
if f==0:
  print("Yes")
else:
  print("No")
import numpy as np


def score(cache, sss, a, ab, d):
    mat = cache[ab]
    if mat is None:
        mat = cache[ab] = np.cumsum(np.resize(sss, ((n - 1) // ab + 1, ab)).T, axis=1)
    mat_a = mat[a % ab]
    return mat[0][d] + mat_a[-1] - mat_a[-d - 2]


n = int(input())
sss = list(map(int, input().split()))
sss.extend([0] * n)
sss = np.array(sss, dtype=np.int64)

ans = 0
cache = [None] * n
for ab in range(1, int((n - 2) ** 0.5) + 1):
    for remain in range(ab, n - 3, ab):
        a = n - remain - 1
        d = remain // ab
        if remain < a:
            ans = max(ans, score(cache, sss, a, ab, d))
            if ab != d:
                ans = max(ans, score(cache, sss, a, d, ab))
        else:
            if a % ab > 0:
                ans = max(ans, score(cache, sss, a, ab, d))
            if a > d and ab != d and a % d > 0:
                ans = max(ans, score(cache, sss, a, d, ab))
print(ans)


### FIXED CODE ###

n = int(input())
sss = list(map(int, input().split()))

ans = 0
for c in range(1, n // 2):
    a = n - 1 - c
    k = c
    tmp = 0
    while a > c and a != k and a + c != k:
        tmp += sss[a] + sss[k]
        ans = max(ans, tmp)
        a -= c
        k += c
print(ans)
import copy
n = int(input())
a = list(map(int,input().split()))
a2 = copy.copy(a)
c = 0
d = len(a)
for i in range(len(a)):
    if i+1 == len(a):
        ans = a[i-1] ^ a[0]
        if (ans in a):
            try:
                a2.remove(ans)
            except e:
                break
        else:
            break
    else:
        ans = a[i-1] ^ a[i+1]
        if (ans in a):
            try:
                a2.remove(ans)
            except e:
                break
        else:
            break
    c += 1

if c == d:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

n=int(input())
al=list(map(int,input().split()))
t=0
for a in al:
    t^=a
print('Yes' if t==0 else 'No')
input()
nums = input().split()
result = 18 # 制約 Ai < 10^9より
for num in nums:
  num = int(num)
  div_times = 0
  while (num & 1) == 0:
    num = num >> 1
    div_times += 1
  if div_times < result:
    result = div_times
print(result)

### FIXED CODE ###

marbleNum = input().count("1")
print(marbleNum)
n = int(raw_input())
for i in range(n):
    s = int(raw_input())
    print "Case %d:"%(i+1)
    for j in range(10):
        s =int(str(s**2)[-6:-2])
        print s

### FIXED CODE ###

n = int(raw_input())
for i in range(n):
    s = int(raw_input())
    print "Case %d:"%(i+1)
    for j in range(10):
        if len(str(s**2)) < 3:
            s = 0
        else:
            s =int(str(s**2)[-6:-2])
        print s
while 1:
  x,y = map(int, input().split)
  if x == 0 and y == 0:
    break
  min = min(x,y)
  max = max(x,y)
  print x + y

### FIXED CODE ###

while 1:
  x, y = map(int, raw_input().split())
  if x == 0 and y == 0:
    break
  elif x > y:
    print "%d %d" % (y,x)
  else:
    print "%d %d" % (x,y)
mod=10**9+7
ors=[n]
rev=[1]

def ie(n,r,mod):
  if r==1:
    return n
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return n*((ie(n,(r-1)//2,mod))**2)%mod
  
for i in range(1,b):
  ors.append(ors[-1]*(n-i)%mod)
  rev.append(rev[-1]*(i+1)%mod)  
N=ie(2,n,mod)
A=ors[a-1]*ie(rev[a-1],mod-2,mod)
B=ors[b-1]*ie(rev[b-1],mod-2,mod)
print((N-A-B-1)%mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
ors=[n]
rev=[1]

def ie(n,r,mod):
  if r==1:
    return n
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return n*((ie(n,(r-1)//2,mod))**2)%mod
    
  
for i in range(1,b):
  ors.append(ors[-1]*(n-i)%mod)
  rev.append(rev[-1]*(i+1)%mod)  
N=ie(2,n,mod)
A=ors[a-1]*ie(rev[a-1],mod-2,mod)
B=ors[b-1]*ie(rev[b-1],mod-2,mod)
print((N-A-B-1)%mod)
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x-1, y))
xy = np.array(xy)
x, y = xy[:, :].T
x = x.T 
y = y.T

def main():
    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        for i in range(n):
            if not comb >> i & 1:
                continue
            if np.any(comb >> x[i] & 1 ^ y[i]):
                break
            cnt += 1
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
# import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x-1, y))

# xy = np.array(xy)
# x, y = xy[:, :].T
# x = x.T 
# y = y.T

def main():
    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        ok = True
        for i in range(n):
            if not comb >> i & 1:
                continue
            for x, y in xy[i]:
                if comb >> x & 1 ^ y:
                    ok = False
                    break
            if ok:
                cnt += 1
            else:
                break
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)
N, W = map(int, input().split())
W = []
V = []

for _ in range(N):
  w, v = map(int, input().split())
  W.append(w)
  V.append(v)

Ans = [[0 for _ in range(W+1)] for _ in range(N)]

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    if w - W[i] >= 0:
      Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w], Ans[i][w])
    else:
      Ans[i][w] = max(Ans[i-1][w], Ans[i][w])

print(max(Ans[N-1]))


### FIXED CODE ###

import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:
      # pdb.set_trace()
      # print(num, load, ws[num], vs[num])
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:
      Value[num][load] = max(Value[num][load], Value[num-1][load])

print(Value[N-1][W])
import numpy　as np
N = int(input())
a = int(list(input()))

count = [0] * N
for i in range(N):
  while(a[i] % 2== 1):
    a[i] = a[i] // 2
    count[i] += 1
print(np.min(count))

### FIXED CODE ###

import numpy as np
N = int(input())
a = list(map(int, input().split()))

count = [0] * N
for i in range(N):
  while(a[i] % 2== 0):
    a[i] = a[i] // 2
    count[i] += 1
print(np.min(count))
n = int(input())
p=map(int, input().split())
q=map(int, input().split())

import math

a=0
for i in range(n-1):
  a +=(p[i]-1) * math.factorial(n-1-i)
  
  
b=0
for i in range(n-1):
  b +=(q[i]-1) * math.factorial(n-1-i)
  
print(abs(a-b))




### FIXED CODE ###

from itertools import permutations
n=int(input())
v=list(permutations(range(1,n+1),n))
print(abs(v.index(tuple(map(int,input().split())))-v.index(tuple(map(int,input().split())))))
import math

def yes():
    print("Yes")
def no():
    print("No")

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

if a-b > k or b-c > k or c-d > k or d-e > k:
    no()
else:
    yes()


### FIXED CODE ###

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

if l[4]-l[0]>l[5]:
    print(":(")
else:
    print("Yay!")
def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = []
    for b in xy[a]:
      num = cal(b)
      dp[b] = num
      ans.append(num+1)
    return max(ans)
  return 0

if __name__ == "__main__":
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()

### FIXED CODE ###

import sys

def main():
  out = 0
  for i in range(1, n+1):
    if dp[i]:
        di = dp[i]
        if di > out:
            out = di
    else:
        di = cal(i)
        if di > out:
            out = di
  print(out)

def cal(a):
  if xy[a]:
    ans = 0
    for b in xy[a]:
      if dp[b]:
        num = dp[b]
      else:
        num = cal(b)
        dp[b] = num
      if num+1 > ans:
        ans = num+1
    return ans
  return 0

if __name__ == "__main__":
  sys.setrecursionlimit(100000)
  n, m = map(int, input().split())
  xy = [set() for _ in range(n+1)]
  dp = [None]*(n+1)
  for _ in range(m):
    x, y = map(int, input().split())
    xy[x].add(y)
  main()