I = [int(_) for _ in open(0).read().split()]

N, T = I[:2]

A, B = I[2::2], I[3::2]

dp = [-1] * 6001

dp[0] = 0

for a, b in sorted(zip(A, B)):

    dp_new = dp[:]

    for k in range(T):

        if dp[k] == -1:

            continue

        dp_new[k + a] = max(dp[k + a], dp[k] + b)

    dp = dp_new

print((max(dp)))

I = [int(_) for _ in open(0).read().split()]

N, T = I[:2]

A, B = I[2::2], I[3::2]

dp = [-1] * 6001

dp[0] = 0

for a, b in sorted(zip(A, B)):

    for k in range(T - 1, -1, -1):

        if dp[k] == -1:

            continue

        dp[k + a] = max(dp[k + a], dp[k] + b)

print((max(dp)))

I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    dp_new = dp[:]
    for k in range(T):
        if dp[k] == -1:
            continue
        dp_new[k + a] = max(dp[k + a], dp[k] + b)
    dp = dp_new
print((max(dp)))

I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    for k in range(T - 1, -1, -1):
        if dp[k] == -1:
            continue
        dp[k + a] = max(dp[k + a], dp[k] + b)
print((max(dp)))

-    dp_new = dp[:] -    for k in range(T): +    for k in range(T - 1, -1, -1): -        dp_new[k + a] = max(dp[k + a], dp[k] + b) -    dp = dp_new +        dp[k + a] = max(dp[k + a], dp[k] + b)