Takahashi is at an all-you-can-eat restaurant.
The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i-th dish, whose deliciousness is B_i.
The restaurant has the following rules:
 - You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.
 - You cannot order the same kind of dish more than once.
 - Until you finish eating the dish already served, you cannot order a new dish.
 - After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.
Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.
What is the maximum possible happiness achieved by making optimal choices?

-----Constraints-----
 - 2 \leq N \leq 3000
 - 1 \leq T \leq 3000
 - 1 \leq A_i \leq 3000
 - 1 \leq B_i \leq 3000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N T
A_1 B_1
:
A_N B_N

-----Output-----
Print the maximum possible happiness Takahashi can achieve.

-----Sample Input-----
2 60
10 10
100 100

-----Sample Output-----
110

By ordering the first and second dishes in this order, Takahashi's happiness will be 110.
Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.

Difficulty: interview

Starter code:

Solutions:
import numpy as np
 
N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()
data = np.array(data)

dp = np.zeros(T)
ans = 0
for a, b in data:
    ans = max(ans,dp[-1]+b)
    if a< T:
        newtable = dp[:T-a] + b
        dp[a:] = np.maximum(dp[a:], newtable)

print(int(ans))

import numpy as np
n,t = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
dp = np.array([0]*t)
ans = 0
for a,b in l:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[a:],dp[:-a]+b)
    
    
print(max(ans,dp[-1]))

import numpy as np

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
# dp は0からT-1まで
dp = np.zeros(T, dtype=np.int32)
temp_ans = 0
for a, b in AB:
    temp_ans = max(temp_ans, dp.max() + b)
    dp[a:] = np.maximum(dp[a:], dp[:-a]+b)
print(temp_ans) 


from numpy import zeros, maximum

N, T, *AB = list(map(int, open(0).read().split()))

dp = zeros(6010, int)
for w, v in sorted(zip(*[iter(AB)] * 2)):
    dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)

print((dp.max()))


from numpy import*
N,T,*L=map(int,open(0).read().split())
d=zeros(6010,int)
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

import numpy as np
 
N,T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(AB)

dp = np.zeros(T,np.int64)  
ans = 0
for a, b in AB:
    ans = max(ans, dp.max() + b)
    np.maximum(dp[a:], dp[:-a] + b, out=dp[a:])
print(ans)

def main():
    import numpy as np
    n,t=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(n)]
    F.sort(key=lambda x:x[0])

    dp=np.zeros([n+1,t],dtype=np.int64)
    for i in range(n):
        a1=F[i][0]
        b1=F[i][1]
        dp[i+1][:a1]=dp[i][:a1]
        dp[i+1][a1:]=np.maximum(dp[i][a1:],dp[i][:-a1]+b1)
    
    ans=0
    for i in range(n):
        ans=max(ans,dp[i][-1]+F[i][1])
    print(ans)
         
def __starting_point():
    main()
__starting_point()

import sys

import numpy as np

n, t = map(int, input().split())
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)

print(max(tmp_ans, knapsack.max()))

n,t=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda x:x[0])
import numpy as np
ans=0
dp=np.zeros(t,np.int64)
# dp[i]:時間合計i以内に食べれる料理のおいしさ総和の最大
for i in range(n):
  a,b=ab[i]
  ans=max(ans,dp[-1]+b)
  dp[a:]=np.maximum(dp[a:],dp[:-a]+b)
print(ans)


import numpy as np
 
n, t = map(int, input().split())
a = []
b = []

for _ in range(n):
  a_tmp, b_tmp = map(int, input().split())
  a.append(a_tmp)
  b.append(b_tmp)
    
arg = np.argsort(a)
a = np.array(a)[arg]
b = np.array(b)[arg]
dp = np.zeros((n, t), dtype=np.int)
    
for i in range(n - 1):
  dp[i+1, :a[i]] = dp[i, :a[i]]
  dp[i+1, a[i]:] = np.maximum(dp[i, a[i]:], dp[i, :-a[i]] + b[i])
  
