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
from operator import itemgetter

input = sys.stdin.readline




TIME = 0
VAL = 1




N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)] + [tuple(int(a) for a in input().split()) for _ in range(N)]


time_value.sort(key = itemgetter(VAL))





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

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

for n in range(1, N + 1):
    dp[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp[n][t] = dp[n - 1][t]
        else:
            dp[n][t] = max(dp[n - 1][t],
                             time_value[n][VAL] + dp[n - 1][t - time_value[n][TIME]])









val_acum = time_value[N][VAL]
t = T - 1  
max_val = val_acum + dp[N - 1][t]

for n in range(N - 1, 0, -1):  
    val_acum += time_value[n][VAL] 
    t -= time_value[n + 1][TIME] 
    if t < 0:
        break
    else:
        max_val = max(max_val, val_acum + dp[n - 1][t])

print(max_val)

Solution (Python):
import sys
from operator import itemgetter

input = sys.stdin.readline




TIME = 0
VAL = 1




N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)] + [None] * (N)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())


time_value.sort(key = itemgetter(VAL))





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

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

for n in range(1, N + 1):
    dp[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp[n][t] = dp[n - 1][t]
        else:
            dp[n][t] = max(dp[n - 1][t],
                             time_value[n][VAL] + dp[n - 1][t - time_value[n][TIME]])









val_acum = time_value[N][VAL]
t = T - 1  
max_val = val_acum + dp[N - 1][t]

for n in range(N - 1, 0, -1):  
    val_acum += time_value[n][VAL] 
    t -= time_value[n + 1][TIME] 
    if t < 0:
        break
    else:
        max_val = max(max_val, val_acum + dp[n - 1][t])

print(max_val)

Solution (Python):
n,t=map(int,input().split())
dp=[[-1 for j in range(2)] for i in range(t+1)]
dp[0][0]=0
d=[]
for i in range(n):
    d.append(list(map(int,input().split())))
d.sort()
for i in range(n):
    for j in range(t,-1,-1):
        for k in range(1,-1,-1):
            if k==0:
                if dp[j][k]>=0 and j+d[i][0]<t:
                    dp[j+d[i][0]][k]=max(dp[j+d[i][0]][k],dp[j][k]+d[i][1])
            if k==1:
                if dp[j][0]>=0:
                    dp[j][k]=max(dp[j][k],dp[j][0]+d[i][1])
ans=0
for i in range(t+1):
    for j in range(2):
        ans=max(ans,dp[i][j])
print(ans)

Solution (Python):
n, t = [int(i) for i in 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])

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

ans = 0

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

print(ans)

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

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

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

ans = 0

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





max_num = [0]*n

for i in reversed(range(n)):
    
    if i == 0:
        break
    if max_num[i] < ab[i][1]:
        max_num[i-1] = ab[i][1]
    else:
        max_num[i-1] = max_num[i]





ans = 0
for i in range(n-1):
    
    if ans < dp[i+1][t-1]+max_num[i]:
        ans = dp[i+1][t-1]+max_num[i]
        
    
    
    
        
print(ans)

Solution (Python):

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

Solution (Python):
import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())


time_value.sort(key = itemgetter(VAL))




dp_table = [[-1] * T for _ in range(N + 1)]


for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  
    val_acum += time_value[n][VAL] 
    t -= time_value[n + 1][TIME] 
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)

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


if __name__ == '__main__':
    solve()

Solution (Python):
import math
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,T=LI()
lis=[tuple(LI()) for i in range(N)]
lis.sort()
RES=[[0]*(T+1) for i in range(N+1)]
for i in range(1, N+1):
    A, B = lis[i-1]
    for t in range(T):
        if (t-A >= 0):
            RES[i][t] = max(RES[i-1][t], RES[i-1][t-A]+B)
        else:
            RES[i][t] = RES[i-1][t]
    RES[i][T] = max(RES[i-1][T], RES[i-1][T-1]+B)

print(RES[i][T])

Solution (Python):
n,t=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(n)]
AB.sort()
ma=AB[-1][0]
dp=[0]*(t+ma)    
for a,b in AB:
    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))

Solution (Python):
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])


dp = [[0] * (W + 1) for i in range(N + 1)]


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)

Solution (Python):
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])


dp = [[0] * (W + 1) for i in range(N + 1)]


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):
    for j in range(W):
        ans = max(ans, dp[i][j] + vi)

print(ans)

Solution (Python):
N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]




