AtCoder Beginner Contest 145 - All-you-can-eat

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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
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]))


(N, T) = map(int, input().split())
K = []
for i in range(N):
	(a, b) = map(int, input().split())
	K.append([a, b])
K.sort()
dp = [[0] * (N + 1) for _ in range(T + 3001)]
for i in range(1, T + 3001):
	for j in range(N):
		if 0 <= i - K[j][0] <= T - 1:
			dp[i][j + 1] = max(dp[i - K[j][0]][j] + K[j][1], dp[i][j])
		else:
			dp[i][j + 1] = dp[i][j]
ans = 0
for i in range(1, T + 3001):
	ans = max(dp[i][N], ans)
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 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()


(n, t) = 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)


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)


(n, t) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
l.sort()
dp = [[0] * t for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(t):
		if j - l[i - 1][0] >= 0:
			dp[i][j] = max(dp[i - 1][j - l[i - 1][0]] + l[i - 1][1], dp[i - 1][j])
		else:
			dp[i][j] = dp[i - 1][j]
ans = []
for i in range(n):
	ans.append(dp[i][-1] + l[i][1])
print(max(ans))


(n, t) = [int(i) for i in input().split()]
ab = []
for _ in range(n):
	ab.append([int(i) for i in input().split()])
ab.sort(key=lambda x: x[0])
aa = t + max([i[0] for i in ab]) + 1
c = [0] * aa
for i in ab:
	d = c[:]
	for j in range(t):
		k = d[j]
		l = i[0] + j
		if l >= aa:
			continue
		c[l] = max(c[l], d[j] + i[1])
print(max(c))


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)


(n, t) = map(int, input().split())
(a, b) = ([0] * n, [0] * n)
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
dp = [[[0] * (t + 1) for i in range(n + 1)] for j in range(2)]
for i in range(n):
	for d in range(2):
		for l in range(1, t + 1):
			if l < a[i]:
				dp[d][i + 1][l] = max(dp[d][i][l], d * (b[i] + dp[0][i][l - 1]))
			else:
				dp[d][i + 1][l] = max(dp[d][i][l], b[i] + dp[d][i][l - a[i]], d * (b[i] + dp[0][i][l - 1]))
print(dp[1][n][t])


(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)
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)
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 main():
	(_, t, *L) = 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)))
main()


(n, t) = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
items.sort()
ma = items[-1][0]
dp = [0] * (t + ma)
for (a, b) in items:
	for i in range(t + ma - 1, a - 1, -1):
		if i - a < t:
			dp[i] = max(dp[i], dp[i - a] + b)
print(max(dp))


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


(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 = [[0 for t in range(T)] for i in range(N + 1)]
ans = 0
for (i, ab) in enumerate(AB):
	ans = max(ans, dp[i][T - 1] + ab[1])
	for t in range(T):
		if t < ab[0]:
			dp[i + 1][t] = dp[i][t]
		else:
			dp[i + 1][t] = max(dp[i][t - ab[0]] + ab[1], dp[i][t])
print(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 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())


(n, t) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
dp = [[0 for i in range(t + 1)] for j in range(n + 1)]
for i in range(n):
	(ti, vi) = ab[i]
	for j in range(t + 1):
		if j + ti <= t:
			dp[i + 1][j + ti] = max(dp[i + 1][j + ti], dp[i][j] + vi)
		dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
ma = 0
for (i, (ti, vi)) in enumerate(ab):
	ma = max(ma, dp[i][t - 1] + vi)
print(ma)


(N, T) = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]
G.sort()
dp = [0] * 60000
for g in G:
	for i in range(T - 1, -1, -1):
		dp[i + g[0]] = max(dp[i + g[0]], dp[i] + g[1])
print(max(dp))


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)


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)


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0] * (T + 1)
for (A, B) in AB:
	for i in range(T - 1, -1, -1):
		if A + i >= T:
			dp[T] = max(dp[T], dp[i] + B)
		else:
			dp[i + A] = max(dp[i + A], dp[i] + B)
print(max(dp))


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


(n, t) = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort()
d = [0] * 6000
for (c, v) in a:
	for i in reversed(range(t)):
		d[i + c] = max(d[i + c], d[i] + v)
print(max(d))


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


(n, t) = map(int, input().split())
ab = []
for i in range(n):
	(a, b) = map(int, input().split())
	ab.append([a, b])
dp = [0] * t
ab.sort()
m = 0
for (i, j) in ab:
	(pdp, dp) = (dp, [0] * t)
	for k in range(t):
		dp[k] = pdp[k]
	for k in range(t):
		if k + i >= t:
			m = max(m, pdp[k] + j)
		else:
			dp[k + i] = max(dp[k + i], pdp[k] + j)