print(np.max(dp[:, -1] + b))

from numpy import zeros, maximum, array

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

    dp = zeros(T + max(AB[::2]), int)
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)

    print((dp.max()))

main()


import numpy as np
n,t = list(map(int, input().split()))
item = [None]*n
ans = 0
dp = np.zeros(t, dtype=int)

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

for i in range(n):
    a,b = item[i]
    ans = max(ans, dp.max()+b)
    dp[a:] = np.maximum(dp[a:], dp[:-a]+b)

print(ans)


import numpy as np


def solve():


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

    A = []
    B = []

    for _ in range(N):
        A_temp, B_temp = list(map(int, input().split()))
        A.append(A_temp)
        B.append(B_temp)

    A = np.array(A, np.int)
    B = np.array(B, np.int)

    idx = np.argsort(A)
    A = A[idx]
    B = B[idx]

    dp = np.zeros((N, T), np.int)

    for i in range(N - 1):
        dp[i + 1, :A[i]] = dp[i, :A[i]]
        dp[i + 1, A[i]:] = np.maximum(dp[i, A[i]:], dp[i, :-A[i]] + B[i])

    print((np.max(dp[:, -1] + B)))


def __starting_point():
    solve()

__starting_point()

import sys
import numpy as np

n, t = list(map(int, input().split()))
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)
print(tmp_ans)


def main():
  e=enumerate
  (n,t),*g=[list(map(int,t.split()))for t in open(0)]
  d=[0]
  g.sort()
  dp=[]
  d=[0]*t
  for a,b in g:
    p=d[:]
    for i in range(a,t):
      v=d[i-a]+b
      if v>p[i]:p[i]=v
    dp+=p,
    d=p
  a=m=0
  for(*_,v),(_,w)in zip(dp[-2::-1],g[::-1]):
    if w>m:m=w
    if v+m>a:a=v+m
  print(a)
main()

import numpy as np
n, t = map(int, input().split())
lst = np.full((t), -float("inf"))
lst[0] = 0
ans = 0
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
for a, b in ab:
    ans = max(ans, max(lst) + b)
    if a < t:
        lst[a:] = np.maximum(lst[a:], lst[:-a] + b)
ans = int(ans)
print(ans)

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()


import numpy as np

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

dp = np.zeros(T, dtype=int)
ans = 0
for i, (a, b) in enumerate(C):
    ans = max(ans, dp[T - 1] + b)
    new_dp = dp.copy()
    new_dp[a:] = np.maximum(dp[a:], dp[:-a] + b)
    dp = new_dp
print(ans)


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()


from numpy import*
N,T,*L=int64(open(0).read().split())
d=zeros(6010,int)
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

import sys
input = sys.stdin.readline
read = sys.stdin.read
import numpy as np

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = np.zeros((n+1, t), dtype=np.int64)
for i, (a, b) in enumerate(AB):
  np.maximum(dp[i, a:], dp[i, :-a]+b, out=dp[i+1, a:])
maxB = np.maximum.accumulate(B[::-1])[::-1]
ans = (dp[1:-1, -1]+maxB[1:]).max()
print(ans)

import numpy as np
N, T = map(int, input().split())

menu = []
for _ in range(N):
    m = tuple(map(int, input().split()))
    menu.append(m)
menu = sorted(menu, key=lambda m: m[0])

# 料理i-1をj-1分までに完食するときの満足度最大値
dp = np.zeros((N, T), dtype='int64')
anss = []

for i in range(1, N):
    # 一つまえのメニューについて
    ai, bi = menu[i-1]
    dp[i][:ai] = dp[i-1][:ai]  # 時間が足りないので注文しない
    dp[i][ai:] = np.fmax(
        dp[i-1][ai:], # 何も注文しない
        dp[i-1][:-ai] + bi # 注文した場合, ai分かかっても大丈夫な範囲から取得
    )
    # 加えて自身を最後に食べた場合を記録
    anss.append(dp[i][-1] + menu[i][1])

print(max(anss))

