CodeEff/ECCO huggingface dataset:
# Original solution
def main():
	_, t, *L = list(map(int, open(0).read().split()))
	d = [0] * (t + max(L[::2]))
	for w, v in sorted((x, y) for x, y in zip(*[iter(L)] * 2)):
		for i in range(t + w - 1, w - 1, -1):
			if d[i - w] + v > d[i]:
				d[i] = d[i - w] + v
	print((max(d)))

if __name__=="__main__":
	main()

#vs after contest

# Optimized solution
def main():
	_, t, *L = list(map(int, open(0).read().split()))
	d = [0] * t
	cand = 0
	for w, v in sorted((x, y) for x, y in zip(*[iter(L)] * 2)):
		if cand < d[-1] + v:
			cand = d[-1] + v
		for i in range(t - 1, w - 1, -1):
			if d[i - w] + v > d[i]:
				d[i] = d[i - w] + v
	print((max(cand, max(d))))

if __name__=="__main__":
	main()
# Original solution
def main():
    n, t = list(map(int, input().split()))
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0 for i in range(t)] for j in range(n + 1)]
    ls = [[[] for i in range(t)] for j in range(n + 1)]
    for i in range(n):
        for j in range(t):
            if j - f[i][0] >= 0 and dp[i][j - f[i][0]] + f[i][1] > dp[i][j]:
                dp[i + 1][j] = dp[i][j - f[i][0]] + f[i][1]
                ls[i + 1][j] = ls[i][j - f[i][0]] + [i]
            else:
                dp[i + 1][j] = dp[i][j]
                ls[i + 1][j] = ls[i][j][:]
    res = dp[n][t - 1]
    ff = [f[i][1] for i in range(n) if not i in ls[n][t - 1]]
    if ff:
        return res + max(ff)
    else:
        return res


print((main()))


# Optimized solution
def main():
    n, t = list(map(int, input().split()))
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = ls[j - f[i][0]] + [i]
    res = dp[t - 1]
    ff = [f[i][1] for i in range(n) if not i in ls[t - 1]]
    if ff:
        return res + max(ff)
    else:
        return res


print((main()))
# Original solution
import copy


def main():
    n, t = list(map(int, input().split()))
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = copy.copy(ls[j - f[i][0]]) + [i]
    res = dp[t - 1]
    ll = ls[t - 1]
    fff = [0 for _ in range(n)]
    for sll in ll:
        fff[sll] = 1
    ff = [f[i][1] for i in range(n) if fff[i] == 0]
    if ff:
        return res + max(ff)
    else:
        return res


print((main()))


# Optimized solution


def main():
    n, t = list(map(int, input().split()))
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

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

    return res




print((main()))
# Original solution
def solve():
  ans = 0
  N, T = list(map(int, input().split()))
  A = [list(map(int, input().split())) for _ in range(N)]
  A.sort()
  dp = [[0]*(T+A[-1][0]) for _ in range(N+1)]
  for i in range(1,N+1):
    for t in range(1,T+A[-1][0]):
      if t<A[i-1][0] or t>=T+A[i-1][0]:
        dp[i][t] = max(dp[i-1][t],dp[i][t-1])
      else:
        dp[i][t] = max([dp[i-1][t],dp[i][t-1],dp[i-1][t-A[i-1][0]]+A[i-1][1]])
  ans = max(dp[-1])
  return ans
print((solve()))

# Optimized solution
def solve():
  N, T = list(map(int, input().split()))
  A = [list(map(int, input().split())) for _ in range(N)] 
  A.sort()
  dp = [[0]*(T+1) for _ in range(N+1)]
  for i in range(N):
    for j in range(0,T+1):
      dp[i+1][j] = max(dp[i+1][j],dp[i][j])
      if j<T:
        t = min(T,j+A[i][0])
        dp[i+1][t] = max(dp[i+1][t],dp[i][j]+A[i][1])
  ans = dp[-1][-1]
  return ans
print((solve()))
# Original solution
import sys
input = sys.stdin.readline

N,T=list(map(int,input().split()))
D=[tuple(map(int,input().split())) for i in range(N)]