if m == 0:
	print(max(dp))
else:
	print(m)


(n, t) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
dp = [0] * (t + max(l)[0])
for (a, b) in l:
	for i in range(0, t + a)[::-1]:
		if i - a >= 0:
			dp[i] = max(dp[i], dp[i - a] + b)
print(max(dp[t:]))


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())
meals = [tuple(map(int, input().split())) for _ in range(N)]
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])


(n, t) = map(int, input().split())
lst = [0 for _ in range(t)]
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
ans = 0
for (a, b) in ab:
	ans = max(ans, lst[-1] + b)
	for i in range(t - 1, a - 1, -1):
		lst[i] = max(lst[i], lst[i - a] + b)
print(ans)


(n, t) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
	(wi, vi) = ab[i]
	for j in range(t + 1):
		if j + wi <= t:
			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(ab):
	ans = max(ans, dp[i][t - 1] + vi)
print(ans)


(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])
dp = [-1] * (t + 1)
dp[0] = 0
for (a, b) in ab:
	tmp = dp[:]
	for i in range(t):
		if dp[i] >= 0 and dp[i] + b > tmp[min(i + a, t)]:
			tmp[min(i + a, t)] = dp[i] + b
	dp = tmp
print(max(dp))


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) = 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)
print(ans)


def ints():
	return [int(x) for x in input().split()]

def ii():
	return int(input())
(N, T) = ints()
dp = [[0] * T for j in range(N + 1)]
F = sorted([ints() for i in range(N)])
for i in range(N):
	(a, b) = F[i]
	for t in range(T):
		dp[i + 1][t] = max(dp[i + 1][t], dp[i][t])
		nt = t + a
		if nt < T:
			dp[i + 1][nt] = max(dp[i + 1][nt], dp[i][t] + b)
w = max([F[i][1] + dp[i][T - 1] for i in range(1, N)])
print(w)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = 10 ** 18
eps = 10 ** (-7)
(N, W) = map(int, readline().split())
AB = [tuple(map(int, readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0] * (W + 1)
for (w, v) in AB:
	dpnew = dp[:]
	for j in range(W):
		dpnew[min(j + w, W)] = max(dp[min(j + w, W)], dp[j] + v)
	dp = dpnew
print(dp[W])


(n, t) = 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)


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


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)


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


(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)
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 sys
input = sys.stdin.readline
(n, t) = map(int, input().split())
AB = []
for i in range(n):
	(a, b) = map(int, input().split())
	AB.append((a, b))
AB.sort(key=lambda x: x[0])
ans = 0
dp = [[0] * t for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = AB[i]
	for j in range(t):
		if j >= a:
			dp[i + 1][j] = max(dp[i][j - a] + b, dp[i][j], dp[i + 1][j - 1])
		else:
			dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - 1])
	ans = max(ans, dp[i + 1][t - 1] + AB[i + 1][1])
print(ans)


(n, t) = map(int, input().split())
ab = sorted((list(map(int, input().split())) for _ in range(n)))
dp = [-1] * (t - 1) + [0]
ret = 0
for i in range(n):
	(a, b) = ab[i]
	newdp = dp[:]
	for j in range(t):
		if dp[j] >= 0:
			ret = max(ret, dp[j] + b)
			if j - a >= 0:
				newdp[j - a] = max(newdp[j - a], dp[j] + b)
	dp = newdp
print(ret)


(n, t) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
a.sort()
DP = [[0 for i in range(t + 3001)] for j in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, t + 3001):
		if j - a[i - 1][0] >= 0:
			DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - a[i - 1][0]] + a[i - 1][1])
		else:
			DP[i][j] = DP[i - 1][j]
ans = 0
for i in range(n):
	ans = max(ans, DP[i][t - 1] + a[i][1])
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()


(N, T) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')
dp = [-INF] * (T + 1)
dp[0] = 0
for (a, b) in AB:
	newDp = dp[:]
	for (t, d) in enumerate(dp[:T]):
		newDp[min(T, t + a)] = max(newDp[min(T, t + a)], d + b)
	dp = newDp
print(max(dp))


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


(N, T) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (T + 1) for _ in range(N + 1)]
for (i, (a, b)) in enumerate(sorted(X)):
	for j in range(T + 1):
		if j == T:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + b)
		elif j < a:
			dp[i + 1][j] = dp[i][j]
		else:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - a] + b)
print(dp[-1][-1])


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


(N, T) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
dp = [-1] * 6001
dp[0] = 0
for (a, b) in sorted(X):
	for j in reversed(range(T)):
		if dp[j] == -1:
			continue
		dp[j + a] = max(dp[j + a], dp[j] + b)
