CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline

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

DP = [[[0] * 2 for _ in range(T)] for _ in range(N)]

a, b = AB[0]
if a < T:
  DP[0][a][0] = b
DP[0][0][1] = b

for i in range(1, N):
  a, b = AB[i]
  if a < T:
    DP[i][a][0] = b
  DP[i][0][1] = b
  for j in range(T):
    DP[i][j][0] = max(DP[i][j][0], DP[i - 1][j][0])
    DP[i][j][1] = max(DP[i][j][1], DP[i - 1][j][1])
    if j + a < T: 
      DP[i][j + a][0] = max(DP[i][j + a][0], DP[i - 1][j][0] + b)
      DP[i][j + a][1] = max(DP[i][j + a][1], DP[i - 1][j][1] + b)
    DP[i][j][1] = max(DP[i][j][1], DP[i - 1][j][1])
    DP[i][j][1] = max(DP[i][j][1], DP[i - 1][j][0] + b)

ans = 0
for i in range(T):
  ans = max(ans, DP[-1][i][0])
  ans = max(ans, DP[-1][i][1])

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

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

DP = [[[0] * 2 for _ in range(T)] for _ in range(2)]

a, b = AB[0]
if a < T:
  DP[0][a][0] = b
DP[0][0][1] = b

t = 1
for i in range(1, N):
  a, b = AB[i]
  if a < T:
    DP[t][a][0] = b
  DP[t][0][1] = b
  for j in range(T):
    DP[t][j][0] = max(DP[t][j][0], DP[1 - t][j][0])
    DP[t][j][1] = max(DP[t][j][1], DP[1 - t][j][1])
    if j + a < T: 
      DP[t][j + a][0] = max(DP[t][j + a][0], DP[1 - t][j][0] + b)
      DP[t][j + a][1] = max(DP[t][j + a][1], DP[1 - t][j][1] + b)
    DP[t][j][1] = max(DP[t][j][1], DP[1 - t][j][1])
    DP[t][j][1] = max(DP[t][j][1], DP[1 - t][j][0] + b)
  t = 1 - t
ans = 0
for i in range(T):
  ans = max(ans, DP[1 - t][i][0])
  ans = max(ans, DP[1 - t][i][1])

print(ans)
# Original solution
from collections import defaultdict
from heapq import heappush, heappop
N, T = list(map(int, input().split()))
dic = defaultdict(list)
ls = []
pre = []
log = [[1]*N]*T
dp = [0]*(T)
for i in range(N):
  a, b = list(map(int, input().split()))
  ls += [(a,b)]
  if a<T:
    for j in range(T-1,a-1,-1):
      if dp[j-a]+b>dp[j]:
        dp[j] = dp[j-a]+b
        log[j] = log[j-a][:]
        log[j][i] = 0
  else:
    heappush(pre, -b)
m = 0
ind = -1
his = None
for j in range(T):
  if dp[j]>m:
    m = dp[j]
    ind = j
for c in range(N):
  if log[ind][c]:
    heappush(pre,-ls[c][1])

if pre:
  m -= heappop(pre)
print(m)

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

ls = []
for i in range(N):
  a, b = list(map(int, input().split()))
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

for i in range(N):
  a, b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)
    
pre = [0]*N
pre[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  pre[i] = max(pre[i+1], ls[i][1])
    
ans = 0
for i in range(N-1):
  ans = max(ans, max(dp[i+1])+pre[i+1])
ans = max(ans, max(dp[-1]))
print(ans)
# Original solution
N, T = list(map(int, input().split()))
ls = []
for i in range(N):
  a, b = list(map(int, input().split()))
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

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

for i in range(N):
  a,b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)

