CodeEff/ECCO huggingface dataset:
# Original solution
n, t = list(map(int, input().split()))
dp1 = [[-float("inf") for i in range(t)] for i in range(n + 1)]
dp1[0][0] = 0
dp2 = [[-float("inf") for i in range(t)] for i in range(n + 1)]
dp2[n][0] = 0
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
for i in range(n):
    a, b = ab[i]
    for j in range(t - 1, -1, -1):
        if j >= a:
            dp1[i + 1][j] = max(dp1[i][j], dp1[i][j - a] + b)
        else:
            dp1[i + 1][j] = dp1[i][j]
for i in range(n - 1, -1, -1):
    a, b = ab[i]
    for j in range(t - 1, -1, -1):
        if j >= a:
            dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - a] + b)
        else:
            dp2[i][j] = dp2[i + 1][j]
ans = [max([max(dp1[i][:j + 1]) + max(dp2[i + 1][:t - j]) + ab[i][1]]) for j in range(t) for i in range(n)]
print((max(ans)))

# Optimized solution
n, t = list(map(int, input().split()))
dp1 = [[-float("inf") for i in range(t)] for i in range(n + 1)]
dp1[0][0] = 0
dp2 = [[-float("inf") for i in range(t)] for i in range(n + 1)]
dp2[n][0] = 0
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
for i in range(n):
    a, b = ab[i]
    for j in range(t - 1, -1, -1):
        if j >= a:
            dp1[i + 1][j] = max(dp1[i][j], dp1[i][j - a] + b)
        else:
            dp1[i + 1][j] = dp1[i][j]
for i in range(n + 1):
    for j in range(t - 1):
        dp1[i][j + 1] = max(dp1[i][j], dp1[i][j + 1])
for i in range(n - 1, -1, -1):
    a, b = ab[i]
    for j in range(t - 1, -1, -1):
        if j >= a:
            dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - a] + b)
        else:
            dp2[i][j] = dp2[i + 1][j]
for i in range(n + 1):
    for j in range(t - 1):
        dp2[i][j + 1] = max(dp2[i][j], dp2[i][j + 1])
ans = [max([dp1[i][j] + dp2[i + 1][t - 1 - j] + ab[i][1] for j in range(t)]) for i in range(n)]
print((max(ans)))
# Original solution
# dp[i][t_sum]: i番目までの品物で時間がt_sumを超えないように選んだときの、満足度の総和の最大値
N, T = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]

dp1 = [[0 for t_sum in range(T+1)] for i in range(N+2)]
dp2 = [[0 for t_sum in range(T+1)] for i in range(N+2)]

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

    for t_sum in range(T+1):
        if t_sum-items[N-1-i][0] >= 0:
            dp2[N-1-i][t_sum] = max(dp2[N-1-i][t_sum], dp2[N-i]
                                    [t_sum-items[N-1-i][0]]+items[N-1-i][1])
        dp2[N-1-i][t_sum] = max(dp2[N-1-i][t_sum], dp2[N-i][t_sum])


ans = 0
for i in range(N):
    for t in range(T):
        ans = max(ans, dp1[i][t]+dp2[i+1][T-1-t]+items[i][1])
print(ans)


# Optimized solution
# dp[i][t_sum]: i番目までの品物で時間がt_sumを超えないように選んだときの、満足度の総和の最大値
N, T = list(map(int, input().split()))
items = sorted([tuple(map(int, input().split()))
                for i in range(N)], key=lambda x: x[0])

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

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

ans = 0
for i in range(N):
    for t in range(T):
        ans = max(ans, dp1[i][t]+items[i][1])
print(ans)
# Original solution
n,t=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(n)]
ab.sort()
dp=[6007*[0]for _ in range(n)]
ans=0
for i in range(n):
  a,b=ab[i]
  for j in range(6007):
    if i==0:
      if j>=a and j<t:dp[i][j]=b
    elif j>=a and j-a<t:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
    ans=max(ans,dp[i][j])
print(ans)

# Optimized solution
n,t=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(n)]
ab.sort()
dp=[6007*[0]for _ in range(n)]
for i in range(n):
  a,b=ab[i]
  for j in range(6007):
    if i==0:
      if j>=a and j<t:dp[i][j]=b
    elif j>=a and j-a<t:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print((max(dp[-1])))