print(max(dp))


(N, T) = map(int, input().split())
item = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
dp = [0] * (T + 1)
for (a, b) in item:
	for t in reversed(range(T)):
		dist = min(T, t + a)
		dp[dist] = max(dp[t] + b, dp[dist])
print(max(dp))


(N, T) = map(int, input().split())
Tmax = 6000
dp = [[-1] * Tmax for i in range(N + 1)]
dp[0][0] = 0
q = []
for i in range(N):
	q.append(list(map(int, input().split())))
q.sort()
for i in range(N):
	dp[i + 1][:] = dp[i][:]
	(a, b) = q[i]
	for j in range(T):
		if dp[i][j] >= 0:
			dp[i + 1][a + j] = max(dp[i][a + j], dp[i][j] + b)
print(max(dp[N]))


ans = 0
(n, t) = 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)))


(N, T) = map(int, input().split())
L = []
for i in range(N):
	(a, b) = map(int, input().split())
	L.append((a, b))
L.sort()
DP = [[0 for i in range(T)] for j in range(N)]
for i in range(N):
	a = L[i][0]
	b = L[i][1]
	for j in range(min(T, a)):
		DP[i][j] = DP[i - 1][j]
	for j in range(min(T, a), T):
		DP[i][j] = max(DP[i - 1][j - a] + b, DP[i - 1][j])
ans = 0
for i in range(N - 1):
	ans = max(ans, DP[i][T - 1] + L[i + 1][1])
print(ans)


import sys
input = sys.stdin.readline
(n, t) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
dp = [[0 for j in range(t + 1)] for i in range(n + 1)]
for i in range(n):
	for j in range(t + 1):
		dp[i + 1][j] = dp[i][j]
	for j in range(t):
		next = min(j + ab[i][0], t)
		dp[i + 1][next] = max(dp[i + 1][next], dp[i][j] + ab[i][1])
print(max(dp[n]))


(N, T) = [int(s) for s in input().split(' ')]
AB = sorted([tuple((int(s) for s in input().split(' '))) for _ in range(N)])
dp = [0] * T
ans = 0
for (a, b) in AB:
	for (t, v) in enumerate(dp):
		if t >= a:
			dp[t - a] = max(dp[t - a], v + b)
		else:
			ans = max(ans, v + b)
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.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 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 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 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))


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


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


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


(n, t) = map(int, input().split())
ab = []
for i in range(n):
	(a, b) = map(int, input().split())
	ab.append((a, b))
ab.sort()
am = ab[-1][0]
dp = [-1] * (t + am + 1)
dp[0] = 0
for j in range(n):
	for i in range(t - 1, -1, -1):
		if dp[i] != -1:
			dp[i + ab[j][0]] = max(dp[i + ab[j][0]], dp[i] + ab[j][1])
print(max(dp))


import sys
input = sys.stdin.readline
(N, T) = map(int, input().split())
L = []
for i in range(N):
	(a, b) = map(int, input().split())
	L.append((a, b))
L.sort()
dp = [-1 for i in range(6001)]
dp[0] = 0
for i in range(N):
	for j in range(T):
		if dp[T - 1 - j] != -1:
			dp[T - 1 - j + L[i][0]] = max(dp[T - 1 - j + L[i][0]], dp[T - 1 - j] + L[i][1])
print(max(dp))


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)


(n, t) = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * t for i in range(n + 1)]
s.sort()
for i in range(n):
	for j in range(t):
		if j - s[i][0] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - s[i][0]] + s[i][1])
		else:
			dp[i + 1][j] = dp[i][j]
ans = 0
for i in range(n):
	ans = max(ans, dp[i][t - 1] + s[i][1])
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])
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)
	anss.append(dp[i][-1] + menu[i][1])
print(max(anss))


import sys
readline = sys.stdin.buffer.readline
(n, t) = map(int, readline().split())
dp = [0] * (t + 1)
AB = [list(map(int, readline().split())) for i in range(n)]
AB.sort(reverse=True)
for i in range(n):
	(a, b) = AB[i]
	for j in range(t):
		if j + a > t:
			dp[j] = max(dp[j], b)
		else:
			dp[j] = max(dp[j], dp[j + a] + b)
print(dp[0])


(N, T) = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)])
dp = [[0] * N for _ in range(T)]
for i in range(1, T):
	for j in range(N - 1):
		if AB[j][0] <= i:
			dp[i][j] = max(dp[i][j - 1], dp[i - AB[j][0]][j - 1] + AB[j][1])
		else:
			dp[i][j] = dp[i][j - 1]
