def solve():

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

    w = []

    v = []

    for i in range(N):

        tmpw, tmpv = list(map(int, input().split()))

        w.append(tmpw)

        v.append(tmpv)



    dp = [[0 for i in range(W+1)] for j in range(N+1)]



    for i in range(N+1):

        dp[i][0] = 0

    

    for j in range(W+1):

        dp[0][j] = 0



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

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

            if sum_w - w[i-1] >= 0:

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

            

            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

        

    print((dp[N][W]))



if __name__ == '__main__':

    solve()
def solve():

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

    weight = []

    value = []

    for i in range(N):

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

        weight.append(w)

        value.append(v)

    

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



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

        for w in range(W+1):

            if w - weight[i-1] < 0:

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

            else:

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

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

    

    print((max(dp[-1])))



if __name__ == '__main__':

    solve()
def solve():
    N, W = list(map(int, input().split()))
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = list(map(int, input().split()))
        w.append(tmpw)
        v.append(tmpv)
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 0
    for j in range(W + 1):
        dp[0][j] = 0
    for i in range(1, N + 1):
        for sum_w in range(1, W + 1):
            if sum_w - w[i - 1] >= 0:
                dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - w[i - 1]] + v[i - 1])
            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])
    print((dp[N][W]))


if __name__ == "__main__":
    solve()

def solve():
    N, W = list(map(int, input().split()))
    weight = []
    value = []
    for i in range(N):
        w, v = list(map(int, input().split()))
        weight.append(w)
        value.append(v)
    dp = [[0] * (W + 1) for i in range(N + 1)]
    for i in range(1, N + 1):
        for w in range(W + 1):
            if w - weight[i - 1] < 0:
                dp[i][w] = max(dp[i][w], dp[i - 1][w])
            else:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1])
                dp[i][w] = max(dp[i][w], dp[i - 1][w])
    print((max(dp[-1])))


if __name__ == "__main__":
    solve()

-    w = [] -    v = [] +    weight = [] +    value = [] -        tmpw, tmpv = list(map(int, input().split())) -        w.append(tmpw) -        v.append(tmpv) -    dp = [[0 for i in range(W + 1)] for j in range(N + 1)] -    for i in range(N + 1): -        dp[i][0] = 0 -    for j in range(W + 1): -        dp[0][j] = 0 +        w, v = list(map(int, input().split())) +        weight.append(w) +        value.append(v) +    dp = [[0] * (W + 1) for i in range(N + 1)] -        for sum_w in range(1, W + 1): -            if sum_w - w[i - 1] >= 0: -                dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - w[i - 1]] + v[i - 1]) -            dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w]) -    print((dp[N][W])) +        for w in range(W + 1): +            if w - weight[i - 1] < 0: +                dp[i][w] = max(dp[i][w], dp[i - 1][w]) +            else: +                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]) +                dp[i][w] = max(dp[i][w], dp[i - 1][w]) +    print((max(dp[-1])))