import sys



import numba as nb

import numpy as np



input = sys.stdin.readline





@nb.njit("i8(i8,i8,i8[:,:])")

def solve(N, W, wv):

    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)

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

        w, v = wv[i - 1]

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

            if j < w:

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

            else:

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

    return dp[-1, -1]





def main():

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

    wv = np.zeros(shape=(N, 2), dtype=np.int64)

    for i in range(N):

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

        wv[i] = w, v



    ans = solve(N, W, wv)

    print(ans)





if __name__ == "__main__":

    main()

import sys



import numpy as np



input = sys.stdin.readline





def main():

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

    w = [0] * N

    v = [0] * N

    for i in range(N):

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



    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)

    for i, (w_, v_) in enumerate(zip(w, v)):

        dp[i + 1] = dp[i]

        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, :W + 1 - w_] + v_)



    ans = np.max(dp[-1])

    print(ans)





if __name__ == "__main__":

    main()

import sys
import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])")
def solve(N, W, wv):
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i in range(1, N + 1):
        w, v = wv[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp[i, j] = dp[i - 1, j]
            else:
                dp[i, j] = max(dp[i - 1, j - w] + v, dp[i - 1, j])
    return dp[-1, -1]


def main():
    N, W = list(map(int, input().split()))
    wv = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        w, v = list(map(int, input().split()))
        wv[i] = w, v
    ans = solve(N, W, wv)
    print(ans)


if __name__ == "__main__":
    main()

import sys
import numpy as np

input = sys.stdin.readline


def main():
    N, W = list(map(int, input().split()))
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = list(map(int, input().split()))
    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i, (w_, v_) in enumerate(zip(w, v)):
        dp[i + 1] = dp[i]
        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, : W + 1 - w_] + v_)
    ans = np.max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

-import numba as nb -@nb.njit("i8(i8,i8,i8[:,:])") -def solve(N, W, wv): -    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64) -    for i in range(1, N + 1): -        w, v = wv[i - 1] -        for j in range(1, W + 1): -            if j < w: -                dp[i, j] = dp[i - 1, j] -            else: -                dp[i, j] = max(dp[i - 1, j - w] + v, dp[i - 1, j]) -    return dp[-1, -1] - - -    wv = np.zeros(shape=(N, 2), dtype=np.int64) +    w = [0] * N +    v = [0] * N -        w, v = list(map(int, input().split())) -        wv[i] = w, v -    ans = solve(N, W, wv) +        w[i], v[i] = list(map(int, input().split())) +    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64) +    for i, (w_, v_) in enumerate(zip(w, v)): +        dp[i + 1] = dp[i] +        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, : W + 1 - w_] + v_) +    ans = np.max(dp[-1])