ans = 0
for j in range(1, N):
	ans = max(ans, dp[-1][j - 1] + AB[j][1])
print(ans)


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


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [0] * (T + 1)
for (a, b) in AB:
	for t in range(T):
		x = dp[t + a] + b if t + a < T else b
		dp[t] = max(dp[t], x)
ans = dp[0]
print(ans)


(n, t) = map(int, input().split())
c = [tuple(map(int, input().split())) for _ in range(n)]
c.sort()
dp = [-1] * t
dp[0] = 0
ans = 0
for r in range(n):
	(a, b) = c[r]
	cur = max(dp) + b
	if ans < cur:
		ans = cur
	for i in range(t - a - 1, -1, -1):
		if dp[i] >= 0 and dp[i + a] < dp[i] + b:
			dp[i + a] = dp[i] + b
cur = max(dp)
if cur > ans:
	ans = cur
print(ans)


(n, t) = [int(_) for _ in input().split()]
ab = []
for i in range(n):
	ab_ = [int(_) for _ in input().split()]
	ab.append(ab_)
ab.sort()
dp = [-1 for _ in range(6000)]
dp[0] = 0
dp2 = dp[:]
dplist = [0]
for i in range(n):
	dp_trans = ab[i][0]
	dp_delicious = ab[i][1]
	for j in range(t):
		if dp[j] != -1:
			dp2[j + dp_trans] = max(dp[j + dp_trans], dp[j] + dp_delicious)
	dp = dp2[:]
print(max(dp))


(n, w) = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(n)])
dp = [[0] * (w + 1) for _ in range(n + 2)]
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)


(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)
dp = [[0, 0] for i in range(T)]
for i in range(N):
	for j in reversed(range(T)):
		dp[j][1] = max(dp[j][1], dp[j][0] + B[i])
		if j - A[i] >= 0:
			dp[j][0] = max(dp[j - A[i]][0] + B[i], dp[j][0])
			dp[j][1] = max(dp[j - A[i]][1] + B[i], dp[j][1])
ans = max(dp[T - 1][0], dp[T - 1][1])
print(ans)


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


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


inpl = lambda : list(map(int, input().split()))
(N, T) = inpl()
AB = sorted([inpl() for _ in range(N)])
ans = 0
dp_intime = [0] * T
for n in range(N):
	dp_intime_prev = dp_intime
	dp_intime = [0] * T
	(a, b) = AB[n]
	for t in range(T):
		if t < a:
			dp_intime[t] = dp_intime_prev[t]
		else:
			dp_intime[t] = max(dp_intime_prev[t], dp_intime_prev[t - a] + b)
	ans = max(ans, dp_intime_prev[-1] + b)
print(ans)


(N, T) = map(int, input().split())
AB = sorted([list(map(int, input().split())) for i in range(N)])
dp = [[0] * (T + 3001) for i in range(N + 1)]
for i in range(1, N + 1):
	(a, b) = AB[i - 1]
	for j in range(T + 3001):
		dp[i][j] = dp[i - 1][j]
		if 0 <= j - a < T:
			dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b)
print(max(dp[-1]))


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)


(N, T) = 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)


(N, T) = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
li = sorted(li, key=lambda x: x[0])
dp = [0] * T
counter = 0
for i in range(N - 1):
	(A, B) = li[i]
	counter = max(counter, max(dp) + B)
	if A > T - 1:
		continue
	for t in range(T - A - 1, -1, -1):
		dp[t + A] = max(dp[t] + B, dp[t + A])
print(max(max(dp) + li[N - 1][1], counter))


from heapq import heappop, heappush
(N, T) = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
AB = sorted(AB)
j = 0
ans = 0
dp = [[0] * (T + 1) for _ in range(N + 1)]
for i in range(N):
	for t in range(T + 1):
		dp[i + 1][t] = max(dp[i + 1][t], dp[i][t])
		if t <= T - 1:
			dp[i + 1][min(T, t + AB[i][0])] = max(dp[i + 1][min(T, t + AB[i][0])], dp[i][t] + AB[i][1])
print(dp[N][T])


(N, T) = map(int, input().split())
a_list = []
for _ in range(N):
	(a, b) = map(int, input().split())
	a_list.append((a, b))
a_list.sort(key=lambda x: x[0])
dp = [[0 for _ in range(T + 3001)] for _ in range(N + 1)]
for i in range(1, N + 1):
	(a, b) = a_list[i - 1]
	for j in range(T + 3001):
		dp[i][j] = dp[i - 1][j]
	for j in range(T):
		dp[i][j + a] = max(dp[i - 1][j + a], dp[i - 1][j] + b)
print(max(dp[-1]))