from numpy import*
N,T,*AB=map(int,open(0).read().split())
dp=zeros(6010,int)
for w,v in sorted(zip(*[iter(AB)]*2)):dp[w:T+w]=maximum(dp[w:T+w],dp[:T]+v)
print(max(dp))

import sys

import numpy as np

n, t = list(map(int, input().split()))
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)

print((max(tmp_ans, knapsack.max())))


import numpy as np
n,t = map(int, input().split())
DP = np.full((t), -float("inf"))
DP[0] = 0
ans = 0
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
for a,b in ab:
    ans = max(ans, max(DP)+b)
    if a<t:
        DP[a:] = np.maximum(DP[a:], DP[:-a]+b)

ans = int(ans)
print(ans)

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, T = lr()
AB = [lr() for _ in range(N)]
AB.sort()
# 時間のかかる物は後ろへ
dp = np.zeros(T, np.int64)
answer = 0
for a, b in AB:
    answer = max(answer, dp.max() + b)
    prev = dp
    dp[a:] = np.maximum(prev[a:], prev[:-a] + b)

print(answer)


import numpy as np

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

dp = np.zeros((N+1, 2, T), np.int64)
for i, (A, B) in enumerate(ABs):
    dp[i+1] = dp[i]
    dp[i+1, 1] = np.maximum(dp[i, 0] + B, dp[i+1, 1])
    dp[i+1, :, A:] = np.maximum(dp[i, :, :-A] + B, dp[i+1, :, A:])

print(np.max(dp[N]))

def main():
    N, T = list(map(int, input().split()))
    ab = [tuple(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[0])
    t = ab[-1][0]
    dp = [-1]*(T+t+1)
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, -1, -1):
            if dp[i] < 0:
                continue
            if dp[i+a] < dp[i]+b:
                dp[i+a] = dp[i]+b
    ans = max(dp)
    print(ans)
main()


import sys
import numpy as np
input = sys.stdin.readline

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

ab.sort(key=lambda x:(x[0], -x[1]))

dp = np.array([0]*t)
ans = 0

for a, b in ab:
    ans = max(ans, dp[-1] + b)
    dp[a:] = np.maximum(dp[:-a]+b, dp[a:])
print(max(ans, dp[-1]))

def knapsack_DP(N, W, weight, value):
    import numpy as np
    dishes = [(weight[i], value[i]) for i in range(N)]
    dishes = sorted(dishes, key=lambda x: x[0])
    dp = np.zeros(W, dtype=int)
    ans=0
    for w, v in dishes:
        ans=max(dp[-1]+v, ans)
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) 
    return ans

def __starting_point():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    print(knapsack_DP(N, W, weight, value))
__starting_point()

import numpy as np

n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()
dp = np.array([0]*t)
ans = 0
for a,b in ab:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[:-a]+b,dp[a:])
# print(dp,ans)
print(max(ans,dp[-1]))

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,T = MI()
	max_T = -1
	dish = []
	for i in range(N):
		A,B = MI()
		dish.append([A,B])
		dish.sort(key=lambda x : x[0])
		max_T = max(max_T, A)

	dp=np.array([-1 for _ in range(T+max_T)])
	dp[0] = 0
	upper = 1
	for i in range(N):
		ch = (dp>=0)
		ch[T:] = False
		ch2 = np.roll(ch, dish[i][0])
		ch2[:dish[i][0]]=False
		dp[ch2] = np.maximum(dp[ch2] , dp[ch] + dish[i][1])
	print(max(dp))
main()

import numpy as np

n, t = map(int, input().split())
a = []
b = []
for _ in range(n):
  a_tmp, b_tmp = map(int, input().split())
  a.append(a_tmp)
  b.append(b_tmp)
arg = np.argsort(a)
a = np.array(a)[arg]
b = np.array(b)[arg]
dp = np.zeros((n, t), dtype=np.int)
for i in range(n - 1):
  dp[i+1, :a[i]] = dp[i, :a[i]]
  dp[i+1, a[i]:] = np.maximum(dp[i, a[i]:], dp[i, :-a[i]] + b[i])
  
