import sys

sys.setrecursionlimit(1000000) # 再帰上限を増やす



def main():

    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！

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

    item_list = []

    for _ in range(N):

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

        item_list.append((w, v))



    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値

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



    for i, item in enumerate(item_list):

        for w in range(W+1):

            # もし品物iが入れられる

            if w + item[0] <= W:

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

            # 入れないパターン

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

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



if __name__ == '__main__':

    main()
import sys

sys.setrecursionlimit(1000000) # 再帰上限を増やす



def main():

    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！

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

    item_list = []

    for _ in range(N):

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

        item_list.append((w, v))



    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値

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



    for i, item in enumerate(item_list, 1):

        for w in range(W+1):

            # もし品物iが入れられる

            if w + item[0] <= W:

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

            # 入れないパターン

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

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



if __name__ == '__main__':

    main()
import sys

sys.setrecursionlimit(1000000)  # 再帰上限を増やす


def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = list(map(int, input().rstrip().split()))
    item_list = []
    for _ in range(N):
        w, v = list(map(int, input().rstrip().split()))
        item_list.append((w, v))
    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N)]
    for i, item in enumerate(item_list):
        for w in range(W + 1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w + item[0]] = max(dp[i][w + item[0]], dp[i - 1][w] + item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i - 1][w])
    print((dp[N - 1][W]))


if __name__ == "__main__":
    main()

import sys

sys.setrecursionlimit(1000000)  # 再帰上限を増やす


def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = list(map(int, input().rstrip().split()))
    item_list = []
    for _ in range(N):
        w, v = list(map(int, input().rstrip().split()))
        item_list.append((w, v))
    # dp[i][w] = i番目まで見て重さwで持ち帰れる最大の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, item in enumerate(item_list, 1):
        for w in range(W + 1):
            # もし品物iが入れられる
            if w + item[0] <= W:
                dp[i][w + item[0]] = max(dp[i][w + item[0]], dp[i - 1][w] + item[1])
            # 入れないパターン
            dp[i][w] = max(dp[i][w], dp[i - 1][w])
    print((dp[N][W]))


if __name__ == "__main__":
    main()

-    dp = [[0] * (W + 1) for _ in range(N)] -    for i, item in enumerate(item_list): +    dp = [[0] * (W + 1) for _ in range(N + 1)] +    for i, item in enumerate(item_list, 1): -    print((dp[N - 1][W])) +    print((dp[N][W]))