def main():
	(N, T, *AB) = map(int, open(0).read().split())
	dp = [0] * (T + max(AB[::2]))
	for (w, v) in sorted(zip(*[iter(AB)] * 2)):
		for i in reversed(range(T)):
			if dp[i + w] < dp[i] + v:
				dp[i + w] = dp[i] + v
	print(max(dp))
main()


import sys
readline = sys.stdin.readline
(N, T) = map(int, readline().split())
AB = [list(map(int, readline().split())) for _ in range(N)]
AB.sort()
(A, B) = map(list, zip(*AB))
dp = [0] * (T + max(A) + 2)
L = len(dp)
for i in range(N):
	dp2 = dp[:]
	(a, b) = (A[i], B[i])
	for t in range(L):
		if T + a > t >= a:
			dp2[t] = max(dp2[t], dp[t - a] + b)
	dp = dp2[:]
print(max(dp))


import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)
(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:])
	now = 0
	if i != N - 1:
		now = dp[i + 1][T - 1] + max(FOOD[i + 1:], key=lambda x: x[1])[1]
	ans = max(ans, now)
print(ans)


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


(N, T) = map(int, input().split())
abl = []
for _ in range(N):
	(a, b) = map(int, input().split())
	abl.append((a, b))
abl.sort()
dp = [[0] * 6001 for _ in range(N + 1)]
for i in range(N):
	(a, b) = abl[i]
	for t in range(6001):
		dp[i + 1][t] = max(dp[i + 1][t], dp[i][t])
		if t < T:
			dp[i + 1][t + a] = max(dp[i][t] + b, dp[i][t + a])
ans = max(dp[N])
print(ans)


(n, t) = map(int, input().split())
ab = [[0] * 2 for i in range(n + 1)]
for i in range(1, n + 1):
	(ab[i][0], ab[i][1]) = map(int, input().split())
dp = [[0] * (t + 3001) for i in range(n + 1)]
ab.sort(key=lambda x: x[0])
for i in range(1, n + 1):
	for j in range(t):
		dp[i][j] = max(dp[i][j], dp[i - 1][j])
		dp[i][j + ab[i][0]] = max(dp[i][j + ab[i][0]], dp[i - 1][j] + ab[i][1])
ans = 0
for i in range(n + 1):
	ans = max(ans, max(dp[i]))
print(ans)


(n, t) = list(map(int, input().split()))
ab = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
dp = [[-10 ** 10] * (t + 1) for _ in range(n + 1)]
dp[0][0] = 0
dp[1][0] = 0
ans = ab[0][1]
for i in range(1, n):
	for j in range(t):
		dp[i + 1][j] = max(dp[i][j], dp[i][j - ab[i - 1][0]] + ab[i - 1][1] if j >= ab[i - 1][0] else -10 ** 10)
		ans = max(ans, dp[i + 1][j] + ab[i][1])
print(ans)


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


(N, T) = map(int, input().split())
p = []
for i in range(N):
	(A, B) = map(int, input().split())
	p.append([A, B])
p.sort()
dp = [[0] * 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])
		nextj = j + p[i][0]
		if nextj < T:
			dp[i + 1][nextj] = max(dp[i + 1][nextj], dp[i][j] + p[i][1])
	now = dp[i][T - 1] + p[i][1]
	ans = max(ans, now)
print(ans)


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(n, t) = na()
dp = [0] * 6005
ab = []
for i in range(n):
	ab.append(na())
ab.sort(key=lambda x: x[0])
for u in ab:
	for i in range(6004 - u[0], -1, -1):
		if i < t:
			dp[i + u[0]] = max(dp[i + u[0]], dp[i] + u[1])
print(max(dp))


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * T
AB.sort()
m = 0
for (a, b) in AB:
	m = max(m, dp[-1] + b)
	for j in range(T - 1, a - 1, -1):
		dp[j] = max(dp[j], dp[j - a] + b)
print(m)


(N, T) = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
DP = [[0] * T for _ in range(N)]
DP[0][0] = AB[0][1]
for i in range(1, N):
	(a, b) = AB[i]
	DP[i][0] = max(DP[i - 1][0], b)
	for j in range(T):
		DP[i][j] = max(DP[i][j], DP[i - 1][j])
		if j + a < T:
			DP[i][j + a] = DP[i - 1][j] + b
print(max(DP[-1]))


def solve():
	(N, T) = 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())


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


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * T
AB.sort()
ans = 0
for i in range(N):
	(a, b) = AB[i]
	ans = max(ans, dp[-1] + b)
	for j in range(T - 1, -1, -1):
		if j - a >= 0:
			dp[j] = max(dp[j], dp[j - a] + b)
print(ans)