dp1 = [[0] * (W + 1) for i in range(N + 2)]
dp2 = [[0] * (W + 1) for i in range(N + 2)]


for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp1[i + 1][j + wi] = max(dp1[i + 1][j + wi], dp1[i][j] + vi)
        dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j])


for i in range(N + 1, 1, -1):
    wi, vi = items[i - 2]
    for j in range(W + 1):
        if j + wi <= W:
            dp2[i - 1][j + wi] = max(dp2[i - 1][j + wi], dp2[i][j] + vi)
        dp2[i - 1][j] = max(dp2[i][j], dp2[i - 1][j])



ans = 0

for i, (wi, vi) in enumerate(items, start=1):
    for j in range(W):
        ans = max(ans, dp1[i - 1][j] + dp2[i + 1][W - j - 1] + vi)

print(ans)

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

ans = int(ans)
print(ans)

Solution (Python):
n, t = map(int, input().split())
a = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  a[i][0], a[i][1] = x, y
a = sorted(a, key=lambda x: x[0], reverse=True)
dp = [[0 for i in range(t+1)] for j in range(n+1)]

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

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

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


if __name__ == '__main__':
    solve()

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
N,T = map(int,readline().split())
m = map(int,read().split())
AB = sorted(zip(m,m))
 
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)
 
answer = 0
for i,(a,b) in enumerate(AB):
    np.maximum(dp[a:], dp[:-a] + b, out = dp[a:])
    x = dp.max() + can_add[i]
    if answer < x:
        answer = x
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
N,T = map(int,readline().split())
m = map(int,read().split())
AB = sorted(zip(m,m))
 
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)
 
answer = 0
for i,(a,b) in enumerate(AB):
    np.maximum(dp[a:], dp[:-a] + b, out = dp[a:])
    x = dp.max() + can_add[i]
    if answer < x:
        answer = x
print(answer)

Solution (Python):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))




deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = np.zeros(T, np.int64)
for i in range(N - 1):
    dp[ls[i][0]:] = np.maximum(dp[ls[i][0]:], dp[:-ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))

ls.sort()

deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

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

if __name__=='__main__':
    main()

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

Solution (Python):
import sys

import numpy as np

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

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

Solution (Python):
import numpy as np
N,T = map(int, raw_input().split())
L = [map(int, raw_input().split()) for i in range(N)]
d=np.zeros(10000,int)
for a,b in sorted(L):
    t=d[a:T+a]
    np.maximum(t,d[:T]+b,t)
print(max(d))

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

ab_list.sort(key=lambda x: x[0])
    
dp = [[0 for _ in range(T+1+3000)] for _ in range(N+1)]

for i in range(N):
    a, b = ab_list[i]
    for j in range(T+1):
        if j-a >= 0:
            dp[i+1][j] = max(dp[i][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
    for k in range(T+1,T+1+3000):
        
        if k-a >= 0 and k-a <= T-1:
            dp[i+1][k] = max(dp[i][k-a] + b, dp[i][k])
        else: 
            dp[i+1][k] = dp[i][k]
            
print(max(dp[-1]))

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

Solution (Python):
import numpy as np


def solve():


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

    A = []
    B = []

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

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

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

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

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

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


if __name__ == "__main__":
    solve()

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

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

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

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

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)

Solution (Python):


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








val.sort()
A=[v[0] for v in val]
B=[v[1] for v in val]

















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

for itemp in range(T):
    i=itemp
    if i>=A[0]:
        temp[i][0]=B[0]
    for jtemp in range(N-1):
        j=jtemp+1
        jbfo=temp[i][j-1]
        ijnow=temp[i][j]
        
        if i>0:
            temp[i][j]=max(ijnow,temp[i-1][j])
            
        temp[i][j]=max(ijnow,jbfo)
        if A[j]<T-i:
            temp[i+A[j]][j]=max(jbfo+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(jbfo+B[j],temp[T][j])
print(int(max(temp[-1][:])))

Solution (Python):
def get():
    return map(int,input().split())

N,W=get()
x=[[0,0] for _ in range(N)]
for i in range(N):
    x[i][0],x[i][1]=get()
x.sort()
w=[0]*N
v=[0]*N
for i in range(N):
    w[i], v[i] = x[i]

if W>=sum(w):
    print(sum(v))
else:
    dp=[0]*(W+1)
    for i in range(N):
        for j in range(W+w[i]-1,w[i]-1,-1):
            if j >= W:
                dp[W]=max(dp[W],dp[j-w[i]]+v[i])
            else:
                dp[j]=max(dp[j],dp[j-w[i]]+v[i])
    print(dp[W])

Solution (Python):
n, t = map(int, input().split())
w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
w, v = zip(*sorted(zip(w, v)))
dp = [[0] * (t + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(t):
        if j >= w[i]:
            dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
    dp[i + 1][t] = dp[i + 1][t] = max(dp[i][t - 1] + v[i], dp[i][t])
print(dp[n][t])

Solution (Python):
import sys
from operator import itemgetter as ITEM
input = sys.stdin.readline

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

vA.sort(key=ITEM(0))







dp = [[0,]*(T+2)]
dp_apnd = dp.append

for A,B in vA:
  pDP = dp[-1]
  
  nDP = dp[-1][:]
  
  for t in range(T):
    nDP[min(t+A,T+1)] = max(pDP[min(t+A,T+1)], pDP[t]+B)
  dp_apnd(nDP)
  

print(max(dp[-1]))

Solution (Python):
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)]
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]
print(max(dp[-1]))

Solution (Python):

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

Solution (Python):
import sys


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


if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np

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

A = []
B = []

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

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

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

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

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

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

Solution (Python):
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
dp=[[0 for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
foodmax=[0]*n
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
foodmax[-1]=food[-1][1]
for i in range(n-1)[::-1]:
  foodmax[i]=max(foodmax[i+1],food[i][1])
foodmax+=[0]
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-food[i][0]]+food[i][1])
      
ans=0
for i in range(n):
  if ans<dp[i+1][t-1]+foodmax[i+1]:
    ans=dp[i+1][t-1]+foodmax[i+1]
print(ans)

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

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

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)

