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):
words = lambda t : list(map(t, input().split()))
n,t = words(int)
xys = []
for i in range(n):
    x,y = words(int)
    xys.append((x,y))

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

def show(dp):
  for row in dp:
      print(row)

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


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

print(ans)

Solution (Python):

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

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

    dpt[0][0]=0

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




    print(max(dpt[-1]))



if __name__ == "__main__":

    resolve()

Solution (Python):
from numpy import*
N,T,*L=int64(open(0).read().split())
d=zeros(1e4,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))

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

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

ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

for i in range(N):
  a, b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)
    
pre = [0]*N
pre[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  pre[i] = max(pre[i+1], ls[i][1])
    
ans = 0
for i in range(N-1):
  ans = max(ans, max(dp[i+1])+pre[i+1])
ans = max(ans, max(dp[-1]))
print(ans)

Solution (Python):
N, T = map(int, input().split())
D = [0 for i in range(N)]
maxA = 0
for i in range(N):
    A, B = map(int, input().split())
    D[i] = [A,B]
G = sorted(D)
maxT = T + G[N-1][0]
dp = [[0 for j in range(maxT)] for i in range(N)]
gans = G[0][1]
dp[0][G[0][0]] = G[0][1]
for i in range(1,N):
    for j in range(maxT):
        nowans = dp[i-1][j]
        if j >= G[i][0] and j <= T-1+G[i][0]:
            nowans = max(nowans, dp[i-1][j-G[i][0]] + G[i][1])
        dp[i][j] = nowans
        gans = max(gans, nowans)

print(gans)

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


N, T = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])


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


bmax_res = [0]*N
bmax = -1
for i in range(N-1, 0, -1):
    a, b = AB[i]
    bmax = max(bmax, b)
    bmax_res[i-1] = bmax



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

res = 0

for i in range(1,N+1):
    a, b = AB[i-1]
    for j in range(1,T+1):
        if a <= j:
            DP[i][j] = max(DP[i-1][j-a] + b, DP[i-1][j])
        else:
            DP[i][j] = max(DP[i-1][j], DP[i][j])
    res = max(res, DP[i][T-1]+bmax_res[i-1])
print(res)

Solution (Python):
n, t = map(int, input().split())
lst = []
for i in range(n):
    lsti = list(map(int, input().split()))
    lst.append(lsti)

lst.sort(key=lambda x: x[0])
a, b = [], []
for i in range(n):
    lsti = lst[i]
    a.append(lsti[0])
    b.append(lsti[1])


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


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


kouho = []
for i in range(n):
    kouho.append(dp[i][t-1]+b[i])
kouho.append(dp[n][t-1])
print(max(kouho))

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

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

Solution (Python):
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, T = map(int, readline().split())
m = map(int, read().split())
AB = sorted(zip(m, m))

dp = np.zeros(T, np.int64)

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)

Solution (Python):
import sys

input = sys.stdin.readline

N, T = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda k: k[0])

resbmax = [0]*N
bmax = 0
for i in range(N-1,0,-1):
	bi = AB[i][1]
	bmax = max(bmax,bi)
	resbmax[i-1] = bmax

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

ans = 0
i = 0
for ai, bi in AB:
	for j in range(T):
		if j>=ai:
			dp[i+1][j] = max(dp[i][j-ai]+bi, dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

	ans = max(ans, dp[i+1][-1]+resbmax[i])
	i += 1

print(ans)

Solution (Python):

import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, t = LMIIS()
    ab = XLMIIS(n)
    ab.sort()

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

    ans = 0
    for i in range(n):
        ans = max(ans, dp1[i][t-1] + ab[i][1])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, t = LMIIS()
    ab = XLMIIS(n)

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


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

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

if __name__ == '__main__':
    main()

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

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

for food in range(n-1):
    for time in range(t):
        if time - foods[food][0] >= 0:
            dp[food+1][time] = max(dp[food][time], dp[food][time-foods[food][0]] + foods[food][1])
        else:
            dp[food+1][time] = dp[food][time]

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


print(ans)

Solution (Python):
n, t = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort()
a_max = x[-1][0]

dp_pre = [0 for j in range(t + a_max)]
dp = [0 for j in range(t + a_max)]
for ai, bi in x:
    for j in range(ai):
        dp[j] = dp_pre[j]
    for j in range(ai, t + ai):
        dp[j] = max(dp_pre[j], dp_pre[j - ai] + bi)
    for j in range(t + ai, t + a_max):
        dp[j] = dp_pre[j]
    dp_pre, dp = dp, dp_pre
print(max(dp_pre))

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

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)

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


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

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

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

Solution (Python):
N, M = map(int, input().split())
D = []
for i in range(N):
    t, v = map(int, input().split())
    D.append((t, v))

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

DP1 = [[0 for j in range(M)] for i in range(N + 2)]
DP2 = [[0 for j in range(M)] for i in range(N + 2)]

