CodeEff/ECCO huggingface dataset:
# Original solution
n, t = list(map(int, input().split()))
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(a[0])] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print((max(ans)))

# Optimized solution
n, t = list(map(int, input().split()))
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print((max(ans)))
# Original solution
N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for i in range(N)]

# dp1[i][j] := 商品0 ~ i が対象
# dp2[i][j] := 商品i ~ N が対象(順番はそのまま)
# out-of-index 対策に余分に取っておく
dp1 = [[0] * (W + 1) for i in range(N + 2)]
dp2 = [[0] * (W + 1) for i in range(N + 2)]

# dp1を埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi)
        dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j])

# dp2を埋める
for i in range(N + 1, 1, -1):
    wi, vi = items[i - 2]
    for j in range(W + 1):
        if j + wi <= W:
            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi)
        dp2[i - 1][j] = max(dp2[i][j], dp2[i - 1][j])


# 2つのdpテーブルを使って、最後に使う商品を全探索
ans = 0
# ここからは商品を1-indexedとする
for i, (wi, vi) in enumerate(items, start=1):
    for j in range(W):
        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi)

print(ans)


# Optimized solution
N, W = list(map(int, input().split()))
items = sorted([list(map(int, input().split())) for i in range(N)])

# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
for i, (wi, vi) in enumerate(items):
    for j in range(W):
        ans = max(ans, dp[i][j] + vi)

print(ans)
# Original solution
N, W = list(map(int, input().split()))
items = sorted([list(map(int, input().split())) for i in range(N)])

# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
for i, (wi, vi) in enumerate(items):
    for j in range(W):
        ans = max(ans, dp[i][j] + vi)

print(ans)


# Optimized solution
N, W = list(map(int, input().split()))
items = sorted([list(map(int, input().split())) for i in range(N)])

# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
for i, (wi, vi) in enumerate(items):
    ans = max(ans, dp[i][W - 1] + vi)

print(ans)
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = list(map(int,readline().split()))
f = []
m = 0
for i in range(n):
  p,q = list(map(int,readline().split()))
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print((max(dp[n])))

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = list(map(int,readline().split()))
f = []
m = 0
for i in range(n):
  p,q = list(map(int,readline().split()))
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j-a >= t:
      break
    if j < a :
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print((max(dp[n])))
# Original solution
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,t=list(map(int,readline().split()))
    li=[list(map(int,readline().split())) for _ in range(n)]
    li.sort()
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=li[i][0],li[i][1]

    #ナップサックDP
    inf=-float("inf")
    dp=[[inf]*(t+1) for _ in range(n+1)]
    dp[0][0]=0
    for i in range(n):
        for j in range(t+1):
            #i番目を食べる
            if j!=t:
                dp[i+1][min(t,j+a[i])]=max(dp[i+1][min(t,j+a[i])],dp[i][j]+b[i])
            
            #i番目を食べない
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])

    print((max(dp[n])))

if __name__=="__main__":
    main()

# Optimized solution
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,t=list(map(int,readline().split()))
    li=[list(map(int,readline().split())) for _ in range(n)]
    li.sort()
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=li[i][0],li[i][1]

    #ナップサックDP
    inf=-10**9
    dp=[[inf]*(t+1) for _ in range(n+1)]
    dp[0][0]=0
    for i in range(n):
        for j in range(t+1):
            #i番目を食べる
            if j!=t:
                dp[i+1][min(t,j+a[i])]=max(dp[i+1][min(t,j+a[i])],dp[i][j]+b[i])
            
            #i番目を食べない
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])

    print((max(dp[n])))

if __name__=="__main__":
    main()
# Original solution
n,t=list(map(int,input().split()))
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))
ab_r=list(reversed(ab))

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

for i in range(n):
    for j in range(t-1):
        if ab[i][0] <= j:
            dp1[i+1][j] = max(dp1[i][j],dp1[i][j-ab[i][0]]+ab[i][1])
        else:
            dp1[i+1][j] = dp1[i][j]
            
for i in range(n):
    for j in range(t-1):
        if ab_r[i][0] <= j:
            dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ab_r[i][0]]+ab_r[i][1])
        else:
            dp2[i+1][j] = dp2[i][j]
            
