Problem:
 Score : 500 points    Problem Statement 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 1 2 60
10 10
100 100      Sample Output 1 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.       Sample Input 2 3 60
10 10
10 20
10 30      Sample Output 2 60  Takahashi can eat all the dishes within 60 minutes.       Sample Input 3 3 60
30 10
30 20
30 30      Sample Output 3 50  By ordering the second and third dishes in this order, Takahashi's happiness will be 50 .  We cannot order three dishes, in whatever order we place them.       Sample Input 4 10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25      Sample Output 4 145

Solution (Python):

import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n,t=map(int,input().split())
t-=1
AB=[list(map(int,input().split())) for i in range(n)]
AB.sort(key=lambda tup:tup[1])
dp = [[0]*(t+1) for i in range(n+1)]
prev = [[0]*(t+1) for i in range(n+1)]

for i in range(1, n+1):
    for j in range(0, t+1):
        if j < AB[i-1][0]:
            dp[i][j] = dp[i-1][j]
            prev[i][j] = j
            
        else:
            if dp[i-1][j] > dp[i-1][j-AB[i-1][0]]+AB[i-1][1]:
                dp[i][j] = dp[i-1][j]
                prev[i][j] = j
            else:
                dp[i][j] = dp[i-1][j-AB[i-1][0]]+AB[i-1][1]
                prev[i][j] = j - AB[i-1][0]
S=set()
cur=t
for i in range(n-1,-1,-1):
    if (prev[i+1][cur] == cur - AB[i][0]):
        S.add(i)
    cur=prev[i+1][cur]

tmp=0
for i in range(n):
    if i not in S:
        tmp=max(tmp,AB[i][1])
    











print(dp[n][t]+tmp)

Solution (Python):
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))

Solution (Python):
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
vw = [[int(i) for i in input().split()] for _ in range(N)]
vw.sort()

M = [0] * N
for i in range(N - 1, -1, -1) :
    M[i] = max(M[i], vw[i][1])
        
dp = [-float('inf')] * T
dp[0] = 0
ret = 0

for n, (w, v) in enumerate(vw) :
    for i in range(T-1, w-1, -1) :
        dp[i] = max(dp[i], dp[i-w]+v)
    
    if n + 1 < N :
        ret = max(ret, max(dp) + M[n + 1])
    else :
        ret = max(ret, max(dp))
    
print(ret)

Solution (Python):
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))

Solution (Python):
def main():
    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())

    u = [0] + [B[0]] * (T)
    v = [0] * A[0] + [B[0]] * (T - A[0] + 1)
    
    for i in range(1, N):
        a, b = A[i], B[i]
        for t in range(T, 0, -1):
            vv = b + v[t - 1]
            if t >= a:
                vv = max(vv, b + u[t - a])
            if u[t] < vv:
                u[t] = vv
        for t in range(T, a - 1, -1):
            vv = b + v[t - a]
            if v[t] < vv:
                v[t] = vv
    print(u[T])

            



main()

Solution (Python):
n,w=map(int,input().split())
ab=[]
w-=1
take=[]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	a,b=map(int,input().split())
	ab.append([a,b])
	for j in range(w):
		if j+1-a>=0:
			dp[i+1][j+1]=max(dp[i][j+1],dp[i][j+1-a]+b)
		else:
			dp[i+1][j+1]=dp[i][j+1]
k=w
take=[]
for i in range(n):
	if dp[n-i-1][w]!=dp[n-i][w]:
		w-=ab[n-i-1][0]
		take.append(n-i-1)
take=set(take)
ans=0
for i in range(n):
	if i not in take:
		ans=max(ans,ab[i][1])
print(dp[-1][-1]+ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 





n,t = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for i in range(n)]

from operator import itemgetter


ab.sort(key = itemgetter(1), reverse = True)
ab.sort(key = itemgetter(0))

dp = [0]*(t)
val = 0



for a,b in ab:
    for i in range(max(0,t-a),t):
        val = max(val,dp[i]+b)
    
    for i in range(t-1,-1,-1):
        if i-a >= 0:
            if dp[i-a] != 0 or i==a:
                dp[i] = max(dp[i], dp[i-a] + b)
        else:
            break
    

print(max(max(dp),val))

Solution (Python):
n, t = map(int, input().split())

a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

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

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

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


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

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

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

print(ans)

