CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n,t = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab.sort(key=lambda x: x[1])
    ab.sort(key=lambda x: x[0])
    dp = [-1]*(t+1)
    dp[0] = 0
    for a, b in ab:
        for j in range(t-1, -1, -1):
            if dp[j] >= 0:
                if j+a<=t:
                    dp[j+a] = max(dp[j+a], dp[j]+b)
                else:
                    dp[-1] = max(dp[-1], dp[j]+b)
    print((max(dp)))

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n,t = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    #ab.sort(key=lambda x: x[1])
    ab.sort(key=lambda x: x[0])
    dp = [-1]*(t+1)
    dp[0] = 0
    for a, b in ab:
        for j in range(t-1, -1, -1):
            if dp[j] >= 0:
                if j+a<=t:
                    dp[j+a] = max(dp[j+a], dp[j]+b)
                else:
                    dp[-1] = max(dp[-1], dp[j]+b)
    print((max(dp)))

if __name__ == '__main__':
    main()
# Original solution
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, t = ril()
ls = rils(n)

dp = [[0] * t for _ in range(n + 1)]
for i in range(n + 1):
    for t0 in range(t):
        a, b = ls[i - 1]
        if i == 0 or t0 == 0:
            continue
        elif a <= t0:
            dp[i][t0] = max(dp[i - 1][t0], dp[i - 1][t0 - a] + b)
        else:
            dp[i][t0] = dp[i - 1][t0]

res = set()
val = dp[n][t - 1]
t0 = t - 1
for i in reversed(list(range(n))):
    a, b = ls[i]
    if val <= 0:
        break
    if val == dp[i][t0]:
        continue
    else:
        res.add(i)
        val -= b
        t0 -= a

remaining = [v for i, (_, v) in enumerate(ls) if i not in res]
if len(remaining) > 0:
    print((dp[n][t - 1] + max(remaining)))
else:
    print((dp[n][t - 1]))

# Optimized solution
# Python3 TLE, PyPy3 AC

import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, t = ril()
ls = rils(n)

dp = [[0] * t for _ in range(n + 1)]
for i in range(n + 1):
    for t0 in range(t):
        a, b = ls[i - 1]
        if i == 0 or t0 == 0:
            continue
        elif a <= t0:
            dp[i][t0] = max(dp[i - 1][t0], dp[i - 1][t0 - a] + b)
        else:
            dp[i][t0] = dp[i - 1][t0]

res = set()
val = dp[n][t - 1]
t0 = t - 1
for i in reversed(list(range(n))):
    a, b = ls[i]
    if val <= 0:
        break
    if val == dp[i][t0]:
        continue
    else:
        res.add(i)
        val -= b
        t0 -= a

m = 0
for i, (_, v) in enumerate(ls):
    if i not in res:
        m = max(m, v)
print((dp[n][t - 1] + m))
# Original solution
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, T = inpl()
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = inpl()

dp_intime = [[0]*T for _ in range(N+1)]
dp_total = [[0]*T for _ in range(N+1)]
for n in range(1,N+1):
    for t in range(T):
        if A[n-1] > t:
            dp_intime[n][t] = dp_intime[n-1][t]
            dp_total[n][t] = max(B[n-1]+dp_intime[n-1][t], dp_total[n-1][t])
        else:
            dp_intime[n][t] = max(dp_intime[n-1][t], B[n-1]+dp_intime[n-1][t-A[n-1]])
            dp_total[n][t] = max(B[n-1]+dp_intime[n-1][t],
                                 B[n-1]+dp_total[n-1][t-A[n-1]],
                                 dp_total[n-1][t])
print((dp_total[-1][-1]))

# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, T = inpl()
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = inpl()

dp_intime = [0]*T
dp_total = [0]*T
for n in range(N):
    dp_intime_prev, dp_intime = dp_intime, [0]*T
    dp_total_prev, dp_total = dp_total, [0]*T
    for t in range(T):
        if A[n] > t:
            dp_intime[t] = dp_intime_prev[t]
            dp_total[t] = max(B[n]+dp_intime_prev[t], dp_total_prev[t])
        else:
            dp_intime[t] = max(dp_intime_prev[t], B[n]+dp_intime_prev[t-A[n]])
            dp_total[t] = max(B[n]+dp_intime_prev[t],
                              B[n]+dp_total_prev[t-A[n]],
                              dp_total_prev[t])
print((dp_total[-1]))
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, T = inpl()
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = inpl()