m=0
for i in range(1,n+1):
    for j in range(t-1):
        m=max(m,dp1[i-1][j]+dp2[n-i][t-1-j]+ab[i-1][1])
print(m)


# Optimized solution
n,t=list(map(int,input().split()))
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))
ab_r=list(reversed(ab))

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

for i in range(n):
    for j in range(t-1):
        if ab[i][0] <= j:
            dp1[i+1][j] = max(dp1[i][j],dp1[i][j-ab[i][0]]+ab[i][1])
        else:
            dp1[i+1][j] = dp1[i][j]
            
        if ab_r[i][0] <= j:
            dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ab_r[i][0]]+ab_r[i][1])
        else:
            dp2[i+1][j] = dp2[i][j]
            
m=0
for i in range(1,n+1):
    for j in range(t-1):
        m=max(m,dp1[i-1][j]+dp2[n-i][t-1-j]+ab[i-1][1])
print(m)
# Original solution
#16:25
n,t = list(map(int,input().split()))
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
now = [0 for _ in range(t+1)]
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f >= w:
      now.append(max(last[f-w]+v,last[f]))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
print((now[-1]))

# Optimized solution
n,t = list(map(int,input().split()))
dish = []
for _ in range(n):
  a,b = list(map(int,input().split()))
  dish.append([a,b])
dish.sort()
now = [0 for _ in range(t+1)]
for i in range(n):
  a,b = dish[i]
  for d in range(t)[::-1]:
    if d + a < t:
      now[d+a] = max(now[d+a],now[d]+b)
    else:
      now[-1] = max(now[-1],now[d]+b)
  #print(now)
print((now[-1]))
# Original solution
import math

def main():

    N, T = list(map(int, input().split()))
    C = []
    for _ in range(N):
        A, B = list(map(int, input().split()))
        C.append([B, A])
    C.sort()

    dp = [[0, 0] for _ in range(T)]
    ans = 0
    for i in range(T):
        for j in range(N):
            if (dp[i][1] >> j) % 2 == 0:
                if i+C[j][1] > T-1:
                    ans = max(ans, dp[i][0] + C[j][0])
                else:
                    if dp[i][0]+C[j][0] > dp[i+C[j][1]][0]:
                        dp[i+C[j][1]][0] = dp[i][0]+C[j][0]
                        dp[i+C[j][1]][1] = (1 << j) | dp[i][1]

    for i in range(T):
        ans = max(ans, dp[i][0])
    return ans



if __name__ == '__main__':
    print((main()))


# Optimized solution
import math

def main():

    N, T = list(map(int, input().split()))
    C = []
    for _ in range(N):
        A, B = list(map(int, input().split()))
        C.append([B, A])
    # C.sort()

    dp = [[0, 0] for _ in range(T)]
    ans = 0
    for i in range(T):
        for j in range(N):
            if (dp[i][1] >> j) % 2 == 0:
                if i+C[j][1] > T-1:
                    ans = max(ans, dp[i][0] + C[j][0])
                else:
                    if dp[i][0]+C[j][0] > dp[i+C[j][1]][0]:
                        dp[i+C[j][1]][0] = dp[i][0]+C[j][0]
                        dp[i+C[j][1]][1] = (1 << j) | dp[i][1]

    # print(dp)
    for i in range(T):
        ans = max(ans, dp[i][0])
    return ans

if __name__ == '__main__':
    print((main()))
# Original solution
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,T = list(map(int,S().split()))
A = [0]
B = [0]
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

dp1 = [[0]*(T+1) for i in range(N+1)]
# dp[i][j] = 1~i番目から選んでT分以内に食べるときの美味しさの和の最大値
dp2 = [[0]*(T+1) for i in range(N+2)]
# dp[i][j] = i~N番目から選んでT分以内に食べるときの美味しさの和の最大値

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

ans = dp1[N][T]
for i in range(1,N+1):  # 最後にi番目の料理を食べる
    for j in range(T):
        ans = max(ans,dp1[i-1][j]+dp2[i+1][T-1-j]+B[i])

