import sys





def input():

    return sys.stdin.readline().rstrip()





def main():

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

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

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

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

        for j in range(W + 1):

            if j >= w:

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

            else:

                dp[j][i] = dp[j][i - 1]



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





if __name__ == "__main__":

    main()

import sys

import math

import itertools





# \n





def input():

    return sys.stdin.readline().rstrip()





def main():

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

    W = []

    V = []

    for i in range(N):

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

        W.append(w)

        V.append(v)



    dp = [[0] * (WW+1) for _ in range(N)]



    for i in range(N):

        w = W[i]

        v = V[i]

        for j in range(WW+1):

            if w<=j:

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

            else:

                dp[i][j] =dp[i-1][j]



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





if __name__ == "__main__":

    main()

import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = list(map(int, input().split()))
    dp = [[0] * (N + 1) for _ in range(W + 1)]
    for i in range(1, N + 1):
        w, v = list(map(int, input().split()))
        for j in range(W + 1):
            if j >= w:
                dp[j][i] = max(dp[j][i - 1], dp[j - w][i - 1] + v)
            else:
                dp[j][i] = dp[j][i - 1]
    print((dp[W][N]))


if __name__ == "__main__":
    main()

import sys
import math
import itertools

# \n
def input():
    return sys.stdin.readline().rstrip()


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


if __name__ == "__main__":
    main()

+import math +import itertools - +# \n -    N, W = list(map(int, input().split())) -    dp = [[0] * (N + 1) for _ in range(W + 1)] -    for i in range(1, N + 1): +    N, WW = list(map(int, input().split())) +    W = [] +    V = [] +    for i in range(N): -        for j in range(W + 1): -            if j >= w: -                dp[j][i] = max(dp[j][i - 1], dp[j - w][i - 1] + v) +        W.append(w) +        V.append(v) +    dp = [[0] * (WW + 1) for _ in range(N)] +    for i in range(N): +        w = W[i] +        v = V[i] +        for j in range(WW + 1): +            if w <= j: +                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) -                dp[j][i] = dp[j][i - 1] -    print((dp[W][N])) +                dp[i][j] = dp[i - 1][j] +    print((max(dp[N - 1])))