print(np.max(dp[:, -1] + b))

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, T = lr()
AB = [lr() for _ in range(N)]
AB.sort()
# 最後の注文はAiが選ぶ料理で最大で、T-1分後に注文するとして良い
dp = np.zeros(T, np.int32)
temp_ans = 0
for a, b in AB:
    temp_ans = max(temp_ans, dp.max()+b)
    dp[a:] = np.maximum(dp[a:], dp[:-a]+b)

print(temp_ans)


import numpy as np

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

AB.sort()

ans = 0
dp = [0] * T
dp = np.zeros(T, int)

for a, b in AB:
    ans = max(ans, dp[-1] + b)
    dp[a:] = np.maximum(dp[a:], dp[:-a] + b)
    # for j in reversed(range(a, T)):
    #     dp[j] = max(dp[j], dp[j-a] + b)

print(ans)


import sys
import numpy as np
input = sys.stdin.readline

_n, _t = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(_n)]
AB.sort()


def dp(t, ablist):
    ans = 0
    table = np.zeros(t, int)
    for a, b in ablist:
        ans = max(ans, max(table) + b)
        np.maximum(table[:-a] + b, table[a:], out=table[a:])

    return ans


print((dp(_t, AB)))


import numpy as np
N,T = map(int,input().split())

meals = [tuple(map(int,input().split())) for _ in range(N)]

# dp1[t]: i番目の料理まででt分以内に食べれるものの美味しさ
# dp2[t]: i番目の料理まででt分以内に食べれるものの美味しさ (最後に食べる用のを選んだ仮定)

dp1 = np.zeros(T,dtype=int)
dp2 = np.zeros(T,dtype=int)

for a,b in meals:
    ndp1 = dp1.copy()
    ndp1[a:] = np.maximum(dp1[a:],dp1[:-a]+b)

    ndp2 = dp2.copy()
    ndp2[a:] = np.maximum(dp2[a:],dp2[:-a]+b)
    ndp2 = np.maximum(ndp2,dp1+b)
    dp1,dp2 = ndp1,ndp2

print(ndp2[-1])

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


def knapsack(ab):
    dp = np.zeros(T, dtype=np.int64)
    res = [dp]
    for a, b in ab:
        newDP = res[-1].copy()
        newDP[a:] = np.maximum(newDP[a:], newDP[:-a] + b)
        res.append(newDP)
    return res


dp1 = knapsack(AB)
dp2 = knapsack(AB[::-1])
dp2 = dp2[::-1]

ans = 0

for i in range(N):
    _, b = AB[i]
    l = dp1[i]
    r = dp2[i + 1][::-1]
    tmp = (l + r).max() + b
    ans = max(ans, tmp)
print(ans)


# https://codeforces.com/blog/entry/71482
# https://atcoder.jp/contests/abc145/submissions/8473167

import numpy
n, t = map(int, input().split())
time = []
for i in range(n):
    x, y = map(int, input().split())
    time.append((x, y))


dp = numpy.zeros(t, dtype=int)
time.sort()
ans = 0
for a, b in time:
    ans = max(ans, dp[-1]+b)
    dp[a:] = numpy.maximum(dp[a:], dp[:-a]+b)

print(ans)

import numpy as np
N,T = map(int,input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
AB.sort(key=lambda x:(x[0],-x[-1]))
dp = np.array([0]*T)
ans = 0
for a,b in AB:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[:-a]+b,dp[a:])
print(max(ans,dp[-1]))

import numpy as np

N,T = map(int, input().split())
item = [None]*N
for i in range(N):
  w,v = map(int,input().split())
  item[i] = [w,v]
item.sort(key=lambda x:x[0])

dp = np.zeros(T, dtype=int)
ans=0
for i in range(N):
    w,v=item[i]
    ans=max(ans,dp.max()+v)
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
print(ans)

import numpy as np

N, T = map(int, input().split())

A = []
B = []