Solution (Python):
N, W = map(int,input().split())
v = [0] * N
w = [0] * N
prev_w = [[0 for i in range(W + 1)] for j in range(N + 1)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
    w[i], v[i] = map(int,input().split())

for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:
            if dp[i+1][j] < dp[i][j-w[i]] + v[i]:
                dp[i+1][j] = dp[i][j-w[i]] + v[i]
                prev_w[i+1][j] = j - w[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
            prev_w[i+1][j] = j

ans=dp[-1][-1]

sel=set()
cur_w = W-1
i=N-1
while i>=0:
    if (prev_w[i+1][cur_w] == cur_w - w[i]) :
        sel.add(i)
    cur_w = prev_w[i+1][cur_w]
    i-=1

tmp=0
for i in range(N):
    if i not in sel:
        tmp=max(v[i],tmp)
print(max(ans,dp[-1][-2]+tmp))

Solution (Python):



def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    
    for i in range(n+1): 
        for w in range(W+1):
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
        res = K[n][W] 
      
    w = W
    used = [False for i in range(N)]
    for i in range(n, 0, -1): 
        if res <= 0: 
            break
        
        
        
        
        
        if res == K[i - 1][w]: 
            continue
        else: 
            
            used[i - 1] = True
              
            
            
            res = res - val[i - 1] 
            w = w - wt[i - 1] 
    return K[n][W], used

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

best, _ = knapSack(T, wts, val, N)
other, used = knapSack(T - 1, wts, val, N)
add = 0
for i, wasUsed in enumerate(used):
    if not wasUsed: add = max(add, val[i])
print(max(best, other + add))

Solution (Python):
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(key=lambda x:x[1],reverse=True)

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

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

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

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

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

    

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

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

print(ANS)

Solution (Python):
N,T = map(int,input().split())
food = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(T) for i in range(N+1)]
for i in range(N):
    a,b = food[i]
    for j in range(min(a,T)):
        DP[i+1][j] = DP[i][j]
    for j in range(a,T):
        DP[i+1][j] = max(DP[i][j],DP[i][j-a]+b)
ans = 0
i = N
j = T-1
while i > 0 and j > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        food[i-1][1] = 0
        j -= food[i-1][0]
        i -= 1
food.sort(reverse=True,key= lambda x:x[1])
print(DP[-1][-1]+food[0][1])

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

max_a = 0
for i in range(len(ab)):
    max_a = max(max_a, ab[i][0])


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


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

print(dp[-1][-1])

Solution (Python):
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)

Solution (Python):
import sys
input = sys.stdin.readline

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

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


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

for n in range(N): 
    a, b = AB[n]
    for w in range(T):
        if a > w: 
            dp[w][n+1] = dp[w][n]
            prev[w][n+1] = w
        else: 
            if b+dp[w-a][n] >= dp[w][n]:
                dp[w][n+1] = dp[w-a][n] + b
                prev[w][n+1] = w - a
            else:
                dp[w][n+1] = dp[w][n]
                prev[w][n+1] = w

ans = dp[T-1][N]
used = [False]*N
c = T-1
for i in reversed(range(N)):
    if prev[c][i+1] == c - AB[i][0]:
        used[i] = True
    c = prev[c][i+1]

p = 0
for i in range(N):
    if not used[i] and AB[i][1] > p:
        p = AB[i][1]

print(ans+p)

Solution (Python):
_, t, *L = map(int, open(0).read().split())
d = [0] * (t + max(L[::2]))
for w, v in sorted((x, y) for x, y in zip(*[iter(L)] * 2)):
	for i in range(t + w - 1, w - 1, -1):
		if d[i - w] + v > d[i]:
			d[i] = d[i - w] + v
print(max(d))

Solution (Python):


def knapsack2(N,W,weight,value,WW):
  
  inf=float("inf")
  dp=[[-inf for i in range(WW)] for j in range(N+1)]
  for i in range(WW):
      dp[0][i]=0
  maxval = 0
  
  for i in range(N):
    for w in range(WW):
      if weight[i]<=w:
        if w-weight[i]>=W: 
          dp[i+1][w]=dp[i][w]
        else: 
          dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: 
        dp[i+1][w]=dp[i][w]
    maxval = max([maxval, max(dp[i+1])])


  return maxval
  
  

N, T = map(int,input().split())
WW = T+3000
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

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

weight = [elem[0] for elem in ab]
value = [elem[1] for elem in ab]
res = knapsack2(N,T,weight,value,WW)
print(res)