(N, T) = map(int, input().split())
l = []
for _ in range(N):
	(a, b) = map(int, input().split())
	l.append([a, b])
l.sort()
dp = [-1] * 6001
dp[0] = 0
for cand in l:
	for i in range(T)[::-1]:
		if dp[i] != -1:
			dp[i + cand[0]] = max(dp[i + cand[0]], dp[i] + cand[1])
print(max(dp))


(N, T) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
(A, B) = map(list, zip(*AB))
dp = {0: 0}
for i in range(N):
	prev_dp = dp.copy()
	for a in prev_dp.keys():
		if a >= T or (a + A[i] in dp and dp[a + A[i]] >= prev_dp[a] + B[i]):
			continue
		dp[a + A[i]] = prev_dp[a] + B[i]
print(max(dp.values()))


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (T + 1) for _ in range(N + 1)]
AB.sort()
for i in range(1, N + 1):
	dp[i] = dp[i - 1][:]
	time = AB[i - 1][0]
	happy = AB[i - 1][1]
	for j in range(T):
		dp[i][min(j + time, T)] = max(dp[i][min(j + time, T)], dp[i - 1][j] + happy)
print(dp[N][T])


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


(n, t) = map(int, input().split())
dish = [list(map(int, input().split())) for i in range(n)]
dish.sort()
dp = [0] * 6001
for i in range(n):
	(a, b) = dish[i]
	for j in range(t - 1, -1, -1):
		dp[j + a] = max(dp[j + a], dp[j] + b)
print(max(dp))


def main():
	(n, t) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * n]
	ab.sort(key=lambda x: x[0])
	dp = [0] * (t + 1)
	for (a, b) in ab:
		for i in range(t - 1, -1, -1):
			if a + i >= t:
				dp[t] = max(dp[t], dp[i] + b)
			else:
				dp[i + a] = max(dp[i + a], dp[i] + b)
	print(max(dp))
main()


(N, T) = map(int, input().split())
fs = [tuple(map(int, input().split())) for _ in range(N)]
fs = sorted(fs)
dp = [0] * 6005
for (a, b) in fs:
	for t in range(T + a - 1, a - 1, -1):
		dp[t] = max(dp[t - a] + b, dp[t])
print(max(dp))


(n, t) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[0])
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(t + 1):
		dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
		res = j + ab[i][0]
		if res <= t:
			dp[i + 1][res] = max(dp[i][res], dp[i][j] + ab[i][1])
	dp[i + 1][t] = max(dp[i + 1][t], dp[i][t], dp[i][t - 1] + ab[i][1])
print(dp[n][t])


(n, t) = map(int, input().split())
dishes = []
for _ in range(n):
	(time, point) = map(int, input().split())
	dishes.append([time, point])
dishes.sort()
DP = [0] * t
candidates = []
for (time, point) in dishes:
	candidates.append(max(DP) + point)
	for i in range(t - 1, time - 1, -1):
		DP[i] = max(DP[i], DP[i - time] + point)
print(max(candidates))


(n, W) = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()
ans = 0
dp = [0] * W
for (a, b) in ab:
	if ans < dp[-1] + b:
		ans = dp[-1] + b
	for j in reversed(range(W)):
		if j - a < 0:
			break
		if dp[j] < dp[j - a] + b:
			dp[j] = dp[j - a] + b
print(ans)


(n, t) = map(int, input().split())
dish = []
for _ in range(n):
	(a, b) = 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[-1])


(N, T) = map(int, input().split())
A = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
A.insert(0, [-1, -1])
dp = [[0 for _ in range(T + 1)] for _ in range(N)]
for i in range(1, N):
	for j in range(1, T + 1):
		dp[i][j] = dp[i - 1][j]
		if j > A[i][0]:
			dp[i][j] = max(dp[i][j], dp[i - 1][j - A[i][0]] + A[i][1])
dmax = 0
for i in range(1, N + 1):
	dmax = max(dmax, dp[i - 1][T] + A[i][1])
print(dmax)


def main():
	(N, T) = 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 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)


(n, t) = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
dp = [[0 for i in range(t + 1)] for j in range(n + 1)]
for i in range(n):
	(ti, vi) = ab[i]
	for j in range(t + 1):
		if j + ti <= t:
			dp[i + 1][j + ti] = max(dp[i + 1][j + ti], dp[i][j] + vi)
		dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
ans = 0
for (i, (ti, vi)) in enumerate(ab):
	ans = max(ans, dp[i][t - 1] + vi)
print(ans)


import sys
input = sys.stdin.readline
(N, T) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
dp0 = [0] * T
dp1 = [0] * T
for (A, B) in AB:
	for j in range(T):
		dp1[j] = max(dp1[j], dp0[j] + B)
	for j in range(A, T)[::-1]:
		dp0[j] = max(dp0[j], dp0[j - A] + B)
