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

AB = [list(map(int,input().split())) for _ in range(N)]

AB.sort(key=lambda x:x[1])



dp1 = [[0]*T for i in range(N+1)]

for n in range(N):

    for w in range(T):

        if w-AB[n][0]>=0:

            dp1[n+1][w] = max(dp1[n][w],dp1[n][w-AB[n][0]]+AB[n][1])

        else:

            dp1[n+1][w] = dp1[n][w]



for n in range(N):

    for w in range(T-1):

        dp1[n][w+1] = max(dp1[n][w+1],dp1[n][w])



dp2 = [[0]*T for i in range(N+1)]

for n in range(N):

    for w in range(T):

        if w-AB[-n-1][0]>=0:

            dp2[n+1][w] = max(dp2[n][w],dp2[n][w-AB[-n-1][0]]+AB[-n-1][1])

        else:

            dp2[n+1][w] = dp2[n][w]



for n in range(N):

    for w in range(T-1):

        dp2[n][w+1] = max(dp2[n][w+1],dp2[n][w])



ans = 0

for n in range(N):

    for w in range(T):

        ans = max(AB[n][1]+dp1[n][w]+dp2[N-n-1][T-1-w],ans)



print(ans)
N,T = list(map(int,input().split()))

AB = [list(map(int,input().split())) for _ in range(N)]

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



dp = [[0]*T for i in range(N+1)]

ans = 0

for n in range(N):

    for w in range(T):

        ans = max(ans,dp[n][w]+AB[n][1])

        if w-AB[n][0]>=0:

            dp[n+1][w] = max(dp[n][w],dp[n][w-AB[n][0]]+AB[n][1])

        else:

            dp[n+1][w] = dp[n][w]



print(ans)
N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])
dp1 = [[0] * T for i in range(N + 1)]
for n in range(N):
    for w in range(T):
        if w - AB[n][0] >= 0:
            dp1[n + 1][w] = max(dp1[n][w], dp1[n][w - AB[n][0]] + AB[n][1])
        else:
            dp1[n + 1][w] = dp1[n][w]
for n in range(N):
    for w in range(T - 1):
        dp1[n][w + 1] = max(dp1[n][w + 1], dp1[n][w])
dp2 = [[0] * T for i in range(N + 1)]
for n in range(N):
    for w in range(T):
        if w - AB[-n - 1][0] >= 0:
            dp2[n + 1][w] = max(dp2[n][w], dp2[n][w - AB[-n - 1][0]] + AB[-n - 1][1])
        else:
            dp2[n + 1][w] = dp2[n][w]
for n in range(N):
    for w in range(T - 1):
        dp2[n][w + 1] = max(dp2[n][w + 1], dp2[n][w])
ans = 0
for n in range(N):
    for w in range(T):
        ans = max(AB[n][1] + dp1[n][w] + dp2[N - n - 1][T - 1 - w], ans)
print(ans)

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
dp = [[0] * T for i in range(N + 1)]
ans = 0
for n in range(N):
    for w in range(T):
        ans = max(ans, dp[n][w] + AB[n][1])
        if w - AB[n][0] >= 0:
            dp[n + 1][w] = max(dp[n][w], dp[n][w - AB[n][0]] + AB[n][1])
        else:
            dp[n + 1][w] = dp[n][w]
print(ans)

-AB.sort(key=lambda x: x[1]) -dp1 = [[0] * T for i in range(N + 1)] -for n in range(N): -    for w in range(T): -        if w - AB[n][0] >= 0: -            dp1[n + 1][w] = max(dp1[n][w], dp1[n][w - AB[n][0]] + AB[n][1]) -        else: -            dp1[n + 1][w] = dp1[n][w] -for n in range(N): -    for w in range(T - 1): -        dp1[n][w + 1] = max(dp1[n][w + 1], dp1[n][w]) -dp2 = [[0] * T for i in range(N + 1)] -for n in range(N): -    for w in range(T): -        if w - AB[-n - 1][0] >= 0: -            dp2[n + 1][w] = max(dp2[n][w], dp2[n][w - AB[-n - 1][0]] + AB[-n - 1][1]) -        else: -            dp2[n + 1][w] = dp2[n][w] -for n in range(N): -    for w in range(T - 1): -        dp2[n][w + 1] = max(dp2[n][w + 1], dp2[n][w]) +AB.sort(key=lambda x: x[0]) +dp = [[0] * T for i in range(N + 1)] -        ans = max(AB[n][1] + dp1[n][w] + dp2[N - n - 1][T - 1 - w], ans) +        ans = max(ans, dp[n][w] + AB[n][1]) +        if w - AB[n][0] >= 0: +            dp[n + 1][w] = max(dp[n][w], dp[n][w - AB[n][0]] + AB[n][1]) +        else: +            dp[n + 1][w] = dp[n][w]