for i in range(1, N + 1):
    for j in range(1, M):
        if j - D[i - 1][0] >= 0:
            DP1[i][j] = max(DP1[i - 1][j], DP1[i - 1][j - D[i - 1][0]] + D[i - 1][1])
        else:
            DP1[i][j] = DP1[i - 1][j]

for i in range(N, 0, -1):
    for j in range(1, M):
        if j - D[i - 1][0] >= 0:
            DP2[i][j] = max(DP2[i + 1][j], DP2[i + 1][j - D[i - 1][0]] + D[i - 1][1])
        else:
            DP2[i][j] = DP2[i + 1][j]

mv = 0
for i in range(N):
    for j in range(M):
        mv = max(DP1[i][j] + DP2[i + 2][M - 1 - j] + D[i][1], mv)

print(mv)

Solution (Python):
import numpy as np

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

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

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

ab.sort()

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

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

ab.sort()

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

ans = 0
i = 0
for a, b in ab:
    ans = max(ans, max(dp[i]) + b)
    if a < t:
        dp[i+1][a] = max(dp[i][a], b)
    for j in range(1, t):
        if dp[i][j] > 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if a + j < t:
                dp[i+1][a+j] = max(dp[i][a+j], dp[i][j] + b)
    i += 1

ans = max(ans, max(dp[n]))

print(ans)

Solution (Python):
N, M = map(int, input().split())
D = []
for i in range(N):
    t, v = map(int, input().split())
    D.append((t, v))

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

DP = [[0 for j in range(M)] for i in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, M):
        if j - D[i - 1][0] >= 0:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - D[i - 1][0]] + D[i - 1][1])
        else:
            DP[i][j] = DP[i - 1][j]
mv = 0
for l in range(N): 
    mv = max(DP[l][M - 1] + D[l][1], mv)

print(mv)

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

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

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

if __name__=="__main__":
	main()

Solution (Python):


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

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

    return res




print(main())

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

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

Solution (Python):
N,T=map(int,input().split())
x=[(0,0)] 
for i in range(1,N+1): 
    x.append(tuple(map(int,input().split()))) 

x.sort()


dp1=[[0 for j in range(T)] for i in range(N+2)] 
for i in range(1,N+1): 
    for j in range(T): 
        if x[i][0]>j:
            dp1[i][j]=dp1[i-1][j]
        else:
            dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-x[i][0]]+x[i][1])

cans=[dp1[i-1][T-1]+x[i][1] for i in range(1,N+1)]



ans=max(cans)

print(ans)

Solution (Python):
N,T=map(int,input().split())
x=[None] 
for i in range(1,N+1): 
    x.append(tuple(map(int,input().split()))) 


dp1=[[0 for j in range(T)] for i in range(N+2)] 
for i in range(1,N+1): 
    for j in range(T): 
        if x[i][0]>j:
            dp1[i][j]=dp1[i-1][j]
        else:
            dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-x[i][0]]+x[i][1])



dp2=[[0 for j in range(T)] for i in range(N+2)] 
for i in range(N,0,-1): 
    for j in range(T):
        if x[i][0]>j:
            dp2[i][j]=dp2[i+1][j]
        else:
            dp2[i][j]=max(dp2[i+1][j],dp2[i+1][j-x[i][0]]+x[i][1])



cans=[0 for i in range(N+1)] 
for i in range(1,N+1):
    cans[i]=max([dp1[i-1][j]+dp2[i+1][T-1-j] for j in range(T)])+x[i][1]



ans=max(cans)

print(ans)

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

Solution (Python):
import numpy as np
N, T = 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)

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







import numpy as np



















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



if __name__ == '__main__':
	main()

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

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)

Solution (Python):
def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  

            
            
            
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            
            
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


























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


def main():
	n, t = map(int, input().split())
	AB = []
	A = []
	B = []
	for _ in range(n):
		a, b = map(int, input().split())
		AB.append((a, b))
	AB.sort()
	for a,b in AB:
		A.append(a)
		B.append(b)
	dp= knapsack(n, t, A, B)
	
	ans=0
	for i in range(n):
		ans=max(ans,dp[i][t-1] + AB[i][1])
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):


import sys
N,T=map(int, sys.stdin.readline().split())
AB=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

AB.sort()

N=6005
dp=[ None for _ in range(N) ]
dp[0]=0

for a,b in AB:
    for i in range(N-1,-1,-1):
        if dp[i] is not None and i<T:
                dp[i+a]=max(dp[i+a],dp[i]+b)

print max(dp)

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

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

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

if __name__=="__main__":
    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))

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

if __name__=="__main__":
	main()

Solution (Python):
def main():
    N, T = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    l.sort(key=lambda x: x[0])
    m = [[0] * T for _ in range(N)]
    m[0] = [0 if t < l[0][0] else l[0][1] for t in range(T)]
    for i in range(1, N):
        t, v = l[i]
        for j in range(min(t, T)):
            m[i][j] = m[i-1][j]
        for j in range(t, T):
            m[i][j] = max(l[i][1] + m[i-1][j-t], m[i-1][j])
    return max(l[i][1] + m[i-1][-1] if i > 0 else l[i][1] for i in range(N))

