from fractions import gcd

from functools import reduce



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

v = [0]*(N+1)

wtemp = [0]*(N+1)



for i in range(1,N+1):

  v[i],wtemp[i] = list(map(int, input().split()))



gcdw = reduce(gcd,wtemp+[W])

w = list([x//gcdw for x in wtemp])



W2 = W//gcdw

dp = [[0]*(W2+1) for y in range(N+1)]



for i in range(1,N+1):

    dp[i][0:w[i]] = dp[i-1][0:w[i]]

    for j in range(w[i], W2+1):

        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])



print((dp[N][W2]))
N,W = list(map(int, input().split()))

dp = [0]*(W+1)

temp = [0]*(W+1)



for i in range(1,N+1):

    v,w = list(map(int,input().split()))

    for j in range(1, W+1):

        if w <= j and v + temp[j-w] > temp[j]:

            dp[j] = temp[j-w]+v

    temp[0:W+1] = dp[0:W+1]



print((dp[W]))
from fractions import gcd
from functools import reduce

N, W = list(map(int, input().split()))
v = [0] * (N + 1)
wtemp = [0] * (N + 1)
for i in range(1, N + 1):
    v[i], wtemp[i] = list(map(int, input().split()))
gcdw = reduce(gcd, wtemp + [W])
w = list([x // gcdw for x in wtemp])
W2 = W // gcdw
dp = [[0] * (W2 + 1) for y in range(N + 1)]
for i in range(1, N + 1):
    dp[i][0 : w[i]] = dp[i - 1][0 : w[i]]
    for j in range(w[i], W2 + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
print((dp[N][W2]))

N, W = list(map(int, input().split()))
dp = [0] * (W + 1)
temp = [0] * (W + 1)
for i in range(1, N + 1):
    v, w = list(map(int, input().split()))
    for j in range(1, W + 1):
        if w <= j and v + temp[j - w] > temp[j]:
            dp[j] = temp[j - w] + v
    temp[0 : W + 1] = dp[0 : W + 1]
print((dp[W]))

-from fractions import gcd -from functools import reduce - -v = [0] * (N + 1) -wtemp = [0] * (N + 1) +dp = [0] * (W + 1) +temp = [0] * (W + 1) -    v[i], wtemp[i] = list(map(int, input().split())) -gcdw = reduce(gcd, wtemp + [W]) -w = list([x // gcdw for x in wtemp]) -W2 = W // gcdw -dp = [[0] * (W2 + 1) for y in range(N + 1)] -for i in range(1, N + 1): -    dp[i][0 : w[i]] = dp[i - 1][0 : w[i]] -    for j in range(w[i], W2 + 1): -        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) -print((dp[N][W2])) +    v, w = list(map(int, input().split())) +    for j in range(1, W + 1): +        if w <= j and v + temp[j - w] > temp[j]: +            dp[j] = temp[j - w] + v +    temp[0 : W + 1] = dp[0 : W + 1] +print((dp[W]))