Solution (Python):
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))

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

dp1 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[n][0]>=0:
            dp1[n+1][w] = max(dp1[n][w],dp1[n][w-AB[n][0]]+AB[n][1])
        else:
            dp1[n+1][w] = dp1[n][w]

for n in range(N):
    for w in range(T-1):
        dp1[n][w+1] = max(dp1[n][w+1],dp1[n][w])

dp2 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[-n-1][0]>=0:
            dp2[n+1][w] = max(dp2[n][w],dp2[n][w-AB[-n-1][0]]+AB[-n-1][1])
        else:
            dp2[n+1][w] = dp2[n][w]

for n in range(N):
    for w in range(T-1):
        dp2[n][w+1] = max(dp2[n][w+1],dp2[n][w])

ans = 0
for n in range(N):
    for w in range(T):
        ans = max(AB[n][1]+dp1[n][w]+dp2[N-n-1][T-1-w],ans)

print(ans)

Solution (Python):
n,t = map(int,input().split())
menu = []
time = [] 
value = []

for _ in range(n):
    a,b = map(int,input().split())
    menu.append([a,b])

menu = sorted(menu,key=lambda x:x[1])

for i in range(n):
    time.append(menu[i][0])
    value.append(menu[i][1])

dp = [[0 for _ in range(t+1)] for __ in range(n+1)]
ind = [[-1 for _ in range(t+1)] for __ in range(n+1)]



for i in range(n):
    for w in range(t+1):
        if time[i] < w:
            if dp[i][w-time[i]]+value[i] > dp[i][w]:
                dp[i+1][w] = dp[i][w-time[i]]+value[i]
                ind[i+1][w] = ind[i][w-time[i]]
            else:
                dp[i+1][w] = dp[i][w]
                ind[i+1][w] = i
        else:
            dp[i+1][w] = dp[i][w]
            ind[i+1][w] = i

if ind[n][t] < 0:
    print(dp[n][t])
else:
    print(dp[n][t]+value[ind[n][t]])

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    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=[[0]*(6001) for _ in range(n+1)]
    for i,(a,b) in enumerate(AB):
        for j in range(1,6001):
            if j<a:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1])
            elif j-a<t:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1],DP[i][j-a]+b)
            else:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1])
    print(max(DP[-1]))
    
if __name__=='__main__':
    main()

Solution (Python):

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



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

AB = []
for i in range(N):
	AB.append(tuple(map(int, input().split())))
AB.sort(reverse=True)

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

max_under = 0
for i in range(N):
	max_under = max(max_under, AB[i][1])
	dp[0][i] = max_under

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

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


print(dp[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
d = []
for _ in range(N):
  d.append(list(map(int, input().split())))
d.sort(key = lambda x: x[0])
dp = [[0] * (T + 1) for _ in range(N + 1)]
res = 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 + d[i][0] <= T: dp[i + 1][j + d[i][0]] = max(dp[i + 1][j + d[i][0]], dp[i][j] + d[i][1])
    else: dp[i + 1][T] = max(dp[i + 1][T], dp[i][j] + d[i][1])
  
for i in range(N + 1):
  res = max(max(dp[i]), res)
print(res)

Solution (Python):
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()
dp=[[-1]*t for i in range(n)]
for i in range(n):
    dp[i][0]=0
a,b=ab[0]
if a<t:
    dp[0][a]=b
for i in range(1,n):
    a,b=ab[i]
    for j in range(min(a,t)):
        dp[i][j]=dp[i-1][j]
    for j in range(a,t):
        if dp[i-1][j-a]==-1:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b)
table=[0]*n
table[n-1]=ab[n-1][1]
for i in range(n-2,-1,-1):
    table[i]=max(table[i+1],ab[i][1])
ans=0
for i in range(n-1):
    c=max(dp[i])
    ans=max(ans,c+table[i+1])
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


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

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

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

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

ans0 = dp[N][-1]
ans = ans0
for i in range(N):
    if s and i==s[-1] :
        s.pop()
        continue
    ans = max(ans,ans0+AB[i][1])
print(ans)

Solution (Python):

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

tlis = [[0] * (T+1) for i in range(N+1)]
AB = []

for i in range(N):

    A,B = map(int,input().split())
    AB.append([A,B])

AB.sort()

for i in range(N):

    A = AB[i][0]
    B = AB[i][1]

    for j in range(T+1):

        tlis[i+1][j] = tlis[i][j]

    tlis[i+1][min(T,A)] = max(tlis[i+1][min(T,A)],B)
    
    for j in range(T):

        if tlis[i][j] != 0:
            tlis[i+1][ min(T , j+A) ] = max(tlis[i+1][ min(T , j+A) ] , tlis[i][j] + B)
    

    
ans = 0
for i in range(T+1):

    ans = max(ans , tlis[-1][i])
    
print (ans)

Solution (Python):
n, t = list(map(int, input().split()))
dishes = [list(map(int, input().split())) for _ in range(n)]

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



dp = [[-1 for _ in range(t + 1)] for _ in range(n + 1)]

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

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


print(dp[-1][-1])

Solution (Python):
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)))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, T = inpl()
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = inpl()