dp_intime = [0]*T
dp_total = [0]*T
for n in range(N):
    dp_intime_prev, dp_intime = dp_intime, [0]*T
    dp_total_prev, dp_total = dp_total, [0]*T
    for t in range(T):
        if A[n] > t:
            dp_intime[t] = dp_intime_prev[t]
            dp_total[t] = max(B[n]+dp_intime_prev[t], dp_total_prev[t])
        else:
            dp_intime[t] = max(dp_intime_prev[t], B[n]+dp_intime_prev[t-A[n]])
            dp_total[t] = max(B[n]+dp_intime_prev[t],
                              B[n]+dp_total_prev[t-A[n]],
                              dp_total_prev[t])
print((dp_total[-1]))

# Optimized solution
inpl = lambda: list(map(int,input().split()))
N, T = inpl()
AB = sorted([inpl() for _ in range(N)])

ans = 0
dp_intime = [0]*T
for n in range(N):
    dp_intime_prev = dp_intime
    dp_intime = [0]*T
    a, b = AB[n]
    for t in range(T):
        if t < a:
            dp_intime[t] = dp_intime_prev[t]
        else:
            dp_intime[t] = max(dp_intime_prev[t], dp_intime_prev[t-a]+b)
    ans = max(ans, dp_intime_prev[-1]+b)
print(ans)
# Original solution
N,T = list(map(int,input().split()))
data = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0 for n in range(N+1)] for t in range(T+1)] #dp1[t][n] := (data[:n]の中からtまでに食べ切る範囲で美味しく）
dp2 = [[0 for n in range(N+1)] for t in range(T+1)] #dp1[t][n] := (data[:n]の中からt-1までに注文する範囲で美味しく)


for t in range(1,T+1):
    for n in range(1,N+1):
        if t-data[n-1][0] >= 0:
            dp1[t][n] = max(dp1[t][n-1],dp1[t-data[n-1][0]][n-1]+data[n-1][1])
            dp2[t][n] = max(dp2[t][n-1],dp2[t-data[n-1][0]][n-1]+data[n-1][1],dp1[t-1][n-1]+data[n-1][1])
        else:
            dp1[t][n] = dp1[t][n-1]
            dp2[t][n] = max(dp2[t][n-1],dp1[t-1][n-1]+data[n-1][1])


print((dp2[T][N]))

# Optimized solution
import sys
input = sys.stdin.readline
N,T = list(map(int,input().split()))
data = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*(N+1) for t in range(T+1)] #dp1[t][n] := (data[:n]の中からtまでに食べ切る範囲で美味しく）
dp2 = [[0]*(N+1) for t in range(T+1)] #dp1[t][n] := (data[:n]の中からt-1までに注文する範囲で美味しく)


for t in range(1,T+1):
    for n in range(1,N+1):
        if t-data[n-1][0] >= 0:
            dp1[t][n] = max(dp1[t][n-1],dp1[t-data[n-1][0]][n-1]+data[n-1][1])
            dp2[t][n] = max(dp2[t][n-1],dp2[t-data[n-1][0]][n-1]+data[n-1][1],dp1[t-1][n-1]+data[n-1][1])
        else:
            dp1[t][n] = dp1[t][n-1]
            dp2[t][n] = max(dp2[t][n-1],dp1[t-1][n-1]+data[n-1][1])


print((dp2[T][N]))
# Original solution
import sys
input = sys.stdin.readline
n,t = list(map(int,input().split()))
data = [list(map(int,input().split())) for _ in range(n)]

dp1 = [[0 for i in range(n+1)] for j in range(t+1)]
dp2 = [[0 for i in range(n+1)] for j in range(t+1)]

q = 0
for i in range(1,n+1):
    q = max(q,data[i-1][0])
    dp2[1][i] = q

for i in range(1,t+1):
    for j in range(1,n+1):
        if i-data[j-1][0] >= 0:
            dp1[i][j] = max(dp1[i][j-1],dp1[i-data[j-1][0]][j-1]+data[j-1][1])
            dp2[i][j] = max(dp2[i][j-1],dp2[i-data[j-1][0]][j-1]+data[j-1][1],dp1[i-1][j-1]+data[j-1][1])
        else:
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = max(dp2[i][j-1],dp1[i-1][j-1]+data[j-1][1])


print((dp2[t][n]))

# Optimized solution
N,T = list(map(int, input().split()))
data = [list(map(int, input().split())) for i in range(N)]
dp1 = [[0]*(N+1) for _ in range(T+1)]
dp2 = [[0]*(N+1) for _ in range(T+1)]