# Original solution
n,t=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(n)]
ab.sort()
dp=[(6007)*[0]for _ in range(n+1)]
dp[0][0]=0
ans=0
for i in range(n):
  for j in range(6007):
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
    if j<t:dp[i+1][j+ab[i][0]]=max(dp[i][j]+ab[i][1],dp[i][j+ab[i][0]])
    ans=max(ans,dp[i+1][j])
print(ans)


# Optimized solution
n,t=list(map(int,input().split()))
dp=[[0]*(t+3001)for _ in range(n+1)]
ans=0
ab=[list(map(int,input().split()))for _ in range(n)]
ab.sort()
for i in range(1,n+1):
    a,b=ab[i-1]
    for j in range(t):
        dp[i][j]=max(dp[i-1][j],dp[i][j])
        dp[i][j+a]=dp[i-1][j]+b
        ans=max(dp[i][j],dp[i][j+a],ans)
print(ans)
# Original solution
n,t = list(map(int,input().split()))
ab = [[int(i) for i in input().split()] for j in range(n)]

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

ans = 0

for h in range(n):
    dp = [[0 for i in range(t)] for j in range(n+1)]
    for i in range(n):
        if h == 0 and i == 0:
            continue
        if h == i:
            dp[i+1] = dp[i]
            continue
        for j in range(t):
            #print(h,i)
            dp[i+1][j] = dp[i][j]
            #print(j,ab[i][0])
            if j < ab[i][0]:
                #print(j)
                continue
            #if dp[i][j] < dp[i][j-ab[i][0]] + ab[i][1]:
            #    dp[i+1][j] = dp[i][j-ab[i][0]] + ab[i][1]
            dp[i+1][j] = max(dp[i][j],dp[i][j-ab[i][0]] + ab[i][1])
            #print(dp)
    #print(h,dp)
    ans = max(ans,dp[n][t-1]+ab[h][1])


print(ans)

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

dp = [[0 for i in range(t)] for j in range(n+1)]
ab.sort()

ans = 0

for i in range(n):
    for j in range(t):
        #for k in range(2):
        #dp[i+1][j] = max(dp[i][j],dp[i-1][j])
        dp[i+1][j] = dp[i][j]
        #print(j,ab[i][0])
        if j >= ab[i][0]:
        #if dp[i][j] < dp[i][j-ab[i][0]] + ab[i][1]:
        #    dp[i+1][j] = dp[i][j-ab[i][0]] + ab[i][1]
            dp[i+1][j] = max(dp[i][j],dp[i][j-ab[i][0]] + ab[i][1])
        #print(dp)
    #print(h,dp)

#print(ab)
#print(dp)


max_num = [0]*n

for i in reversed(list(range(n))):
    #print(i)
    if i == 0:
        break
    if max_num[i] < ab[i][1]:
        max_num[i-1] = ab[i][1]
    else:
        max_num[i-1] = max_num[i]

#print(max_num)
#print(ab[2272:2336])
#exit()

ans = 0
for i in range(n-1):
    #print(i)
    if ans < dp[i+1][t-1]+max_num[i]:
        ans = dp[i+1][t-1]+max_num[i]
        #print(i,ans,max_num[i],max_num[i+1],max_num[i-1])
    #ans = max(ans,)
    #print(max(ab[i:][1]))
    #print()
        
print(ans)
#print())
# Original solution
n,t = list(map(int,input().split()))

food = [[0,0] for i in range(n)]
for i in range(n):
  a,b = list(map(int,input().split()))
  food[i][0] = a
  food[i][1] = b


dp = [[-10000000 for i in range((n+1)*3000)] for j in range(n+1)]
dp[0][0] = 0


for i in range(n):
  a = food[i][0]
  b = food[i][1]
  for j in range(t):
    eat = dp[i][j]+b
    next_time = j+a
    # print(j,next_time)
    if dp[i+1][next_time] < eat:
      dp[i+1][next_time] = eat
    if dp[i+1][j] < dp[i][j]:
      dp[i+1][j] = dp[i][j]

# for i in range(n):
#   for j in range(10,21):
#     print(dp[i][j],end=" ")
#   print()
print((max(dp[-1])))

# Optimized solution
n,t = list(map(int,input().split()))
orders = []
for i in range(n):
    a,b = list(map(int,input().split()))
    orders.append([a,b])

orders.sort(key=lambda x:(x[0],-x[1]))
# print(orders)

dp = [[-1e10 for i in range(t+1)] for j in range(n+1)]
dp[0][0] = 0