last = [0]*N
last[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  last[i] = max(last[i+1], ls[i][1])

ans = 0

for i in range(1,N+1):
  ans = max(ans, max(dp[i-1])+last[i-1])

print(ans)


# Optimized solution
N, T = list(map(int, input().split()))
ls = []
for i in range(N):
  a, b = list(map(int, input().split()))
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])
t = [[0]*T for i in range(N+1)]
for i in range(1,N+1):
  a, b = ls[i-1]
  for j in range(T):
    if j-a>=0:
      t[i][j] = max(t[i-1][j-a]+b,t[i-1][j])
last = [0]
for i in range(N-1,-1,-1):
  last += [max(last[-1], ls[i][-1])]
ans = 0
for i in range(1,N+1):
  j = N-i
  ans = max(ans, last[j]+t[i][-1])
print(ans)
# Original solution
N,T = list(map(int,input().split()))
A = [0]*N
B = [0]*N
for i in range(N):
    A[i],B[i] = list(map(int,input().split()))

# T-1分以内に完食を目指す，特定の料理のみ使わないで計算したい．
#DP1[i][t]はi番目の料理まででt分後までに完食で得られる幸福度の最大(商品番号は1から振る)
#DP2[i][t]はiからN番目の料理でt分後までに完食で得られる幸福度の最大

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

for i in range(N):
    for t in range(1,T):
        dp1[i+1][t] = dp1[i][t]
        if t-A[i]>=0:
            dp1[i+1][t]=max(dp1[i][t],dp1[i][t-A[i]]+B[i])


for i in reversed(list(range(0,N))):
    for t in range(1,T):
        dp2[i][t] = dp2[i+1][t]
        if t-A[i]>=0:
            dp2[i][t]=max(dp2[i+1][t],dp2[i+1][t-A[i]]+B[i])


ans=0
#i番目の料理を時間ギリギリに注文
for i in range(1,N):
    for j in range(0,T):
        ans = max(ans,dp1[i][j]+dp2[i+1][T-1-j]+B[i])
print(ans)

# Optimized solution
#Aをソートしておく，時間ギリギリにi番目の料理を頼むことで固定．
N,T = list(map(int,input().split()))
AB = [[0,0] for _ in range(N)]

for i in range(N):
    AB[i][0],AB[i][1] = list(map(int,input().split()))

AB.sort()
#ソートした時のbの情報を維持しないと

# T-1分以内にi番目以外の料理をできるだけ完食する
#DP1[i][t]はi番目の料理まででt分後までに完食で得られる幸福度の最大(商品番号は1から振る)


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

for i in range(N):
    for t in range(1,T):
        dp1[i+1][t] = dp1[i][t]
        if t-AB[i][0]>=0:
            dp1[i+1][t]=max(dp1[i][t],dp1[i][t-AB[i][0]]+AB[i][1])
            
ans=0
for i in range(N):
    ans=max(ans,dp1[i][-1]+AB[i][1])
