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

wt = [];    val = []

for i in range(n):

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

    wt.append(a);   val.append(b)

dp = [[0 for i in range(tw+1)] for j in range(n+1)]

for i in range(n):

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

        if j < wt[i]:

            dp[i+1][j] = dp[i][j]

        else:

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

print((dp[n][tw]))

def ks(n, W, arr):

    dp = [[0 for i in range(W+1)] for j in range(n+1)]

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

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

            if arr[i-1][0] > j:

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

            else:

                dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i-1][0]]+arr[i-1][1])

    return dp[n][W]



if __name__ == "__main__":

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

    arr = []

    for i in range(n):

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

        arr.append([w,v])

    arr.sort(key = lambda x:x[0])

    ans = ks(n,W,arr)

    print(ans)

n, tw = list(map(int, input().split()))
wt = []
val = []
for i in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    val.append(b)
dp = [[0 for i in range(tw + 1)] for j in range(n + 1)]
for i in range(n):
    for j in range(1, tw + 1):
        if j < wt[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], val[i] + dp[i][j - wt[i]])
print((dp[n][tw]))

def ks(n, W, arr):
    dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if arr[i - 1][0] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(
                    dp[i - 1][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1]
                )
    return dp[n][W]


if __name__ == "__main__":
    n, W = list(map(int, input().split()))
    arr = []
    for i in range(n):
        w, v = list(map(int, input().split()))
        arr.append([w, v])
    arr.sort(key=lambda x: x[0])
    ans = ks(n, W, arr)
    print(ans)

-n, tw = list(map(int, input().split())) -wt = [] -val = [] -for i in range(n): -    a, b = list(map(int, input().split())) -    wt.append(a) -    val.append(b) -dp = [[0 for i in range(tw + 1)] for j in range(n + 1)] -for i in range(n): -    for j in range(1, tw + 1): -        if j < wt[i]: -            dp[i + 1][j] = dp[i][j] -        else: -            dp[i + 1][j] = max(dp[i][j], val[i] + dp[i][j - wt[i]]) -print((dp[n][tw])) +def ks(n, W, arr): +    dp = [[0 for i in range(W + 1)] for j in range(n + 1)] +    for i in range(1, n + 1): +        for j in range(1, W + 1): +            if arr[i - 1][0] > j: +                dp[i][j] = dp[i - 1][j] +            else: +                dp[i][j] = max( +                    dp[i - 1][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1] +                ) +    return dp[n][W] + + +if __name__ == "__main__": +    n, W = list(map(int, input().split())) +    arr = [] +    for i in range(n): +        w, v = list(map(int, input().split())) +        arr.append([w, v]) +    arr.sort(key=lambda x: x[0]) +    ans = ks(n, W, arr) +    print(ans)