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

food = []

for _ in range(n):

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

    food.append((a, b))



dp1 = [[0]*T for _ in range(1+n)]

dp2 = [[0]*T for _ in range(1+n)]



for i in range(n):

    for j in range(T):

        dp1[i+1][j] = dp1[i][j]

        if j - food[i][0] >= 0:

            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j-food[i][0]] + food[i][1])



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

    for j in range(T):

        dp2[i][j] = dp2[i+1][j]

        if j - food[i][0] >= 0:

            dp2[i][j] = max(dp2[i][j], dp2[i+1][j-food[i][0]] + food[i][1])



res = 0

for i in range(n):

    for j in range(T):

        res = max(res, food[i][1] + dp1[i][j] + dp2[i+1][T-1-j])

print(res)
n, t = list(map(int, input().split()))

l = []

 

for i in range(n):

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

  l.append((a, b))

 

l.sort()

 

ans = 0

dp = [[0]*t for _ in range(n+1)]

for i in range(n):

  cur = dp[i][t-1] + l[i][1]

  ans = max(ans, cur)

  for j in range(t):

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

    nj = j+l[i][0]

    if nj < t:

      dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+l[i][1])

print(ans)
n, T = list(map(int, input().split()))
food = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    food.append((a, b))
dp1 = [[0] * T for _ in range(1 + n)]
dp2 = [[0] * T for _ in range(1 + n)]
for i in range(n):
    for j in range(T):
        dp1[i + 1][j] = dp1[i][j]
        if j - food[i][0] >= 0:
            dp1[i + 1][j] = max(dp1[i + 1][j], dp1[i][j - food[i][0]] + food[i][1])
for i in range(n - 1, -1, -1):
    for j in range(T):
        dp2[i][j] = dp2[i + 1][j]
        if j - food[i][0] >= 0:
            dp2[i][j] = max(dp2[i][j], dp2[i + 1][j - food[i][0]] + food[i][1])
res = 0
for i in range(n):
    for j in range(T):
        res = max(res, food[i][1] + dp1[i][j] + dp2[i + 1][T - 1 - j])
print(res)

n, t = list(map(int, input().split()))
l = []
for i in range(n):
    a, b = list(map(int, input().split()))
    l.append((a, b))
l.sort()
ans = 0
dp = [[0] * t for _ in range(n + 1)]
for i in range(n):
    cur = dp[i][t - 1] + l[i][1]
    ans = max(ans, cur)
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + l[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + l[i][1])
print(ans)

-n, T = list(map(int, input().split())) -food = [] -for _ in range(n): +n, t = list(map(int, input().split())) +l = [] +for i in range(n): -    food.append((a, b)) -dp1 = [[0] * T for _ in range(1 + n)] -dp2 = [[0] * T for _ in range(1 + n)] +    l.append((a, b)) +l.sort() +ans = 0 +dp = [[0] * t for _ in range(n + 1)] -    for j in range(T): -        dp1[i + 1][j] = dp1[i][j] -        if j - food[i][0] >= 0: -            dp1[i + 1][j] = max(dp1[i + 1][j], dp1[i][j - food[i][0]] + food[i][1]) -for i in range(n - 1, -1, -1): -    for j in range(T): -        dp2[i][j] = dp2[i + 1][j] -        if j - food[i][0] >= 0: -            dp2[i][j] = max(dp2[i][j], dp2[i + 1][j - food[i][0]] + food[i][1]) -res = 0 -for i in range(n): -    for j in range(T): -        res = max(res, food[i][1] + dp1[i][j] + dp2[i + 1][T - 1 - j]) -print(res) +    cur = dp[i][t - 1] + l[i][1] +    ans = max(ans, cur) +    for j in range(t): +        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) +        nj = j + l[i][0] +        if nj < t: +            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + l[i][1]) +print(ans)