for t in range(T):
    for n in range(N):
        if t+1-data[n][0]>=0:
            dp1[t+1][n+1] = max(dp1[t+1][n],dp1[t+1-data[n][0]][n]+data[n][1])
            dp2[t+1][n+1] = max(dp2[t+1][n],dp2[t+1-data[n][0]][n]+data[n][1],
                                dp1[t][n]+data[n][1])
        else:
            dp1[t+1][n+1] = dp1[t+1][n]
            dp2[t+1][n+1] = max(dp2[t+1][n],dp1[t][n]+data[n][1])

print((dp2[T][N]))
# Original solution
N,T=list(map(int,input().split()))
A,B=[],[]
for i in range(N):
    a,b=list(map(int,input().split()))
    A.append(a);B.append(b)
dp=[[[0,0] for i in range(T)] for i in range(N+1)]

for i in range(N):
    for j in range(T):
        if j-A[i]>=0:
            dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j-A[i]][0]+B[i])
            dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j-A[i]][1]+B[i])
        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0])
        dp[i+1][j][1]=max([dp[i+1][j][1],dp[i][j][0]+B[i],dp[i][j][1]])
ans=max(dp[N][T-1][0],dp[N][T-1][1])
print(ans)

# Optimized solution
N,T=list(map(int,input().split()))
A,B=[],[]
for i in range(N):
    a,b=list(map(int,input().split()))
    A.append(a);B.append(b)
dp=[[0,0] for i in range(T)]

for i in range(N):
    for j in reversed(list(range(T))):
        dp[j][1]=max(dp[j][1],dp[j][0]+B[i])
        if j-A[i]>=0:
            dp[j][0]=max(dp[j-A[i]][0]+B[i],dp[j][0])
            dp[j][1]=max(dp[j-A[i]][1]+B[i],dp[j][1])
ans=max(dp[T-1][0],dp[T-1][1])
print(ans)
# Original solution
"""
食べるのにかかる時間順にソートしてナップサックするのがよい。
dp[i][j]
"""
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 _ in range(N+1)]
for i in range(1,N+1):
    a,b = AB[i-1]
    for j in range(1,T):
        if j-a >= 0:
            dp[i][j] = max(dp[i-1][j-a]+b,dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(1,N):
    a,b = AB[i]
    ans = max(ans,dp[i][-1]+b)
print(ans)

# Optimized solution
N,T = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort()

dp = [0]*(T)
ans = 0
for i in range(N):
    a,b = AB[i]
    ans = max(ans,dp[-1]+b)
    for j in range(T-1,-1,-1):
        if j - a >= 0:
            dp[j] = max(dp[j],dp[j-a]+b)
print(ans)
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]

    dp1 = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp1[i + 1][t] = dp1[i][t - A[i]] + B[i]
            if dp1[i + 1][t] < dp1[i][t]:
                dp1[i + 1][t] = dp1[i][t]

    dp2 = [[0] * T for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for t in range(T):
            if 0 <= t - A[i]:
                dp2[i][t] = dp2[i + 1][t - A[i]] + B[i]
            if dp2[i][t] < dp2[i + 1][t]:
                dp2[i][t] = dp2[i + 1][t]

    ans = 0
    for i in range(N):
        tmp = max(dp1[i][t] + dp2[i + 1][T - t - 1] for t in range(T)) + B[i]
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = list(map(int, read().split()))
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()
    A, B = list(zip(*D))

    dp = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp[i + 1][t] = dp[i][t - A[i]] + B[i]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        tmp = dp[i+1][T - 1] + max(B[i + 1 :], default=0)
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = list(map(int, read().split()))
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()
    A, B = list(zip(*D))

    dp = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp[i + 1][t] = dp[i][t - A[i]] + B[i]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        tmp = dp[i+1][T - 1] + max(B[i + 1 :], default=0)
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = list(map(int, read().split()))
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()
    A, B = list(zip(*D))

    dp = [[0] * T for _ in range(N + 1)]
    for i, (a, b) in enumerate(D):
        for t in range(T):
            if 0 <= t - a:
                dp[i + 1][t] = dp[i][t - a] + b
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        tmp = dp[i + 1][T - 1] + max(B[i + 1 :], default=0)
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = list(map(int, read().split()))
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    max_sum = [0] * N
    for i, (a, b) in enumerate(D):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b
        max_sum[i] = dp[T - 1]

    ans = max(max_sum[i] + D[i + 1][1] for i in range(N - 1))

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = list(map(int, read().split()))
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    ans = 0
    for i, (a, b) in enumerate(D[:-1]):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b

        if ans < dp[T - 1] + D[i + 1][1]:
            ans = dp[T - 1] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
n,t=list(map(int,input().split()))
F=[list(map(int,input().split())) for i in range(n)]
dp1=[[0]*(t+1) for i in range(n)]
for i in range(1,n):
  for j in range(1,t+1):
    if j-F[i-1][0]>=0:
      dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1],dp1[i-1][j-F[i-1][0]]+F[i-1][1])
    else:
      dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])