D.sort(key=lambda x:x[1],reverse=True)

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,x-1,-1):
        if DP[time][0]<DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time]=[DP[time-x][0]+y,DP[time-x][1]]

        elif DP[time][0]==DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time][1]=min(ind+1,DP[time][1])
            else:
                DP[time][1]=min(DP[time-x][1],DP[time][1])

    #print(DP)

D.append((0,0))
                
ANS=DP[-1][0]

for x,y in DP[:-1]:
    #if x==0:
    #    continue
    ANS=max(ANS,x+D[y][1])

print(ANS)
    


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

N,T=list(map(int,input().split()))
D=[tuple(map(int,input().split())) for i in range(N)]
D.sort()

DP=[0]*(T+1)
ANS=0

for i in range(N):
    a,b=D[i]

    for j in range(T,a-1,-1):
        DP[j]=max(DP[j-a]+b,DP[j])

    for j in range(i+1,N):
        ANS=max(ANS,DP[T-1]+D[j][1])

print(ANS)
# Original solution
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, T = list(map(int, input().split()))
    cv = [tuple(map(int, input().split())) for _ in range(N)]
    cv = sorted(cv, key=lambda x : x[0])

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

    values = [v for c, v in cv]
    max_values = [max(values[i:]) for i in range(N)]
    # 貰うdp
    for i in range(N):
        cost, value = cv[i]
        for now in range(cost, T+1):
            old = now - cost
            dp[i+1][now] = max(dp[i][now], dp[i][old] + value)

        for j in range(1, T+1):
            dp[i+1][j] = max(dp[i+1][j], dp[i+1][j-1])
        
        for j in range(1, T+1):
            dp_ext[i+1][j] = max(dp[i+1][j], dp[i][j-1] + max_values[i], dp_ext[i][j])

    print((dp_ext[N][T]))

if __name__ == "__main__":
    main()

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N, T = list(map(int, input().split()))
    cv = [tuple(map(int, input().split())) for _ in range(N)]
    cv = sorted(cv, key=lambda x : x[0])
    dp = [[0]*(T+1) for _ in range(N+1)]

    # 貰うdp

    ans = 0
    for i in range(N):
        cost, value = cv[i]
        for now in range(min(T+1, cost)):
            dp[i+1][now] = dp[i][now]

        for now in range(cost, T+1):
            old = now - cost
            dp[i+1][now] = max(dp[i][now], dp[i][old] + value)
        
        ans = max(ans, dp[i][T-1] + value)

    print(ans)

if __name__ == "__main__":
    main()
# Original solution
def knapsack(n, w, info):
  dp = [[0]*(w + 1) for i in range(n + 1)]

  for i in range(n):
    for j in range(w + 1):
      weight, value = info[i]
      if j < weight:
        dp[i + 1][j] = dp[i][j]
      else:
        dp[i + 1][j] = max(dp[i][j], dp[i][j - weight] + value)
  return dp

N,T = list(map(int,input().split()))
food = []
for _ in range(N):
  food.append(list(map(int,input().split())))
food.sort(key= lambda x: x[0])
dp = knapsack(N,T,food)

C = [0]*(N+1)
for i in range(N)[::-1]:
  C[i] = max(C[i+1], food[i][1])

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

print(ans)


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

foods.sort(key=lambda x: x[0])

# dp[i][j] = 1～i 番目の料理で j 分以内に完食できる美味しさの合計の最大値
dp = [ [0]*(T+1) for _ in range(N+1) ]

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

# for d in dp:
#   print(d)

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

print((max(ans, dp[-1][-1])))
# Original solution
import sys

N, T = list(map(int, input().split()))
S = sys.stdin.readlines()
A = []
B = []
for s in S:
    a, b = list(map(int, s.split()))
    A.append(a)
    B.append(b)

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

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

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

print(ans)


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

for i in range(N):
    A, B = D[i]
    for j in range(T):
        here = dp[i][j]
        if j < A:
            dp[i + 1][j] = here
        else:
            dp[i + 1][j] = max(here, dp[i][j - A] + B)

maxB = [0] * (N + 1)
t = 0
for i in range(N - 1, -1, -1):
    t = max(t, D[i][1])
    maxB[i] = t

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