for _ in range(N):
    A_temp, B_temp = map(int,input().split())
    A.append(A_temp)
    B.append(B_temp)

A = np.array(A, np.int)
B = np.array(B, np.int)

idx = np.argsort(A)
A = A[idx]
B = B[idx]

dp = np.zeros((N, T), np.int)

for i in range(N - 1):
    dp[i+1, :A[i]] = dp[i, :A[i]]
    dp[i+1, A[i]:] = np.maximum(dp[i, A[i]:], dp[i, :-A[i]] + B[i])

print(np.max(dp[:, -1] + B))

import numpy as np
N, T = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for n in range(N)]
AB.sort()

dp = np.zeros(T, dtype=int)
ans = 0
for a, b in AB:
    ans = max(ans, dp[-1]+b)
    np.maximum(dp[a:], dp[:-a]+b, out=dp[a:])
print(ans)


import numpy as np
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, t = map(int, input().split())
    dp = np.zeros(t,dtype=int)
    food = []
    for _ in range(n):
        a, b = map(int, input().split())
        food.append([a, b])
    food.sort(key=lambda x: x[0]*-1)
    for j in range(n):
        a, b = food[j][0], food[j][1]
        a=min(a,t)
        dptmp=np.zeros(t,dtype=int)
        dptmp[a:] = np.maximum(dp[a:],dp[:-a]+b)
        dptmp[:a] = np.maximum(np.full(a,b,dtype=int), dp[:a])
        dp=dptmp
    print(dp[-1])


def __starting_point():
    main()
__starting_point()

def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    N, T = map(int, f_i.readline().split())
    AB = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    AB.sort()
    max_Ai = AB[-1][0]
    
    dp = [[0] * T for i in range(N + 1)]
    dp = np.zeros(max_Ai + T, dtype=int)
    
    
    for A_i, B_i in AB:
        dp[A_i:A_i+T] = np.maximum(dp[A_i:A_i+T], dp[:T] + B_i)
    
    print(max(dp))

solve()

from numpy import zeros, maximum, int32

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

    dp = zeros(6010, int32)
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)

    print((dp.max()))

main()


import numpy as np

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

ab.sort()

dp = np.zeros(t, dtype=np.int64)

ans = 0
for a, b in ab:
    ans = max(ans, dp[-1] + b)
    np.maximum(dp[a:], dp[:-a] + b, out=dp[a:])


print(ans)


import numpy as np


def solve():
    N, T = map(int, input().split())
    ab_l = [[0, 0] for _ in range(N)]
    for i in range(N):
        ab_l[i][0], ab_l[i][1] = map(int, input().split())
    ab_l.sort()
    dp = np.zeros(T, dtype=int)
    ans = 0

    for a, b in ab_l:
        ans = max(ans, dp[-1] + b)
        dp[a:] = np.maximum(dp[a:], dp[:-a]+b)

    print(ans)


def __starting_point():
    solve()
__starting_point()

import numpy as np
 
N,T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(AB)

can_add = [0]*N
for n in range(N-1, 0, -1):
  x = can_add[n]
  y = AB[n][1]
  can_add[n-1] = x if x>y else y

dp = np.zeros(T,np.int64)  
ans = 0
for i, (a,b) in enumerate(AB):
  np.maximum(dp[a:], dp[:-a].copy()+b, out=dp[a:])
  x = dp.max() + can_add[i]
  if ans < x:
    ans = x
print(ans)     

import numpy as np
def main():
    n, t = map(int, input().split())
    dt = [list(map(int, input().split())) for _ in range(n)]
    dt.sort()
    dp = np.zeros(t, dtype=int)
    ans = 0
    for a, b in dt:
        ans = max(ans, dp[-1]+b)
        np.maximum(dp[a:], dp[:-a]+b, out=dp[a:])
    print(ans)

def __starting_point():
    main()
__starting_point()