dp_intime = [[0]*T for _ in range(N+1)]
dp_total = [[0]*T for _ in range(N+1)]
for n in range(1,N+1):
    for t in range(T):
        if A[n-1] > t:
            dp_intime[n][t] = dp_intime[n-1][t]
            dp_total[n][t] = max(B[n-1]+dp_intime[n-1][t], dp_total[n-1][t])
        else:
            dp_intime[n][t] = max(dp_intime[n-1][t], B[n-1]+dp_intime[n-1][t-A[n-1]])
            dp_total[n][t] = max(B[n-1]+dp_intime[n-1][t],
                                 B[n-1]+dp_total[n-1][t-A[n-1]],
                                 dp_total[n-1][t])
print(dp_total[-1][-1])

Solution (Python):
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[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)))

Solution (Python):
import sys
n,t = map(int, input().split())
a = []
b = []
m = []
for i in range(n):
    ai,bi = map(int, input().split())
    m.append((ai,bi))
m.sort()

for i in range(n):
    a.append(m[i][0])
    b.append(m[i][1])
a_mx = max(a)
dp = [0]*(t+a_mx+1)


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



        
print(max(dp))

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n, t = li()
ab = [tuple(li()) for _ in range(n)]
ans = 0


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

for i, (ai, bi) in enumerate(ab):
    for ti in range(t):
        if ti + ai < t:
            dp[i+1][ti + ai] = max(dp[i][ti + ai], dp[i][ti] + bi)
        dp[i+1][ti] = max(dp[i+1][ti], dp[i][ti])


chose = set()
maxtime = dp[n].index(max(dp[n]))

for idx in range(n, 0, -1):
    if dp[idx][maxtime] != dp[idx-1][maxtime]:
        chose.add(idx-1)
        maxtime -= ab[idx-1][0]

allitem = set(range(n))
notchose = allitem - chose

notchosemax = 0
if notchose:
    for i in notchose:
        notchosemax = max(notchosemax, ab[i][1])

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

Solution (Python):
N, T = map(int, input().split())
T -= 1
Meals = sorted([list(map(int, input().split())) for i in range(N)])
dp = [[0] * (T + 1) for i in range(N + 1)]
prev = [[-1] * (T + 1) for i in range(N + 1)]


for i, (cost, value) in enumerate(Meals):
    for j in range(T + 1):
        if j >= cost:
            if dp[i + 1][j] <= dp[i][j - cost] + value:
                dp[i + 1][j] = dp[i][j - cost] + value
                prev[i + 1][j] = j - cost

        if dp[i + 1][j] <= dp[i][j]:
            dp[i + 1][j] = dp[i][j]
            prev[i + 1][j] = j


selected = set()
cur_w = T
for i in range(N - 1, -1, -1):
    if prev[i + 1][cur_w] == cur_w - Meals[i][0]:
        selected.add(i)
    cur_w = prev[i + 1][cur_w]

non_selected = set(list(range(N))) - selected
ans = dp[N][T]
add = 0
for ni in non_selected:
    add = max(add, Meals[ni][1])

print(dp[N][T] + add)

Solution (Python):
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]))