for i,od in enumerate(orders):
    for j in range(t+1):
        dp[i+1][j] = dp[i][j]
    for j in range(t):
        nt = j+od[0]
        if nt > t-1:
            nt = t
        if dp[i+1][nt] < dp[i][j]+od[1]:
            dp[i+1][nt] = dp[i][j]+od[1]

# for l in dp:
#     print(l[:11])
# print(dp[-1])
print((max(dp[-1])))
# Original solution
n, t = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()

a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)

dp = [[0 for j in range(t+1)] for i in range(n+1)]
prev = [[(0, 0) for j in range(t+1)] for i in range(n+1)]

for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
                prev[i+1][j+a[i]] = (i, j)
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
            prev[i+1][j] = (i, j)

happy = dp[n][t-1]
i = n
j = t-1


used = set([])
while i > 0 or j > 0:
    pi, pj = prev[i][j]
    if dp[pi][pj] != dp[i][j]:
        used.add(pi)
    i = pi
    j = pj

unused = []
for i in range(n):
    if i not in used:
        unused.append(b[i])

if len(unused) == 0:
    ans = happy
else:
    ans = happy + max(unused)

print(ans)





# Optimized solution
n, t = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()

a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)

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

for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]

ans = 0

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

print(ans)
# Original solution
N, T = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]

items.sort()

ans = 0
dp = {0: 0}
for wi, vi in items:
    for w, v in list(dp.items()):
        if w < T:
            v2 = v + vi
            if v2 > ans:
                ans = v2

    for w, v in list(dp.items()):
        w2 = w + wi
        if w2 <= T:
            v2 = v + vi
            if w2 in dp:
                if v2 > dp[w2]:
                    dp[w2] = v2
            else:
                dp[w2] = v2

v2 = max(dp.values())
ans = max(ans, v2)

print(ans)


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

def solve():
    N, T = list(map(int, input().split()))
    items = [tuple(map(int, input().split())) for _ in range(N)]

    items.sort()

    capW = T-1
    dp = [0] * (capW+1)
    ans = 0
    for wi, vi in items:
        ans = max(ans, dp[-1]+vi)
        for w in reversed(list(range(wi, capW+1))):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0

    print(ans)


solve()
# Original solution
import heapq as hq



def resolve():
    (N,T)=(int(i) for i in input().split())

    dishes=[[int(i) for i in input().split()] for _ in range(N)]
    dishes.sort()
    dpt=[[-1 for i in range(T+1)] for _ in range(N+1)]
    vflg=[[False for i in range(T+1)] for _ in range(N+1)]
    dpt[0][0]=0
    q=[]
    hq.heappush(q,(0,0))

    while q:
        
        (ind,cost)=hq.heappop(q)

        if vflg[ind][cost]:
            continue
        vflg[ind][cost]=True
        if ind==N:
            break


        aft=min(cost+dishes[ind][0],T)
        sc=dpt[ind][cost]
        if dpt[ind+1][cost]<sc:
            dpt[ind+1][cost]=sc
            hq.heappush(q,(ind+1,cost))
        if cost==T:
            continue
        if dpt[ind+1][aft]<sc+dishes[ind][1]:
            dpt[ind+1][aft]=sc+dishes[ind][1]
            hq.heappush(q,(ind+1,aft))



    print((max(dpt[-1])))


if __name__ == "__main__":

    resolve()

# Optimized solution

def resolve():
    (N,T)=(int(i) for i in input().split())

    dishes=[[int(i) for i in input().split()] for _ in range(N)]
    dishes.sort()
    dpt=[[-1 for i in range(T+1)] for _ in range(N+1)]

    dpt[0][0]=0

    for i in range(N):
        for j in range(T):
            dpt[i+1][j]=max(dpt[i+1][j],dpt[i][j])
            dpt[i+1][min(T,j+dishes[i][0])]=max(dpt[i+1][min(T,j+dishes[i][0])],dpt[i][j]+dishes[i][1])
        dpt[i+1][T]=max(dpt[i+1][T],dpt[i][T])




    print((max(dpt[-1])))
#    for i in dpt:
#        print(i)

if __name__ == "__main__":
#    unittest.main()
    resolve()
# Original solution
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j])

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


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

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


if __name__ == '__main__':
    main()