print(ans)
# Original solution
N,T = list(map(int, input().split()))
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort()

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

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

    AB.sort()

    # dp[i][j]: 満足度の最大値
    # i: i品目まで
    # j: 制限時間(< T)
    dp = [[0] * 3100 for _ in range(3100)]

    dp[0][0] = 0

    # 貰うDP
    ans = 0
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]
            
            # ラストオーダーはAB[i - 1]
            ans = max(ans, dp[i][j] + AB[i - 1][1])

            if j - AB[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

    print(ans)

if __name__ == "__main__":
    main()
# Original solution
def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = list(map(int, input().split()))
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = list(map(int, input().split()))
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp_ht = [[0] * t for _ in range(n + 2)]  # head->tail
    dp_th = [[0] * t for _ in range(n + 2)]  # tail->head
    # dp[注文可能な範囲の端][完食にかかる総時間]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_ht[dish.idx][cost_] = max(dp_ht[dish.idx - 1][cost_],
                                             dp_ht[dish.idx - 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_ht[dish.idx][cost_] = dp_ht[dish.idx - 1][cost_]

    for dish in reversed(dishes):
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_th[dish.idx][cost_] = max(dp_th[dish.idx + 1][cost_],
                                             dp_th[dish.idx + 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_th[dish.idx][cost_] = dp_th[dish.idx + 1][cost_]

    ret = 0
    for last_dish in dishes:
        for cost_ in range(t):
            ret = max(ret, dp_ht[last_dish.idx - 1][cost_] + dp_th[last_dish.idx + 1][t - 1 - cost_] + last_dish.pt)
    return ret


print((solve()))


# Optimized solution
def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = list(map(int, input().split()))
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = list(map(int, input().split()))
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp = [[0] * 2 for _ in range(t)]
    # dp[完食にかかる総時間][最後の皿を選んだか]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t - 1, -1, -1):
            dp[cost_][True] = max(dp[cost_][True], dp[cost_][False] + dish.pt)
            if cost_ >= dish.cost:
                dp[cost_][False] = max(dp[cost_][False], dp[cost_ - dish.cost][False] + dish.pt)
                dp[cost_][True] = max(dp[cost_][True], dp[cost_ - dish.cost][True] + dish.pt)

    return max(dp[cost_][True] for cost_ in range(t))


print((solve()))

# 最後の皿を選んだかフラグを設ける
# https://sen-comp.hatenablog.com/entry/2019/11/17/003150
# Original solution
def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = list(map(int, input().split()))
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = list(map(int, input().split()))
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp = [[0] * 2 for _ in range(t)]
    # dp[完食にかかる総時間][最後の皿を選んだか]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t - 1, -1, -1):
            dp[cost_][True] = max(dp[cost_][True], dp[cost_][False] + dish.pt)
            if cost_ >= dish.cost:
                dp[cost_][False] = max(dp[cost_][False], dp[cost_ - dish.cost][False] + dish.pt)
                dp[cost_][True] = max(dp[cost_][True], dp[cost_ - dish.cost][True] + dish.pt)

    return max(dp[cost_][True] for cost_ in range(t))


print((solve()))

# 最後の皿を選んだかフラグを設ける
# https://sen-comp.hatenablog.com/entry/2019/11/17/003150


# Optimized solution
def solve():
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = list(map(int, input().split()))
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = list(map(int, input().split()))
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dishes.sort(key=attrgetter('cost'))

    dp = [0] * t
    # dp[完食にかかる総時間]:= 美味しさの最大値

    ret = 0
    for dish in dishes:
        for cost_ in range(t - 1, -1, -1):
            ret = max(ret, dp[cost_] + dish.pt)
            if cost_ >= dish.cost:
                dp[cost_] = max(dp[cost_], dp[cost_ - dish.cost] + dish.pt)

    return ret


print((solve()))

# コスト昇順ソートした皿で、DPする
# 各皿は最後の皿（コスト0で、ポイントだけ加算し、以降は皿を取れない）にすることができる
# 最後の皿を選んだ時点でのポイントのmax
# https://sen-comp.hatenablog.com/entry/2019/11/17/003150
# Original solution
N, T, *AB = list(map(int, open(0).read().split()))

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(list(range(T))):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print((max(dp)))


# Optimized solution
def main():
    N, T, *AB = list(map(int, open(0).read().split()))

    dp = [0] * (T + max(AB[::2]))
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        for i in reversed(list(range(T))):
            dp[i + w] = max(dp[i + w], dp[i] + v)

    print((max(dp)))

main()
# Original solution
def main():
    N, T, *AB = list(map(int, open(0).read().split()))

    dp = [0] * (T + max(AB[::2]))
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        for i in reversed(list(range(T))):
            dp[i + w] = max(dp[i + w], dp[i] + v)

    print((max(dp)))

main()

# Optimized solution
def main():
    N, T, *AB = list(map(int, open(0).read().split()))

    dp = [0] * (T + max(AB[::2]))
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        for i in reversed(list(range(T))):
            if dp[i + w] < dp[i] + v:
                dp[i + w] =  dp[i] + v

    print((max(dp)))

main()
# Original solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x) - 1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n, t = li()
ab = [tuple(li()) for _ in range(n)]
ans = 0

for i in range(n):

    dic = defaultdict(int)
    dic[0] = 0
    for ai, bi in ab[:i] + ab[i+1:]:
        newdic = defaultdict(int)
        keys = list(dic.keys())
        for time, value in list(dic.items()):
            if time + ai < t and time + ai in keys:
                newdic[time + ai] = max(dic[time + ai], value + bi)
            elif time + ai < t:
                newdic[time + ai] = value + bi
            newdic[time] = max(newdic[time], value)
        dic = newdic

    ans = max(ans, max(dic.values()) + ab[i][1])

print(ans)


# Optimized solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x) - 1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n, t = li()
ab = [tuple(li()) for _ in range(n)]
ans = 0

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

for i, (ai, bi) in enumerate(ab):
    for ti in range(t):
        if ti + ai < t:
            dp[i+1][ti + ai] = max(dp[i][ti + ai], dp[i][ti] + bi)
        dp[i+1][ti] = max(dp[i+1][ti], dp[i][ti])

# 経路復元
chose = set()
maxtime = dp[n].index(max(dp[n]))

for idx in range(n, 0, -1):
    if dp[idx][maxtime] != dp[idx-1][maxtime]:
        chose.add(idx-1)
        maxtime -= ab[idx-1][0]

allitem = set(range(n))
notchose = allitem - chose

notchosemax = 0
if notchose:
    for i in notchose:
        notchosemax = max(notchosemax, ab[i][1])

print((max(dp[n]) + notchosemax))
# Original solution
import sys
from operator import itemgetter
from heapq import heapify, heappop, heappush
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return eval(input())

N, T = IL()
ab = [IL() for i in range(N)]
ab.sort(key=itemgetter(0))
#print(ab)

dp = [[0]*(T+1+3000+1) for _ in range(N+1)]
ans = 0
for i in range(N):
  for j in range(T+1+3000+1):
    time, deli = ab[i]
    if 0 <= j-time < T:
      dp[i + 1][j] = max(dp[i][j], dp[i][j - time] + deli)
    else:
      dp[i + 1][j] = dp[i][j]
    ans = max(ans, dp[i + 1][j])
print(ans)

#print(dp)


# Optimized solution
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return eval(input())

N,T = IL()
ab = [IL() for i in range(N)]
ab.sort()

ans = 0
dp = [[0]*T for i in range(N+1)]
for i in range(1,N+1):
  a,b = ab[i-1]
  for j in range(T):
    if 0 <= j-a < T:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b)
    else:
      dp[i][j] = dp[i-1][j]
  else:
    ans = max(ans, dp[i-1][-1] + b)
print(ans)
# Original solution
N, T = list(map(int, input().split()))
table = [[0] * (N + 1) for _ in range(T + 1)]
dish = sorted((tuple(map(int, input().split())) for _ in range(N)), key=lambda t: t[0])
for t in range(T + 1):
    for n in range(N):
        minutes_to_take, deliciousness = dish[n]
        now = table[t][n]
        if t < T:
            table[min(T, t + minutes_to_take)][n + 1] = max(table[min(T, t + minutes_to_take)][n + 1], now + deliciousness)
        if n < N:
            table[t][n + 1] = max(table[t][n + 1], now)
print((max(table[t][N] for t in range(T + 1))))

# Optimized solution
N, T = list(map(int, input().split()))
table = [[0] * (N + 1) for _ in range(T + 1)]
dish = sorted((tuple(map(int, input().split())) for _ in range(N)), key=lambda t: t[0])
for t in range(T + 1):
    for n in range(N):
        minutes_to_take, deliciousness = dish[n]
        now = table[t][n]
        if t < T:
            table[min(T, t + minutes_to_take)][n + 1] = max(table[min(T, t + minutes_to_take)][n + 1], now + deliciousness)
        if n < N:
            table[t][n + 1] = max(table[t][n + 1], now)
print((table[T][N]))
# Original solution
def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[[0,0] for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            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])
        for j in range(1,T+1):
            dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j-1][0] + 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][1])
