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

e = tuple(list(map(int, input().split())) for _ in range(n))

wt, vt = list(zip(*e))



dp = tuple([0] * (w + 1) for _ in range(n + 1))



for i in range(n):

    dp[i + 1][:wt[i]] = dp[i][:wt[i]]

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

        dp[i + 1][j] = max(dp[i][j], dp[i][j - wt[i]] + vt[i])

print((dp[n][w]))

def main():

    import sys

    readline = sys.stdin.readline



    n, w = list(map(int, readline().split()))



    dp = [[0] * (w + 1) for _ in range(n + 1)]



    for i in range(1, n + 1):  # i個目の品物を選ぶかどうか決めた後の価値の総和の最大値,1-indexed

        wi, vi = list(map(int, readline().split()))

        for j in range(wi):

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

        for j in range(wi, w + 1):

            dp[i][j] = max(

                dp[i - 1][j],  # i-1にすることにdebugで気づいた

                dp[i - 1][j - wi] + vi

            )



    print((max(dp[n])))





if __name__ == '__main__':

    main()

n, w = list(map(int, input().split()))
e = tuple(list(map(int, input().split())) for _ in range(n))
wt, vt = list(zip(*e))
dp = tuple([0] * (w + 1) for _ in range(n + 1))
for i in range(n):
    dp[i + 1][: wt[i]] = dp[i][: wt[i]]
    for j in range(wt[i], w + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - wt[i]] + vt[i])
print((dp[n][w]))

def main():
    import sys

    readline = sys.stdin.readline
    n, w = list(map(int, readline().split()))
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):  # i個目の品物を選ぶかどうか決めた後の価値の総和の最大値,1-indexed
        wi, vi = list(map(int, readline().split()))
        for j in range(wi):
            dp[i][j] = dp[i - 1][j]
        for j in range(wi, w + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)  # i-1にすることにdebugで気づいた
    print((max(dp[n])))


if __name__ == "__main__":
    main()

-n, w = list(map(int, input().split())) -e = tuple(list(map(int, input().split())) for _ in range(n)) -wt, vt = list(zip(*e)) -dp = tuple([0] * (w + 1) for _ in range(n + 1)) -for i in range(n): -    dp[i + 1][: wt[i]] = dp[i][: wt[i]] -    for j in range(wt[i], w + 1): -        dp[i + 1][j] = max(dp[i][j], dp[i][j - wt[i]] + vt[i]) -print((dp[n][w])) +def main(): +    import sys + +    readline = sys.stdin.readline +    n, w = list(map(int, readline().split())) +    dp = [[0] * (w + 1) for _ in range(n + 1)] +    for i in range(1, n + 1):  # i個目の品物を選ぶかどうか決めた後の価値の総和の最大値,1-indexed +        wi, vi = list(map(int, readline().split())) +        for j in range(wi): +            dp[i][j] = dp[i - 1][j] +        for j in range(wi, w + 1): +            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)  # i-1にすることにdebugで気づいた +    print((max(dp[n]))) + + +if __name__ == "__main__": +    main()