# Original solution
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - A[i]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + B[i])
            else:
                dp1[i+1][j] = dp1[i][j]
    dp2 = [[0]*(T+1) for _ in range(N+2)]
    for i in range(1, N+1)[::-1]:
        for j in range(T):
            t = j - A[i-1]
            if 0 <= t:
                dp2[i][j] = max(dp2[i+1][j], dp2[i+1][t] + B[i-1])
            else:
                dp2[i][j] = dp2[i+1][j]
    ans = 0
    for i in range(N):
        for j in range(T):
            ans = max(ans, dp1[i][j] + dp2[i+2][T - 1 - j] + B[i])
    print(ans)


if __name__ == '__main__':
    main()


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

    ans = 0
    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - AB[i][0]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + AB[i][1])
            else:
                dp1[i+1][j] = dp1[i][j]
        ans = max(ans, dp1[i][T-1] + AB[i][1])
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
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)

# Optimized solution
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)
# Original solution
N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [-1] * (T + 3000)
dp[0] = 0
c = 0
for a, b in sorted(AB):
    for j in range(c, -1, -1):
        if dp[j] == -1:
            continue
        t = dp[j] + b
        if dp[j + a] < t:
            dp[j + a] = t
    c = min(c + a, T - 1)
print((max(dp)))


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

    dp = [-1] * (T + 3000)
    dp[0] = 0
    c = 0
    for a, b in sorted(AB):
        for j in range(c, -1, -1):
            if dp[j] == -1:
                continue
            t = dp[j] + b
            if dp[j + a] < t:
                dp[j + a] = t
        c = min(c + a, T - 1)
    print((max(dp)))


main()
# Original solution
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=[tuple(map(int,input().split()))for i in range(n)]

dp=[]
dp2=[]
for time,value in x:
    for k,v in list(d.copy().items()):
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in list(db.copy().items()):
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

# Optimized solution
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=sorted([tuple(map(int,input().split()))for i in range(n)],key=lambda xxx:xxx[0])
dp=[]
dp2=[]
for time,value in x:
    for k,v in list(d.copy().items()):
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in list(db.copy().items()):
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
# Original solution
N,T = list(map(int,input().split()))

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

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

for i,(a,b) in  enumerate(item,1):
    for t in reversed(list(range(T))):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)


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

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

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

for i,(a,b) in  enumerate(item,1):
    for t in reversed(list(range(T))):
        dist=min(T,t+a)
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)
# Original solution
#"""
import sys
input = sys.stdin.readline
#"""

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

dp = [[[0,[]] for _ in [0]*T] for _ in [0]*(N+1)]

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t][0] = dp[i][t][0]
        dp[i+1][t][1] = dp[i][t][1][:]
        if t-a>=0:
            if dp[i+1][t][0] < dp[i][t-a][0] + b:
                dp[i+1][t][0] = dp[i][t-a][0]+b
                dp[i+1][t][1] = dp[i][t-a][1][:]
                dp[i+1][t][1].append(i)

ans0 = dp[N][-1][0]
ans = ans0
s = set(dp[N][-1][1])
for i in range(N):
    if i in s:continue
    ans = max(ans,ans0+AB[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 [0]*N]

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

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t] = dp[i][t]
        if t-a>=0:
            dp[i+1][t] = max(dp[i+1][t],dp[i][t-a]+b)

s = []
t = T-1
for j in range(N-1,-1,-1):
    a,b = AB[j]
    while (dp[j+1][t] == dp[j+1][t-1]) and t>0:
        t -= 1
    if dp[j+1][t] == dp[j][t]:
        pass
    else:
        t -= a
        s.append(j)

ans0 = dp[N][-1]
ans = ans0
for i in range(N):
    if s and i==s[-1] :
        s.pop()
        continue
    ans = max(ans,ans0+AB[i][1])
print(ans)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,T=list(map(int,input().split()))
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=-INF
    for i in range(n):
        a,b=AB[i]
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print((max(ans,max(dp))))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,T=list(map(int,input().split()))
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=-INF
    for i in range(n):
        a,b=AB[i]
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print(ans)
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,T=list(map(int,input().split()))
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=-INF
    for i in range(n):
        a,b=AB[i]
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print(ans)
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,t=list(map(int,input().split()))
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    ans=0
    dp=[0]*t
    for a,b in AB:
        ans=max(ans,dp[-1]+b)
        ndp=dp[:]
        for i in range(t):
            if(i+a<t):
                ndp[i+a]=max(ndp[i+a],dp[i]+b)
        dp=ndp

    print(ans)
resolve()