#    print(dp[N][T])
    ans = max(dp[N][T])
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()


# Optimized solution
def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    dp2 = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - A[i]] + B[i])
            dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j - A[i]] + B[i])
        for j in range(1,T+1):
            dp2[i+1][j] = max(dp2[i+1][j], dp[i][j-1] + B[i], dp2[i][j])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#    print(dp[N][T])
    ans = dp2[N][T]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
wv.sort(key = lambda x:x[1],reverse = True)
res = 0
for i in range(min(n,10)):
    dp = [[0] * (t+5) for _ in range(n+5)]
    for j in range(n):
        w,v = wv[j]
        for k in range(t):
            if k < w or i == j:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-w] + v)
    # print(dp[n][t-1])
    res = max(dp[n][t-1] + wv[i][1], res)
print(res)

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
wv.sort(key = lambda x:x[1],reverse = True)
res = 0
for i in range(min(n,3)):
    dp = [[0] * (t+5) for _ in range(n+5)]
    for j in range(n):
        w,v = wv[j]
        for k in range(t):
            if k < w or i == j:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-w] + v)
    # print(dp[n][t-1])
    res = max(dp[n][t-1] + wv[i][1], res)
print(res)
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [None] * n
for i in range(n):
    a,b = inpl()
    wv[i] = (a,b)