def solve():
    from sys import stdin
    f_i = stdin
    
    N, T = map(int, f_i.readline().split())
    AB = [tuple(map(int, f_i.readline().split())) for i in range(N)]
    AB.sort()
    
    dp = [[0] * T for i in range(N + 1)]
    
    for i, AB_i in enumerate(AB, start=1):
        A_i, B_i = AB_i
        dp_i = dp[i]
        dp_pre = dp[i-1]
        dp_i[:A_i] = dp_pre[:A_i]
        for j, t in enumerate(zip(dp_pre[A_i:], dp_pre), start=A_i):
            x, y = t
            if x < y + B_i:
                dp_i[j] = y + B_i
            else:
                dp_i[j] = x
    
    ans = max(dp[k][-1] + AB[k][1] for k in range(N))
    print(ans)

solve()

N,T=map(int,input().split())
import numpy as np
dp=np.zeros(T,dtype=int)
maxval=0

meals=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  meals[i]=a,b

meals=sorted(meals,key=lambda x:x[0])

for i in range(N):
  a,b=meals[i]
  if maxval<dp[-1]+b:
    maxval=dp[-1]+b
  np.maximum(dp[:-a]+b,dp[a:],out=dp[a:])
  
print(maxval)

import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

# ・最適解をとってみる
# ・最適解に仮定できる構造を探す
# ・探索空間が小さくなったら、既知の手法に当てはまる（dpなど）

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

FOOD.sort()
dp = np.array([np.zeros(T + 1, dtype=np.int64) for _ in range(N + 1)])
ans = 0
for i in range(N):
    a, b = FOOD[i]
    dp[i + 1][a:] = np.maximum(dp[i][:-a] + b, dp[i][a:])

    # if len(dp[i][-a+1:T]) > 0:
    # dp[i + 1][T] = max(dp[i + 1][T], max(dp[i][-a+1:T]) + b)
    now = 0
    if i != N-1:
        now = dp[i + 1][T - 1] + max(FOOD[i + 1:], key=lambda x: x[1])[1]
        #print(FOOD[i + 1:])
        #print(max(FOOD[i + 1:], key=lambda x: x[1])[1])
        #print(now)

    ans = max(ans, now)

    # print(dp[i+1])

print(ans)


from numpy import zeros, maximum

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

    dp = zeros(6010, int)
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)

    print((dp.max()))

main()


N,T = map(int,input().split())
import numpy as np
A,B = np.array([list(map(int,input().split())) for _ in range(N)]).T
dp1 = np.array([[0]*T for _ in range(N+1)])
rev_A,rev_B = A[::-1],B[::-1]
dp2 = np.array([[0]*T for _ in range(N+1)])


for i in range(1,N+1):
  a = A[i-1]
  rev_a = rev_A[i-1]
  b = B[i-1]
  rev_b = rev_B[i-1]
  
  dp1[i,:a] = dp1[i-1,:a]
  dp2[i,:rev_a] = dp2[i-1,:rev_a]
  dp1[i,a:] = np.fmax(dp1[i-1,a:],dp1[i-1,:-a]+b)
  dp2[i,rev_a:] = np.fmax(dp2[i-1,rev_a:],dp2[i-1,:-rev_a]+rev_b)

      
lis = [0]*N
for i in range(1,N+1):
  lis[i-1] = (np.max(dp1[i-1]+dp2[N-i][::-1]) + B[i-1])
 
    
print(max(lis))

import numpy as np


def __starting_point():
    # input
    N, T = list(map(int,input().split()))
    menu = list()
    for i in range(N):
        menu_i = tuple(map(int,input().split()))
        menu.append(menu_i)
    menu.sort()
    dp = np.zeros(T, int)
    ans = 0
    # print(N,T,menu)

    for ab in menu:
        # print(ab[0],ab[1])
        ans = max(ans, dp[-1]+ab[1])
        dp[ab[0]:] = np.maximum(dp[ab[0]:], dp[:-ab[0]] + ab[1])
    print(ans)

__starting_point()

import sys
import numpy as np
input = sys.stdin.readline

_n, _t = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(_n)]
AB.sort()