print(ans)

# Optimized solution
def main():
    import sys
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    def S():
        return sys.stdin.readline().rstrip()

    N, T = list(map(int, S().split()))
    A = [0]
    B = [0]
    for i in range(N):
        a, b = LI()
        A.append(a)
        B.append(b)

    dp1 = [[0] * (T + 1) for i in range(N + 1)]
    # dp1[i][j] = 1~i番目から選んでT分以内に食べるときの美味しさの和の最大値
    dp2 = [[0] * (T + 1) for i in range(N + 2)]
    # dp2[i][j] = i~N番目から選んでT分以内に食べるときの美味しさの和の最大値

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

    ans = dp1[N][T]
    for i in range(1, N + 1):  # 最後にi番目の料理を食べる
        for j in range(T):
            ans = max(ans, dp1[i - 1][j] + dp2[i + 1][T - 1 - j] + B[i])

    print(ans)

if __name__ == '__main__':
    main()
# Original solution
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, t = LMIIS()
    ab = XLMIIS(n)

    dp1 = [[0]*t for _ in range(n)]
    for i in range(1, n):
        for j in range(1, t):
            if j < ab[i-1][0]:
                dp1[i][j] = dp1[i-1][j]
            else:
                dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-ab[i-1][0]] + ab[i-1][1])


    dp2 = [[0]*t for _ in range(n)]
    for i in range(1, n):
        for j in range(1, t):
            if j < ab[n - i][0]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = max(dp2[i-1][j], dp2[i-1][j-ab[n-i][0]] + ab[n-i][1])

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

if __name__ == '__main__':
    main()


# Optimized solution
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, t = LMIIS()
    ab = XLMIIS(n)
    ab.sort()

    dp1 = [[0]*t for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, t):
            if j < ab[i-1][0]:
                dp1[i][j] = dp1[i-1][j]
            else:
                dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-ab[i-1][0]] + ab[i-1][1])

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

if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline
N, T = list(map(int, input().split()))
a = []
for _ in range(N):
  w, v = list(map(int, input().split()))
  a.append((w, v))
a.sort()
dp = [[0] * (T + 1) for _ in range(N + 1)]
for i in range(N):
  w, v = a[i]
  for j in range(T):
    if j + w >= T:
      dp[i + 1][T] = max(dp[i + 1][T], dp[i][j] + v)
    else:
      dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
  dp[i + 1][T] = max(dp[i + 1][T], dp[i][T])
print((max(dp[-1])))

# Optimized solution
import sys
input = sys.stdin.readline
N, T = list(map(int, input().split()))
t = [tuple(map(int, input().split())) for _ in range(N)]
t.sort()
dp = [0] * (T + 1)
for a, b in t:
  for i in range(T - 1, -1, -1):
    if i + a < T: dp[i + a] = max(dp[i + a], dp[i] + b)
    else: dp[-1] = max(dp[-1], dp[i] + b) 
print((max(dp)))
# Original solution
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W
# ty geekforgeeks
def knapSack(W, wt, val, n, avoid): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1):
            if avoid != None:
                index = i if i <= avoid else i + 1
            else:
                index = i
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[index-1] <= w: 
                K[i][w] = max(val[index-1] + K[i-1][w-wt[index-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 

N, T = list(map(int, input().split()))
wts = [None for i in range(N)]
val = [None for i in range(N)]
for i in range(N):
    a, b = list(map(int, input().split()))
    wts[i] = a
    val[i] = b

best = knapSack(T, wts, val, N, None)
for i in range(N):
    best = max(best, knapSack(T-1, wts, val, N - 1, i) + val[i])
print(best)



# Optimized solution
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W
# ty geekforgeeks
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1):
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
        res = K[n][W] 
      
    w = W
    used = [False for i in range(N)]
    for i in range(n, 0, -1): 
        if res <= 0: 
            break
        # either the result comes from the 
        # top (K[i-1][w]) or from (val[i-1] 
        # + K[i-1] [w-wt[i-1]]) as in Knapsack 
        # table. If it comes from the latter 
        # one/ it means the item is included. 
        if res == K[i - 1][w]: 
            continue
        else: 
            # This item is included. 
            used[i - 1] = True
              
            # Since this weight is included 
            # its value is deducted 
            res = res - val[i - 1] 
            w = w - wt[i - 1] 
    return K[n][W], used

N, T = list(map(int, input().split()))
wts = [None for i in range(N)]
val = [None for i in range(N)]
for i in range(N):
    a, b = list(map(int, input().split()))
    wts[i] = a
    val[i] = b

best, _ = knapSack(T, wts, val, N)
other, used = knapSack(T - 1, wts, val, N)
add = 0
for i, wasUsed in enumerate(used):
    if not wasUsed: add = max(add, val[i])
print((max(best, other + add)))
# Original solution
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)

# Optimized solution
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)
# Original solution
import sys
import math