print(ans)
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ab.sort()
    dp = [0] * t
    mt = 0
    for a, b in ab:
        mt = max(mt, dp[-1] + b)
        for i in range(t - a - 1, -1, -1):
            dp[i+a] = max(dp[i+a], dp[i] + b)
    print(mt)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = [list(map(int, readline().split())) for _ in range(n)]
    ab.sort()
    dp = [0] * t
    mt = 0
    for a, b in ab:
        mt = max(mt, dp[-1] + b)
        for i in range(t - a - 1, -1, -1):
            dp[i+a] = max(dp[i+a], dp[i] + b)
    print(mt)


if __name__ == '__main__':
    solve()
# Original solution
N,T = list(map(int,input().split()))
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = [{0:0} for i in range(N+1)]
dp1 = [{0:0} for i in range(N+1)]

for i,(a,b) in enumerate(AB):
    for k0,v0 in list(dp0[i].items()):
        if k0 in dp0[i+1]:
            dp0[i+1][k0] = max(dp0[i+1][k0], v0)
        else:
            dp0[i+1][k0] = v0
        if k0+a < T:
            if k0+a in dp0[i+1]:
                dp0[i+1][k0+a] = max(dp0[i+1][k0+a], v0+b)
            else:
                dp0[i+1][k0+a] = v0+b
        if k0 in dp1[i+1]:
            dp1[i+1][k0] = max(dp1[i+1][k0], v0+b)
        else:
            dp1[i+1][k0] = v0+b
    for k1,v1 in list(dp1[i].items()):
        if k1 in dp1[i+1]:
            dp1[i+1][k1] = max(dp1[i+1][k1], v1)
        else:
            dp1[i+1][k1] = v1
        if k1+a < T:
            if k1+a in dp1[i+1]:
                dp1[i+1][k1+a] = max(dp1[i+1][k1+a], v1+b)
            else:
                dp1[i+1][k1+a] = v1+b

print((max(dp1[-1].values())))

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

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in list(dp0.items()):
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in list(dp1.items()):
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print((max(dp1.values())))
# 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 _ in range(t)] for _ 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)


# Optimized solution
#ABC145 E
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)] for _ in range(n+1)]
# i番目より前まで注文してT分以内(max T-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]

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(n):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)
# Original solution
#ABC145 E
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)] for _ in range(n+1)]
# i番目より前まで注文してT分以内(max T-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]

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(n):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)


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

dp = [[0]*T for _ in range(N+1)]
# i番目より前まで注文してT分以内(max T-1)で完食する
def chmax(a,b):
    if a < b:
        return b
    else:
        return a 
    
for i in range(N):
    for t in range(T): #T-1分がmax
        if t+ab[i][0] <= T-1:
        	dp[i+1][t+ab[i][0]] =chmax(dp[i+1][t+ab[i][0]],dp[i][t]+ab[i][1])
        
        dp[i+1][t] = chmax(dp[i+1][t],dp[i][t])

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(N):
    ans = chmax(ans,dp[i][T-1]+ab[i][1])
    
print(ans)
# Original solution
N,T = list(map(int,input().split()))

A =[list(map(int,input().split())) for i in range(N)]

A.sort(key = lambda x:x[0])

INF = float("inf")

DP = [[-INF]*(T+3001) for i in range(N+1)]

DP[0][0] = 0

for i in range(N):
    for j in range(T):
        DP[i+1][j] = max(DP[i+1][j],DP[i][j])
        DP[i+1][j+A[i][0]] = max(DP[i+1][j+A[i][0]],DP[i][j+A[i][0]],DP[i][j]+A[i][1])
score = 0
for i in range(N):
    for j in range(T+A[i][0]):
        score = max(DP[i+1][j],score)

print(score)

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

A =[list(map(int,input().split())) for i in range(N)]

A.sort(key = lambda x:x[0])

INF = float("inf")

DP = [[-INF]*(T+3001) for i in range(N+1)]

DP[0][0] = 0

for i in range(N):
    for j in range(T):
        DP[i+1][j] = max(DP[i+1][j],DP[i][j])
        DP[i+1][j+A[i][0]] = max(DP[i+1][j+A[i][0]],DP[i][j+A[i][0]],DP[i][j]+A[i][1])
score = 0
for i in range(N):
    for j in range(T+A[i][0]):
        score = DP[i+1][j] if DP[i+1][j]>score else score

print(score)
# Original solution
n, W = list(map(int, input().split()))
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(list(range(W))):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print((max(dp)))


# Optimized solution
n, W = list(map(int, input().split()))
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort()

