def main():

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

    w=[0]*(N+1)

    v=[0]*(N+1)

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

        a,b=list(map(int,input().split()))

        w[i]=a

        v[i]=b

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

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

        for j in range(W+1):

            if j-w[i]>=0:

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

            else:

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



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



if __name__=="__main__":

    main()
from sys import stdin

import numpy as np

def main():

    #入力

    readline=stdin.readline

    inf=10**12

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

    w=[0]*n

    v=[0]*n

    for i in range(n):

        w[i],v[i]=list(map(int,readline().split()))



    dp=np.full((n+1,max_w+1),-inf,dtype=np.int64)

    dp[0][0]=0

    for i in range(n):

        dp[i+1,:w[i]]=dp[i,:w[i]]

        dp[i+1,w[i]:]=np.maximum(dp[i,w[i]:],dp[i,:max_w-w[i]+1]+v[i])



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



if __name__=="__main__":

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


if __name__ == "__main__":
    main()

from sys import stdin
import numpy as np


def main():
    # 入力
    readline = stdin.readline
    inf = 10**12
    n, max_w = list(map(int, readline().split()))
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, readline().split()))
    dp = np.full((n + 1, max_w + 1), -inf, dtype=np.int64)
    dp[0][0] = 0
    for i in range(n):
        dp[i + 1, : w[i]] = dp[i, : w[i]]
        dp[i + 1, w[i] :] = np.maximum(dp[i, w[i] :], dp[i, : max_w - w[i] + 1] + v[i])
    print((dp[n].max()))


if __name__ == "__main__":
    main()

+from sys import stdin +import numpy as np + + -    N, W = list(map(int, input().split())) -    w = [0] * (N + 1) -    v = [0] * (N + 1) -    for i in range(1, N + 1): -        a, b = list(map(int, input().split())) -        w[i] = a -        v[i] = b -    dp = [[0] * (W + 1) for _ in range(N + 1)] -    for i in range(1, N + 1): -        for j in range(W + 1): -            if j - w[i] >= 0: -                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) -            else: -                dp[i][j] = dp[i - 1][j] -    print((dp[N][W])) +    # 入力 +    readline = stdin.readline +    inf = 10**12 +    n, max_w = list(map(int, readline().split())) +    w = [0] * n +    v = [0] * n +    for i in range(n): +        w[i], v[i] = list(map(int, readline().split())) +    dp = np.full((n + 1, max_w + 1), -inf, dtype=np.int64) +    dp[0][0] = 0 +    for i in range(n): +        dp[i + 1, : w[i]] = dp[i, : w[i]] +        dp[i + 1, w[i] :] = np.maximum(dp[i, w[i] :], dp[i, : max_w - w[i] + 1] + v[i]) +    print((dp[n].max()))