ans = 0
table = np.zeros(_t, int)
for a, b in AB:
    ans = max(ans, max(table) + b)
    np.maximum(table[:-a] + b, table[a:], out=table[a:])


print(ans)


# -*- coding: utf-8 -*-

import sys
import numpy as np
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, T = MAP()
AB = []
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

# 各料理を時間の昇順でソート
AB.sort(key=itemgetter(1), reverse=True)
AB.sort(key=itemgetter(0))

# 後は普通のナップザック
TMAX = 6007
dp = np.zeros((N+1, TMAX), dtype=np.int64)
for i in range(N):
    a, b = AB[i]
    dp[i+1] = dp[i]
    dp[i+1,a:a+T] = np.maximum(dp[i+1,a:a+T], dp[i,:T] + b)
print((dp[N].max()))


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

#output
import numpy as np
A = np.array(A, np.int)
B = np.array(B, np.int)

idx = np.argsort(A)

A = A[idx]
B = B[idx]

dp = np.zeros((N, T), np.int)
#dp[品物][時間]

for i in range(N-1):
    dp[i+1, :A[i]] = dp[i, :A[i]]
    dp[i+1, A[i]:] = np.maximum(dp[i, A[i]:], dp[i, :-A[i]]+B[i])

print(np.max(dp[:, -1] + B))

import numpy as np

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

ab.sort()

dp = np.zeros(t, dtype=np.int64)

ans = 0
for a, b in ab:
    ans = max(ans, dp[-a:].max() + b)
    np.maximum(dp[a:], dp[:-a] + b, out=dp[a:])


print(ans)


import numpy as np

N, T = list(map(int, input().split()))
T -= 1

AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x: x[1])
AB.sort(key = lambda x: x[0], reverse = True)

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

dp = np.zeros(T + 1, dtype = np.int32)

ans = AB[N - 1][1]
for i in range(N - 1, 0, -1):
    # for j in range(T + 1):
    #     if j < AB[i][0]:
    #         dp[i][j] = dp[i + 1][j]
    #     else:
    #         dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    if AB[i][0] <= T + 1:
        dp[AB[i][0]:] = np.maximum(dp[AB[i][0]:], dp[:T + 1 - AB[i][0]] + AB[i][1])
    tmp = dp[T] + AB[i - 1][1]
    ans = max(ans, tmp)
    
print (ans)
# print (AB)

# for i in dp:
#     print (dp)


from numpy import*
N,T,*L=int_(open(0).read().split())
d=zeros(6010,int)
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

import numpy as np
def solve(n, t, a, b):
    dp = np.zeros(t, dtype=int)
    candidates = []
    for w, v in sorted(zip(a, b)):
        candidates.append(dp[-1] + v)
        if w > t:
            continue
        dp[w:] = np.maximum(dp[:-w] + v, dp[w:])
    return np.max(candidates)

n, t = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(n, t, a, b))

import numpy as np

n, t = map(int, input().split())
dt = [list(map(int, input().split())) for _ in range(n)]
dt.sort()
dp = np.zeros(t, dtype=int)
ans = 0
for a, b in dt:
    ans = max(ans, dp[-1]+b)
    np.maximum(dp[a:], dp[:-a]+b, out=dp[a:])
print(ans)

import numpy as np

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

ab.sort()

dp = np.zeros(t, dtype=np.int64)

ans = 0
for a, b in ab:
    ans = max(ans, dp[-1] + b)
    np.maximum(dp[a:], dp[:-a] + b, out=dp[a:])


print(ans)


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

  for a,b in L:
    for j in range(T-1,-1,-1):
      if dp[j]>=0 and dp[j+a]<dp[j]+b:
        dp[j+a]=dp[j]+b

  print((max(dp)))

def __starting_point():
  main()

__starting_point()

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))))

def __starting_point():
	main()

__starting_point()

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
    for a, b in sorted(AB):
        for i in range(T - 1, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + a] < dp[i] + b:
                dp[i + a] = dp[i] + b
    print((max(dp)))


main()