rwv = wv[::-1]
udp = [[0] * t for _ in range(n)]
ddp = [[0] * t for _ in range(n)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = rwv[i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])
# print(res)
for i in range(1,n-1):
    u = i; d = n-i-1
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][t-1-j]
        mx = max(mx, tmp)
    res = max(res, mx + wv[i][1])
print(res)

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j] , dp[i][j-w] + v)
res = 0
for i in range(n):
    tmp = dp[i][t-1] + wv[i][1]
    res = max(res, tmp)
print(res)
# Original solution
n, t = list(map(int, input().split()))
a = [0]
b = [0]
for i in range(n):
    a_, b_ = list(map(int, input().split()))
    a.append(a_)
    b.append(b_)

dp1 = [[0] * t for _ in range(n+2)]
dp2 = [[0] * t for _ in range(n+2)]

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

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

ans = 0
for i in range(1, n+1):
    for j in range(t):
        total = b[i] +dp1[i-1][j] + dp2[i+1][t-1-j]
        ans = max(ans, total)
print(ans)

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

dp = [[0] * N for _ in range(T)]

for i in range(1, T):
    for j in range(N-1):
        if AB[j][0] <= i:
            dp[i][j] = max(dp[i][j-1], dp[i-AB[j][0]][j-1] + AB[j][1])
        else:
            dp[i][j] = dp[i][j-1]

ans = 0
for j in range(1, N):
    ans = max(ans, dp[-1][j-1] + AB[j][1])

print(ans)
# Original solution
n,t = list(map(int,input().split()))
time = [-1 for i in range(6030)]
time[0] = 0
now = 0
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[0])
for i in range(n):
    for j in range(t-1,-1,-1):
        if time[j] != -1:
            time[j+lis[i][0]] = max(time[j+lis[i][0]],time[j]+lis[i][1])
print((max(time)))

# Optimized solution
n,t = list(map(int,input().split()))
time = [0 for i in range(3000)]
now = 0
ans = 0
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key=lambda x:x[0])
for i in range(n):
    for j in range(t-1,-1,-1):
        if lis[i][0] + j >= t:
            ans = max(ans,time[j]+lis[i][1])
        else:
            time[j+lis[i][0]] = max(time[j+lis[i][0]],time[j]+lis[i][1])
print((max(ans,max(time))))