MOD=10**9+7

N,T=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(N)] 
l.sort(reverse=True)

dp1=[[-10**10 for i in range(T)] for i in range(N)]
dp2=[[0 for i in range(T)] for i in range(N)]

[a,b]=l[0]
dp1[0][0],dp2[0][0]=0,b
if a<T: dp1[0][a]=b

for i in range(1,N):
    [a,b]=l[i]
    m=min(a,T)
    for j in range(m):
        dp1[i][j]=dp1[i-1][j]
        dp2[i][j]=max(b,dp2[i-1][j])
    for j in range(m,T):
        p,q=dp1[i-1][j],dp1[i-1][j-a]+b
        if p<q:
            dp1[i][j]=q
            dp2[i][j]=dp2[i-1][j-a]
        elif p>q:
            dp1[i][j]=p
            dp2[i][j]=max(dp2[i-1][j],b)
        else:
            dp1[i][j]=p
            dp2[i][j]=max(dp2[i-1][j-a],dp2[i-1][j],b)

print((max( dp1[N-1][j]+dp2[N-1][j] for j in range(T) ) ))

# Optimized solution
ans=0
n,t=list(map(int,input().split()))
food=[]
for i in range(n):
    f=list(map(int,input().split()))
    food.append(f)
food=sorted(food)
dp=[0,0]+[-1]*(t-1)

for a,b in food:
    tmp=[dp[i] for i in range(t)]
    for i in range(t):
        if dp[i]==-1: continue
        j=i+a
        if j<t: tmp[j]=max(tmp[j],dp[i]+b)
        else: ans=max(ans,dp[i]+b)
    
    dp=[tmp[i] for i in range(t)]
print((max(ans,max(dp))))
# Original solution
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

# Optimized solution
import sys
from operator import itemgetter

input = sys.stdin.readline

#################
# 定数
#################
TIME = 0
VAL = 1

##################
# 入力処理
##################
N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)] + [None] * (N)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))

###########################
# 動的計画法（Knapsack problem）のテーブル埋め
# 時間の最大値は T - 1
##########################
dp = [[-1] * T for _ in range(N + 1)] # (N+1)行 x T列 2次元リスト

for t in range(0, T):
    dp[0][t] = 0

for n in range(1, N + 1):
    dp[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp[n][t] = dp[n - 1][t]
        else:
            dp[n][t] = max(dp[n - 1][t],
                             time_value[n][VAL] + dp[n - 1][t - time_value[n][TIME]])

##########################
# DPテーブルを用いて問題を解く
##########################

# t = T - 1に食べ始める料理が N, N-1, N-2, ..., 2, 1それぞれの場合で
# 美味しさの最大値を出し、更にその最大値を取る

# 最後に食べる料理がNの場合
val_acum = time_value[N][VAL]
t = T - 1  # N以外の料理を食べるのに使える時間
max_val = val_acum + dp[N - 1][t]

for n in range(N - 1, 0, -1):  # 最後に食べる料理が n = N-1, N-2, ..., 2, 1の場合
    val_acum += time_value[n][VAL] # 料理 N, N-1, ..., nの美味しさ合計
    t -= time_value[n + 1][TIME] # その他の料理 1, 2, ..., n-1を食べるのに使える時間
    if t < 0:
        break
    else:
        max_val = max(max_val, val_acum + dp[n - 1][t])

print(max_val)