print(main())

Solution (Python):
N, T=map(int, input().split())
lst=[list(map(int, input().split())) for _ in range(N)]
MAXN, MAXT=3001, 3001
dp1=[[0 for _ in range(MAXT)] for _ in range(MAXN+1)]
dp2=[[0 for _ in range(MAXT)] for _ in range(MAXN+1)]
for i in range(1, N+1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp1[i][j]=max(dp1[i-1][j], dp1[i-1][j-A]+B) if j>=A else dp1[i-1][j]
for i in range(N, 0, -1):
  A, B=lst[i-1]
  for j in range(1, MAXT):
    dp2[i][j]=max(dp2[i+1][j], dp2[i+1][j-A]+B) if j>=A else dp2[i+1][j]
ans=dp1[N-1][T-1]+lst[-1][1]
for i in range(1, N):
  A, B=lst[i-1]
  for j in range(T):
    ans=max(ans, dp1[i-1][j]+dp2[i+1][T-1-j]+B)
print(ans)

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

Solution (Python):
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 + 1)
    for a, b in ab:
        dp[-1] = max(dp[-1], dp[-2] + b)
        for i in range(t - a - 1, -1, -1):
            dp[i + a] = max(dp[i + a], dp[i] + b)
    print(dp[-1])


if __name__ == '__main__':
    solve()

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):
def solve():
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dishes.sort(key=attrgetter('cost'))

    dp = [0] * t
    

    ret = 0
    for dish in dishes:
        for cost_ in range(t - 1, -1, -1):
            ret = max(ret, dp[cost_] + dish.pt)
            if cost_ >= dish.cost:
                dp[cost_] = max(dp[cost_], dp[cost_ - dish.cost] + dish.pt)

    return ret


print(solve())

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

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))

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

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

for i in range(n):
    for j in range(t-1):
        if ab[i][0] <= j:
            dp1[i+1][j] = max(dp1[i][j],dp1[i][j-ab[i][0]]+ab[i][1])
        else:
            dp1[i+1][j] = dp1[i][j]
            
        if ab_r[i][0] <= j:
            dp2[i+1][j] = max(dp2[i][j],dp2[i][j-ab_r[i][0]]+ab_r[i][1])
        else:
            dp2[i+1][j] = dp2[i][j]
            
m=0
for i in range(1,n+1):
    for j in range(t-1):
        m=max(m,dp1[i-1][j]+dp2[n-i][t-1-j]+ab[i-1][1])
print(m)

Solution (Python):
def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp = [[0] * 2 for _ in range(t)]
    

    for dish in dishes:
        for cost_ in range(t - 1, -1, -1):
            dp[cost_][True] = max(dp[cost_][True], dp[cost_][False] + dish.pt)
            if cost_ >= dish.cost:
                dp[cost_][False] = max(dp[cost_][False], dp[cost_ - dish.cost][False] + dish.pt)
                dp[cost_][True] = max(dp[cost_][True], dp[cost_ - dish.cost][True] + dish.pt)

    return max(dp[cost_][True] for cost_ in range(t))


print(solve())

Solution (Python):
import numpy as np


if __name__ == '__main__':
    
    N, T = 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)

Solution (Python):
def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp_ht = [[0] * t for _ in range(n + 2)]  
    dp_th = [[0] * t for _ in range(n + 2)]  
    

    for dish in dishes:
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_ht[dish.idx][cost_] = max(dp_ht[dish.idx - 1][cost_],
                                             dp_ht[dish.idx - 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_ht[dish.idx][cost_] = dp_ht[dish.idx - 1][cost_]

    for dish in reversed(dishes):
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_th[dish.idx][cost_] = max(dp_th[dish.idx + 1][cost_],
                                             dp_th[dish.idx + 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_th[dish.idx][cost_] = dp_th[dish.idx + 1][cost_]

    ret = 0
    for last_dish in dishes:
        for cost_ in range(t):
            ret = max(ret, dp_ht[last_dish.idx - 1][cost_] + dp_th[last_dish.idx + 1][t - 1 - cost_] + last_dish.pt)
    return ret


print(solve())

Solution (Python):
def knapsack(n, w, info):
    
    
    dp = [[0]*(w + 1) for i in range(n + 1)]
 
    for i in range(n):
        for j in range(w + 1):
            weight, value = info[i]
            if j < weight:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight] + value)
    return dp
  
n, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

dp = knapsack(n, t, info)
dq = knapsack(n, t, info[::-1])
ans = 0
for i in range(n):
    for j in range(t):
        ans = max(dp[i][j] + dq[n-(i+1)][t-(j+1)] + info[i][1], ans)
print(ans)