dp = [[0]*W for _ in range(n+1)]
for i in range(1, n+1):
    w, v = ab[i-1]
    for j in range(W):
        if dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]

        if 0 <= j-w and dp[i][j] < dp[i-1][j-w]+v:
            dp[i][j] = dp[i-1][j-w]+v


ans = 0
for i in range(n):
    a, b = ab[i]
    if ans < dp[i][W-1]+b:
        ans = dp[i][W-1]+b
print(ans)
# Original solution
n, t = list(map(int, input().split()))
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3000)] for _ in range(3000)]
ans = 0

for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

# Optimized solution
n, t = list(map(int, input().split()))
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3005)] for _ in range(3005)]

ans = 0
for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    N, T = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: (x[0], x[1]))
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)

    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    ab.sort(key=lambda x: x[1])
    tmp = ab.pop()
    dp = [-1 for i in range(T)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, 0, -1):
            if i >= a:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)

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

    # print(dp)
    print(ans)


main()


# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    N, T = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[0])
    t = ab[-1][0]
    dp = [-1 for i in range(T+t + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T+t, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)

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

    # print(dp)
    print(ans)


main()
# Original solution
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(eval(input()))


def sinput():
    return input().split()


def intsput():
    return list(map(int, sinput()))


dishes = []
n, t = intsput()
for _ in range(n):
    dishes.append(list(intsput()))
    dishes[-1].append(dishes[-1][1] / dishes[-1][0])

maxweight = max([x[0] for x in dishes])

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

for i in range(1, n + 1):
    for j in range(t):
        if dishes[i - 1][0] > j:
            dp[i][j] = dp[i - 1][j][:]
        else:
            val = max(dp[i - 1][j][0], dp[i - 1][j - dishes[i - 1][0]][0] + dishes[i - 1][1])
            dp[i][j] = [val]
            if val == dp[i - 1][j][0]:
                dp[i][j].append(dp[i - 1][j][1])
            else:
                dp[i][j].append(dp[i - 1][j - dishes[i - 1][0]][1] + [i])

rslt = dp[n][t - 1]

op = []
for i in range(1, n + 1):
    if i not in rslt[1]:
        op.append(i)

if op:
    vv = max([dishes[i - 1][1] for i in op])
else:
    vv = 0

print((rslt[0] + vv))


# Optimized solution
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(eval(input()))


def sinput():
    return input().split()


def intsput():
    return list(map(int, sinput()))


dishes = []
n, t = intsput()
for _ in range(n):
    dishes.append(list(intsput()))
    dishes[-1].append(dishes[-1][1] / dishes[-1][0])

maxweight = max([x[0] for x in dishes])
dishes.sort(key=lambda x: x[1], reverse=True)

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

for i in range(1, n + 1):
    for j in range(t):
        if dishes[i - 1][0] > j:
            dp[i][j] = dp[i - 1][j][:]
        else:
            val = max(dp[i - 1][j][0], dp[i - 1][j - dishes[i - 1][0]][0] + dishes[i - 1][1])
            dp[i][j] = [val]
            if val == dp[i - 1][j][0]:
                dp[i][j].append(dp[i - 1][j][1])
            else:
                if i == dp[i - 1][j - dishes[i - 1][0]][1]:
                    dp[i][j].append(i + 1)
                else:
                    dp[i][j].append(dp[i - 1][j - dishes[i - 1][0]][1])

rslt = dp[n][t - 1]

if rslt[1] <= n:
    vv = dishes[rslt[1] - 1][1]
else:
    vv = 0
print((rslt[0] + vv))
# Original solution
I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    dp_new = dp[:]
    for k in range(T):
        if dp[k] == -1:
            continue
        dp_new[k + a] = max(dp[k + a], dp[k] + b)
    dp = dp_new
print((max(dp)))


# Optimized solution
I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    for k in range(T - 1, -1, -1):
        if dp[k] == -1:
            continue
        dp[k + a] = max(dp[k + a], dp[k] + b)
print((max(dp)))
# Original solution
from operator import itemgetter

N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [dict() for _ in range(N)]
for i in range(T):
    dp[0][i] = 0

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = max(dp[i][T-1] + add_value, dp[i-1][T])
print((dp[-1][T]))


# Optimized solution
from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)