import numpy as np

def resolve():

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

    goods = np.array([list(map(int, input().split())) for _ in range(n)])

    dp = np.zeros([n + 1, w + 1], dtype=int)



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

        tmp = np.zeros(w + 1, dtype=int)

        tmp[goods[i - 1][0]:] = dp[i - 1][:-goods[i - 1][0]] + goods[i - 1][1]

        dp[i] = np.maximum(dp[i - 1], tmp)



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

    

resolve()
import numpy as np

def resolve():

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

    goods = np.array([list(map(int, input().split())) for _ in range(n)])

    

    # dpテーブルを1次元にして破壊的に更新していくパターン

    dp = np.zeros([w + 1], dtype=int)



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

        tmp = np.zeros(w + 1, dtype=int)

        tmp[goods[i - 1][0]:] = dp[:-goods[i - 1][0]] + goods[i - 1][1]

        dp = np.maximum(dp, tmp)



    print((dp[w]))

    

resolve()
import numpy as np


def resolve():
    n, w = list(map(int, input().split()))
    goods = np.array([list(map(int, input().split())) for _ in range(n)])
    dp = np.zeros([n + 1, w + 1], dtype=int)
    for i in range(1, n + 1):
        tmp = np.zeros(w + 1, dtype=int)
        tmp[goods[i - 1][0] :] = dp[i - 1][: -goods[i - 1][0]] + goods[i - 1][1]
        dp[i] = np.maximum(dp[i - 1], tmp)
    print((dp[n][w]))


resolve()

import numpy as np


def resolve():
    n, w = list(map(int, input().split()))
    goods = np.array([list(map(int, input().split())) for _ in range(n)])
    # dpテーブルを1次元にして破壊的に更新していくパターン
    dp = np.zeros([w + 1], dtype=int)
    for i in range(1, n + 1):
        tmp = np.zeros(w + 1, dtype=int)
        tmp[goods[i - 1][0] :] = dp[: -goods[i - 1][0]] + goods[i - 1][1]
        dp = np.maximum(dp, tmp)
    print((dp[w]))


resolve()

-    dp = np.zeros([n + 1, w + 1], dtype=int) +    # dpテーブルを1次元にして破壊的に更新していくパターン +    dp = np.zeros([w + 1], dtype=int) -        tmp[goods[i - 1][0] :] = dp[i - 1][: -goods[i - 1][0]] + goods[i - 1][1] -        dp[i] = np.maximum(dp[i - 1], tmp) -    print((dp[n][w])) +        tmp[goods[i - 1][0] :] = dp[: -goods[i - 1][0]] + goods[i - 1][1] +        dp = np.maximum(dp, tmp) +    print((dp[w]))