

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





#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S



weight=[0]*110

value=[0]*110



S = [[0 for j in range(3)] for i in range(100010)]

DP= [[0 for j in range(100100)] for i in range(110)]



for i in range(N):

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

    weight[i]=A

    value[i]=B

    

for i in range(N):

    for w in range(W+1):

        if w>=weight[i]:

            DP[i+1][w]=max(DP[i][w-weight[i]]+value[i],DP[i][w])

        else:

            DP[i+1][w]=DP[i][w]



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

S = [[0 for j in range(2)] for i in range(N+1)]



DP= [[0 for j in range(100010)] for i in range(110)]

def chmax(a,b):

    if a>b:

        return a

    else:

        return b





for i in range(N):

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

    S[i][0]=w

    S[i][1]=v





for i in range(N):

    for j in range(W+1):

        if j-S[i][0]>=0:

            

            DP[i+1][j]=chmax(DP[i][j],DP[i][j-S[i][0]]+S[i][1])

        

        else:

            DP[i+1][j]=DP[i][j]

        

print((DP[N][W]))

N, W = list(map(int, input().split()))
# S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S
weight = [0] * 110
value = [0] * 110
S = [[0 for j in range(3)] for i in range(100010)]
DP = [[0 for j in range(100100)] for i in range(110)]
for i in range(N):
    A, B = list(map(int, input().split()))
    weight[i] = A
    value[i] = B
for i in range(N):
    for w in range(W + 1):
        if w >= weight[i]:
            DP[i + 1][w] = max(DP[i][w - weight[i]] + value[i], DP[i][w])
        else:
            DP[i + 1][w] = DP[i][w]
print((DP[N][W]))

N, W = list(map(int, input().split()))
S = [[0 for j in range(2)] for i in range(N + 1)]
DP = [[0 for j in range(100010)] for i in range(110)]


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


for i in range(N):
    w, v = list(map(int, input().split()))
    S[i][0] = w
    S[i][1] = v
for i in range(N):
    for j in range(W + 1):
        if j - S[i][0] >= 0:
            DP[i + 1][j] = chmax(DP[i][j], DP[i][j - S[i][0]] + S[i][1])
        else:
            DP[i + 1][j] = DP[i][j]
print((DP[N][W]))

-# S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合S -weight = [0] * 110 -value = [0] * 110 -S = [[0 for j in range(3)] for i in range(100010)] -DP = [[0 for j in range(100100)] for i in range(110)] +S = [[0 for j in range(2)] for i in range(N + 1)] +DP = [[0 for j in range(100010)] for i in range(110)] + + +def chmax(a, b): +    if a > b: +        return a +    else: +        return b + + -    A, B = list(map(int, input().split())) -    weight[i] = A -    value[i] = B +    w, v = list(map(int, input().split())) +    S[i][0] = w +    S[i][1] = v -    for w in range(W + 1): -        if w >= weight[i]: -            DP[i + 1][w] = max(DP[i][w - weight[i]] + value[i], DP[i][w]) +    for j in range(W + 1): +        if j - S[i][0] >= 0: +            DP[i + 1][j] = chmax(DP[i][j], DP[i][j - S[i][0]] + S[i][1]) -            DP[i + 1][w] = DP[i][w] +            DP[i + 1][j] = DP[i][j]