print(dp1[-1])


(n, t) = map(int, input().split())
dishes = [[int(i) for i in input().split()] for _ in range(n)]
dishes.sort(key=lambda x: x[0])
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
	(a, b) = dishes[i]
	for j in range(t + 1):
		if j < t:
			dp[i + 1][min(j + a, t)] = max(dp[i + 1][min(j + a, t)], dp[i][j] + b)
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[n][t])


(n, t) = map(int, input().split())
dp = [0] * (t + 3005)
ans = chk = 0
w = []
for i in range(n):
	(a, b) = map(int, input().split())
	w.append((a, b))
w.sort()
for i in w:
	for j in range(t - 1, -1, -1):
		dp[j + i[0]] = max(dp[j + i[0]], dp[j] + i[1])
		ans = max(ans, dp[j + i[0]])
print(ans)


(n, t) = map(int, input().split())
dp = [0] * (t + 1)
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()
max_b = [0] * n
max_b[-1] = ab[-1][1]
for i in range(n - 1, 0, -1):
	max_b[i - 1] = max(ab[i - 1][1], max_b[i])
for i in range(n - 1):
	(a, b) = ab[i]
	for j in range(t - 1, a - 1, -1):
		dp[j] = max(dp[j - a] + b, dp[j])
	dp[t] = max(dp[t], dp[t - 1] + max_b[i + 1])
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)
print(max(dp))


(N, T) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort()
dp = [-1 for _ in range(T + X[-1][0] + 10)]
dp[0] = 0
for i in range(N):
	for j in range(T, 0, -1):
		if dp[j - 1] != -1:
			dp[j - 1 + X[i][0]] = max(dp[j - 1 + X[i][0]], dp[j - 1] + X[i][1])
print(max(dp))


import numpy as np

def __starting_point():
	(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
	for ab in menu:
		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 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))


(a, b) = map(int, input().split())
c = [list(map(int, input().split())) for i in range(a)]
c.sort()
DP = [[0 for j in range(b + 1)] for i in range(a)]
for i in range(c[0][0], b + 1):
	DP[0][i] += c[0][1]
for i in range(1, a):
	for j in range(b):
		if j < c[i][0]:
			DP[i][j] = DP[i - 1][j]
		else:
			DP[i][j] = max(DP[i - 1][j - c[i][0]] + c[i][1], DP[i - 1][j])
	DP[i][b] = max(DP[i - 1][b - 1] + c[i][1], DP[i - 1][b])
print(max(DP[-1]))


import sys
input = sys.stdin.readline
(N, T) = 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))


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)


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


(n, t) = map(int, input().split())
l = []
for i in range(n):
	(a, b) = 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)


(N, M) = map(int, input().split())
AB = []
for i in range(N):
	AB.append(list(map(int, input().split())))
AB.sort(key=lambda x: x[0])
max_ = 0
for i in AB:
	if max_ < i[0]:
		max_ = i[0]
dp = [0] * (max_ + M)
max_ = 0
for i in AB:
	for j in range(M)[::-1]:
		dp[j + i[0]] = max(dp[j + i[0]], dp[j] + i[1])
print(max(dp))


(N, T) = map(int, input().split())
dp = [[0 for _ in range(T)] for _ in range(N + 1)]
AB = [tuple(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][j], dp[i - 1][j])
		if j >= A:
			dp[i][j] = max(dp[i][j], dp[i - 1][j - A] + B)
AB.append((0, 0))
ans = [x[T - 1] + AB[i][1] for (i, x) in enumerate(dp)]
print(max(ans))


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 collections
(n, t) = map(int, input().split())
tpls = list(sorted((tuple(map(int, input().split())) for _ in range(n))))
a = [None] * n
b = [None] * n
for i in range(n):
	(a[i], b[i]) = tpls[i]
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(t):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		k = min(t, j + a[i])
		dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + b[i])
print(max(map(max, dp)))


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)


(n, t) = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]
ab.sort()
dp = [[0] * t for i in range(n + 1)]
ans = 0
for i in range(n):
	for j in range(t):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if j - ab[i][0] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - ab[i][0]] + ab[i][1])
	now = dp[i][t - 1] + ab[i][1]
	ans = max(ans, now)
print(ans)


(N, T) = map(int, input().split())
A = [0] * T
B = [0] * T
for _ in range(N):
	(a, b) = map(int, input().split())
	for i in range(T)[::-1]:
		if i + a < T:
			A[i + a] = max(A[i + a], A[i] + b)
			B[i + a] = max(B[i + a], B[i] + b)
		B[i] = max(B[i], A[i] + b)