last = [0]*N
last[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  last[i] = max(last[i+1], ls[i][1])

ans = 0

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

print(ans)

Solution (Python):

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

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

def chmax(a,b):
    if a < b:
        return b
    else:
        return a 
    
for i in range(N):
    for t in range(T): 
        if t+ab[i][0] <= T-1:
        	dp[i+1][t+ab[i][0]] =chmax(dp[i+1][t+ab[i][0]],dp[i][t]+ab[i][1])
        
        dp[i+1][t] = chmax(dp[i+1][t],dp[i][t])



ans = 0
for i in range(N):
    ans = chmax(ans,dp[i][T-1]+ab[i][1])
    
print(ans)

Solution (Python):

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

a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
    
dp = [[0 for j in range(t)] for _ in range(n+1)]

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



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

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for _ in range(t)] for _ in range(n+1)]
 
for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
for i in range(n):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for _ in range(t)] for _ in range(n+1)]
 
for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t)] for 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]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t)] for 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]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t)] for 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]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Solution (Python):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t+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]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
dp=[[0 for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
foodmax=[0]*n
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
foodmax[-1]=food[-1][1]
for i in range(n-1)[::-1]:
  foodmax[i]=max(foodmax[i+1],food[i][1])
foodmax+=[0]
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-food[i][0]]+food[i][1])
ans=0
for i in range(n):
  if ans<dp[i+1][t-1]+foodmax[i+1]:
    ans=dp[i+1][t-1]+foodmax[i+1]
print(ans)

Solution (Python):
from numpy import*
(n,t),*l=loadtxt(open(0)).tolist()
d=zeros(1e4,int)
for a,b in sorted(l):p=d[a:a+t];fmax(p,d[:t]+b,p)
print(max(d))

Solution (Python):
inf = float('inf')

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

AB = sorted(AB, key=lambda x:x[0])
A = [a for a, b in AB]
B = [b for a, b in AB]

M = T + max(A)
dp = [[-inf] * (M) for _ in range(N+1)]
dp[0][0] = 0

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

ans = max(dp[N])
print(ans)

Solution (Python):
from numpy import*
(N,T),*L=loadtxt(open(0)).tolist()
d=zeros(1e4,int)
for w,v in sorted(L):t=d[w:T+w];maximum(t,d[:T]+v,t)
print(max(d))

Solution (Python):
from numpy import*
(N,T),*L=loadtxt(open(0)).tolist()
d=zeros(1e4,int)
for w,v in sorted(L):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

Solution (Python):
from numpy import*
(N,T),*L=loadtxt(open(0),int).tolist()
d=zeros(1e4,int)
for w,v in sorted(L):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

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

Solution (Python):
from numpy import*
N,T,*L=int_(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=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))