dp2=[[0]*(t+1) for i in range(n)]
for i in range(1,n):
  for j in range(1,t+1):
    if j-F[n-i][0]>=0:
      dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1],dp2[i-1][j-F[n-i][0]]+F[n-i][1])
    else:
      dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1])
ans=0
for i in range(n):
  for j in range(1,t):
    a=dp1[i][j]+dp2[n-i-1][t-j-1]+F[i][1]
    if a>ans:
      ans=a
print(ans)

# Optimized solution
n,t=list(map(int,input().split()))
l=[list(map(int,input().split())) for _ in range(n)]
l.sort()
dp=[0]*(t+max(l)[0])
for a,b in l:
  for i in range(0,t+a)[::-1]: 
    if i-a>=0:
      dp[i]=max(dp[i],dp[i-a]+b)
print((max(dp[t:])))
# Original solution
import sys
input=sys.stdin.readline
n,t=list(map(int,input().split()))
AB=[]
for i in range(n):
  a,b=list(map(int,input().split()))
  AB.append((a,b))

def f(m):
  dp=[[0]*(t) for _ in range(n+1)]
  for i in range(n):
    if i==m:
      a,b=AB[i]
      add=b
      for j in range(t):
        dp[i+1][j]=dp[i][j]
    else:
      a,b=AB[i]
      for j in range(t):
        if j>=a:
          dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
        else:
          dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  return dp[n][t-1]+add
ans=0
for i in range(n):
  ans=max(ans,f(i))
print(ans)


# Optimized solution
import sys
input=sys.stdin.readline
n,t=list(map(int,input().split()))
AB=[]
for i in range(n):
  a,b=list(map(int,input().split()))
  AB.append((a,b))
AB.sort(key=lambda x:x[0])
ans=0
dp=[[0]*(t) for _ in range(n+1)]
for i in range(n-1):
  a,b=AB[i]
  for j in range(t):
    if j>=a:
      dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
    else:
      dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  ans=max(ans,dp[i+1][t-1]+AB[i+1][1])

print(ans)
# Original solution

from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = make_multi_list(0, [3000, 3000])
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        # iを使うパターン
        nj = j+a
        if nj < T:
            dp[i+1][nj] = max(dp[i + 1][nj], dp[i][j]+b)
    now = dp[i][T-1]+AB[i][1]
    ans = max(ans, now)

print(ans)

# Optimized solution
from copy import deepcopy

# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = make_multi_list(0, [3005, 3005])
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)
# Original solution
from copy import deepcopy

# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = make_multi_list(0, [3005, 3005])
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)


# Optimized solution
N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = dp = [[0 for _ in range(3005)] for _ in range(3005)]
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)
# Original solution
N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = dp = [[0 for _ in range(3005)] for _ in range(3005)]
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)


# Optimized solution
N, T = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a, b))
AB.sort()

ans = 0
dp = [[0 for _ in range(3005)] for _ in range(3005)]
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # iを使うパターン
        nj = j + a
        if nj < T:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + b)
    now = dp[i][T - 1] + b
    ans = max(ans, now)

print(ans)
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def penalty(day, last, c):
    val = 0
    for i in range(26):
        val += c[i] * (day - last[i])
    return val

def calcScore(t, s, c):
    val = 0
    for i in range(26):
        last = 0
        for j in range(len(t)):
            if t[j] == i:
                val += s[j][i]
                val -= c[i]*(j-last)*(j-last-1)//2
                last = j
        val -= c[i]*(len(t)-last)*(len(t)-last-1)//2
    return val

D = int(eval(input()))
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(eval(input())) - 1
M = int(eval(input()))

score = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = list(map(int, input().split()))
    t[d] = q-1
    ans[i] = calcScore(t, s, c)

for v in ans:
    print(v)

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

D = int(eval(input()))
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(eval(input())) - 1
M = int(eval(input()))

scores = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = list(map(int, input().split()))
    t[d] = q-1
    ans[i] = sum(calcScore(t, s, c))

for v in ans:
    print(v)