from numpy import zeros, maximum
N, T, *AB = map(int, open(0).read().split()) 
dp = zeros(6010, int)
for w, v in sorted(zip(*[iter(AB)] * 2)):
  dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)
print(dp.max())

import numpy as np

N, T = map(int, input().split())
AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

AB.sort()

dp = np.zeros(T, dtype=int)

ans = 0
for a, b in AB:
  ans = max(ans, dp[-1] + b)
  dp[a:] = np.maximum(dp[a:], dp[:-a] + b)

print(ans)

import numpy as np

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

#print(data)

dp = np.zeros(T)
ans = 0
for a, b in data:
  ans = max(ans, dp[-1]+b)
  if a < T:
    newtable = dp[:T-a] + b
    dp[a:] = np.maximum(dp[a:], newtable)
print(int(ans))

import numpy as np
import sys
input = sys.stdin.readline


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

ans = 0
dp = np.zeros(t, dtype=int)
for time, point in dish:
    ans = max(ans, dp.max()+point)
    np.maximum(dp[time:], dp[:-time]+point, out=dp[time:])
print(ans)

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
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print((max(dp)))


main()


import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    dishes = []
    for _ in range(N):
        a, b = map(int, input().split())
        dishes.append((a, b))
    
    dishes = sorted(dishes, key=lambda x: x[0])
    
    ans = 0
    dp = np.zeros(T, dtype=int)
    for a, b in dishes:
        ans = max(ans, dp.max() + b)
        np.maximum(dp[:-a] + b, dp[a:], out=dp[a:])

    return ans

def __starting_point():
    print(main())
__starting_point()

import numpy as np
n,t=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
b=np.zeros((n+1,t))
c=np.zeros((n+1,t))
for i in range(n):
    b[i+1]=b[i]
    b[i+1][a[i][0]:]=np.maximum(b[i+1][a[i][0]:],b[i][:-a[i][0]]+a[i][1])
    c[-i-2]=c[-i-1]
    c[-i-2][a[-i-1][0]:]=np.maximum(c[-i-2][a[-i-1][0]:],c[-i-1][:-a[-i-1][0]]+a[-i-1][1])
q=0
for i in range(n):
    q=max(q,max(b[i]+c[i+1][::-1])+a[i][1])
print(int(q))

import numpy as np
I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = np.array([-1] * 6001, dtype=np.int64)
dp[0] = 0
for a, b in sorted(zip(A, B)):
    dp_new = dp[:]
    dp_new[a:a + T] = np.maximum(dp[a:a + T], dp[:T] + b)
    dp = dp_new
print((max(dp)))


import numpy as np
import sys
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,T = inpl()
dp = np.zeros((6001),int)
ABs = [inpl() for _ in range(N)]
ABs.sort()

for A,B in ABs:
    dp[A:T+A] = np.maximum(dp[A:T+A], dp[:T]+B)
    # for i in reversed(range(A,T+A)):
    #     dp[i] = max(dp[i-A] + B, dp[i])


print((max(dp)))


from numpy import zeros, maximum, array

def main():
    N, T, *AB = array(open(0).read().split(), int)

    dp = zeros(6010, int)
    for w, v in sorted(zip(*[iter(AB)] * 2)):
        dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)

    print(dp.max())

main()

# -*- coding: utf-8 -*-

import sys
import numpy as np
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, T = MAP()
AB = []
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

# 各料理を時間の昇順でソート
AB.sort(key=itemgetter(0))

# 後は普通のナップザック
TMAX = 6007
dp = np.zeros((N+1, TMAX), dtype=np.int64)
for i in range(N):
    a, b = AB[i]
    dp[i+1] = dp[i]
    dp[i+1,a:a+T] = np.maximum(dp[i+1,a:a+T], dp[i,:T] + b)
print((dp[N].max()))


from numpy import*
N,T,*L=int_(open(0).read().split())
d=int_([0]*6010)
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

import sys

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


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

    D.sort()

    dp = [0] * T
    ans = 0

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

    print(ans)
    return


def __starting_point():
    main()

__starting_point()