Solution (Python):
def main():
    N, T = map(int, input().split())
    A = [0] * N
    B = [0] * N
    X = [list(map(int, input().split())) for _ in range(N)]
    X.sort(lambda x: x[0])
    for i in range(N):
        A[i], B[i] = X[i]
    M = T+max(A)
    dp = [[(0, 0)] * M for _ in range(2)]
    for i in range(N):
        a, b = A[i], B[i]
        for j in range(M):
            dp[i & 1][j] = dp[(i-1) & 1][j]
        for j in range(a, M):
            t, m = dp[(i-1) & 1][j-a]
            t += b
            m = max(m, a)
            if j - m < T and dp[i & 1][j][0] < t:
                dp[i & 1][j] = (t, m)
    ans = 0
    for i in range(M):
        ans = max(ans, dp[(N-1) & 1][i][0])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import sys
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 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 = list2d(N+1, TMAX, 0)
for i in range(N):
    a, b = AB[i]
    for j in range(TMAX):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j < T:
            dp[i+1][j+a] = max(dp[i+1][j+a], dp[i][j] + b)
print(max(dp[N]))

Solution (Python):
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))

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def knapsack(VW, limit):
    n = len(VW)
    dp = [[0] * (limit+1) for _ in range(n+1)]
    for idx, (v, w) in enumerate(VW, 1):
        for we in range(limit+1):
            dp[idx][we] = dp[idx-1][we]
            if we >= w:
                dp[idx][we] = max(dp[idx][we], dp[idx-1][we-w]+v)
    return dp

def main():
    N, T = map(int, input().split())
    VW = []
    ma = 0
    ama = -1
    for i in range(N):
        w, v = map(int, input().split())
        if ma < v:
            ma = v
            ama = i
        VW.append([v, w])
    dp1 = knapsack(VW, T-1)
    VW.reverse()
    dp2 = knapsack(VW, T-1)
    dp2.reverse()
    VW.reverse()
    
    
    ans = 0
    for (v, w), d1, d2 in zip(VW, dp1[:-1], dp2[1:]):
        
        for i in range(1, T):
            d1[i] = max(d1[i], d1[i-1])
            d2[i] = max(d2[i], d2[i-1])
        for dd1, dd2 in zip(d1, d2[::-1]):
            ans = max(ans, dd1+dd2+v)
    print(ans)


main()

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

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

    
    AB.sort()
    la,lb=AB[-1]

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

    
    AB.sort(lambda x:(x[1],x[0]))
    la,lb=AB[-1]

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

    print(ans)
resolve()

Solution (Python):
import sys
from operator import itemgetter
from heapq import heapify, heappop, heappush
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, T = IL()
ab = [IL() for i in range(N)]
ab.sort(key=itemgetter(0))


dp = [[0]*(T+1+3000+1) for _ in range(N+1)]
ans = 0
for i in range(N):
  for j in range(T+1+3000+1):
    time, deli = ab[i]
    if 0 <= j-time < T:
      dp[i + 1][j] = max(dp[i][j], dp[i][j - time] + deli)
    else:
      dp[i + 1][j] = dp[i][j]
    ans = max(ans, dp[i + 1][j])
print(ans)

Solution (Python):
N, T = map(int, input().split())

items = []
for i in range(N):
	a, b = map(int, input().split())
	items.append((a, -b))

items.sort()

scores = [None] * T
scores[0] = 0
max_d = 0

def search_max():
	max = 0
	for i in range(T):
		s = scores[i]
		if s != None and s > max:
			max = s
	return max

for i in range(N):
	a, b = items[i]
	b = -b
	d = search_max() + b
	if d > max_d:
		max_d = d
	for j in range(T - 1, -1, -1):
		s = scores[j]
		if s != None:
			s += b
			t = j + a
			if t < T:
				prev_s = scores[t]
				if prev_s == None or prev_s < s:
					scores[t] = s

print(max_d)

Solution (Python):
dp = [[-1 for i in range(6005)] for j in range(6005)]


def f(idx, time):
    if time >= T:
        return 0
    if idx >= N:
        return 0
    if dp[idx][time] != -1:
        return dp[idx][time]
    dp[idx][time] = max(f(idx+1, time), B[idx]+f(idx+1, time+A[idx]))
    return dp[idx][time]

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

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

data.sort()
A, B = [], []
for i, j in data:
    A.append(i)
    B.append(j)

for idx in range(N, -1, -1):
    for time in range(T, -1, -1):
        if time == T:
            dp[idx][time] = 0
            continue
        if idx == N:
            dp[idx][time] = 0
            continue
        if A[idx]+time >= T:
            fval = 0
        else:
            fval = dp[idx+1][time+A[idx]]
        dp[idx][time] = max(dp[idx+1][time], B[idx] + fval)

print(dp[0][0])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

main()