print(max(B))


(n, t) = map(int, input().split())
now = [0 for _ in range(t + 1)]
wv = []
for _ in range(n):
	wv.append(list(map(int, input().split())))
wv.sort(key=lambda x: x[0])
for i in range(n):
	(w, v) = wv[i]
	last = now
	now = []
	for f in range(t):
		if f - w >= 0:
			now.append(max(last[f], last[f - w] + v))
		else:
			now.append(last[f])
	now.append(max(last[-2] + v, last[-1]))
print(now[-1])


(n, W) = 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(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))


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


(n, t) = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
MAX = 10000
dish.sort()
dp = [[0] * MAX for _ in range(n + 1)]
for i in range(n):
	(time, value) = dish[i]
	for j in range(t):
		dp[i + 1][j + time] = max(dp[i + 1][j + time], dp[i][j] + value)
	for j in range(MAX):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[n]))


import sys
input = sys.stdin.readline
(N, T) = 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)


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


def MAP():
	return list(map(int, input().split()))

def INT():
	return int(input())

def FLOAT():
	return float(input())
MOD = 10 ** 9 + 7
(n, t) = MAP()
dp = [0] * 6005
ab = []
for i in range(n):
	ab.append(MAP())
ab.sort(key=lambda x: x[0])
for u in ab:
	for i in range(6004 - u[0], -1, -1):
		if i < t:
			dp[i + u[0]] = max(dp[i + u[0]], dp[i] + u[1])
print(max(dp))


def p_e():
	(n, t) = map(int, input().split())
	ab = [tuple(map(int, input().split())) for _ in range(n)]
	ab.sort()
	ma = ab[-1][0]
	dp = [0] * (t + ma)
	for (w, v) in ab:
		next = [0] * (t + ma)
		for j in range(1, t + ma):
			if 0 <= j - w < t:
				next[j] = max(dp[j - w] + v, dp[j])
			else:
				next[j] = dp[j]
		dp = next
	print(max(dp))
p_e()


(N, T) = 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(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)


(n, t) = map(int, input().split())
f = [[0, 0] for i in range(t + 1)]
for i in range(n):
	(w, v) = map(int, input().split())
	for j in range(t, 0, -1):
		f[j][1] = max(f[j][1], f[j - 1][0] + v)
		if j >= w:
			f[j][0] = max(f[j][0], f[j - w][0] + v)
			f[j][1] = max(f[j][1], f[j - w][1] + v)
print(f[t][1])


(n, t) = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]
(m, d) = (0, [0] * t)
for (a, b) in sorted(ab):
	m = max(m, b + d[t - 1])
	for l in range(t - 1, a - 1, -1):
		if b + d[l - a] > d[l]:
			d[l] = b + d[l - a]
print(m)


(n, t) = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * t for _ in range(n)]
ans = 0
a.sort()
for i in range(n - 1):
	for j in range(t):
		if j - a[i][0] < 0:
			dp[i + 1][j] = dp[i][j]
		else:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - a[i][0]] + a[i][1])
	ans = max(ans, dp[i + 1][-1] + a[i + 1][1])
print(ans)


(N, T) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
DP = [[0] * (T + 1) for _ in range(N + 1)]
for n in range(1, N + 1):
	(a, b) = AB[n - 1]
	for t in range(1, T + 1):
		if t - a >= 0:
			DP[n][t] = max(DP[n - 1][t - a] + b, DP[n - 1][t])
		else:
			DP[n][t] = DP[n - 1][t]
T = [DP[n][T - 1] + AB[n][1] for n in range(N)] + [DP[N][T]]
print(max(T))


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)


(n, t) = [int(j) for j in input().split()]
ab = []
ans = []
dp = [0] * t
for i in range(n):
	tmp = [int(j) for j in input().split()]
	ab.append(tmp)
ab.sort()
for (a, b) in ab:
	for i in range(t)[::-1]:
		if dp[i] != 0 or i == 0:
			if i + a >= t:
				ans.append(dp[i] + b)
			else:
				dp[i + a] = max(dp[i + a], dp[i] + b)
if ans:
	print(max(ans))
else:
	print(max(dp))


(N, T) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (T + 1) for _ in range(N + 1)]
AB.sort()
ret = 0
for i in range(1, N + 1):
	for j in range(1, T + 1):
		if j < AB[i - 1][0]:
			dp[i][j] = dp[i - 1][j]
		else:
			dp[i][j] = max(dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1], dp[i - 1][j])
m = 0
for i in range(N):
	m = max(m, AB[i][1] + dp[i][T - 1])
print(m)


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