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 numpy as np

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

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

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

Solution (Python):
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = range(W, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            if weight - weight_list[item] < T:
                dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return max(dp[T:])

import sys
input = sys.stdin.readline


def max2(x, y):
    return x if x > y else y

def min2(x, y):
    return x if x < y else y


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

price_list = []
weight_list = []
data = []
for _ in range(N):
    weight, price = map(int, input().split())
    data.append((weight, price))
data.sort()
for weight, price in data:
    price_list.append(price)
    weight_list.append(weight)

max_weight = max(weight_list)

W = T + max_weight - 1

print(knapsack_weight(single=True))

Solution (Python):
def solve():
  N, T = map(int, input().split())
  A = [list(map(int, input().split())) for _ in range(N)] 
  A.sort()
  dp = [[0]*(T+1) for _ in range(N+1)]
  for i in range(N):
    for j in range(0,T+1):
      dp[i+1][j] = max(dp[i+1][j],dp[i][j])
      if j<T:
        t = min(T,j+A[i][0])
        dp[i+1][t] = max(dp[i+1][t],dp[i][j]+A[i][1])
  ans = dp[-1][-1]
  return ans
print(solve())

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

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,T = IL()
data = ILL(N)
data.sort()

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

for i in range(1,N+1):
  tt,vv = data[i-1]
  for t in range(1,T):
    if t >= tt:
      dp[i][t] = max(dp[i-1][t], dp[i-1][t-tt]+vv)
    else:
      dp[i][t] = dp[i-1][t]
  dp[i][T] = max(dp[i-1][T], dp[i-1][T-1]+vv)
      
print(dp[-1][-1])

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, t = ns()
    d = [na() for _ in range(n)]
    d.sort()

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

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

    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):

import sys

input = sys.stdin.buffer.readline

n, t = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
rAB = AB[::-1]
dp1 = [[0] * (t + 1) for _ in range(n + 1)]
dp2 = [[0] * (t + 1) for _ in range(n + 1)]

for i in range(n):
    ni = i + 1
    a, b = AB[i]
    for j in range(t + 1):
        nj = j + a
        if nj <= t:
            dp1[ni][nj] = max(dp1[i][j] + b, dp1[ni][nj])
        dp1[ni][j] = max(dp1[ni][j], dp1[i][j])
    c, d = rAB[i]
    for j in range(t + 1):
        nj = j + c
        if nj <= t:
            dp2[ni][nj] = max(dp2[i][j] + d, dp2[ni][nj])
        dp2[ni][j] = max(dp2[ni][j], dp2[i][j])

ans = 0


for i in range(n):
    for j in range(t):
        temp = AB[i][1]
        if i >= 1:
            temp += dp1[i][j]
        if n - i - 1 >= 1:
            temp += dp2[n - i - 1][t - 1 - j]
        ans = max(ans, temp)
print(ans)

Solution (Python):
def resolve():
    N, T = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    dp = [[0 for _ in range(T)] for __ in range(N)]
    for i in range(1, N):
        time, value = AB[i-1]
        for j in range(T-1, -1, -1):
            dp[i][j] = dp[i-1][j]
            if j >= time:
                dp[i][j] = max(dp[i][j], dp[i-1][j-time]+value)
    print(max(dp[i][T-1]+AB[i][1] for i in range(N)))
    
if __name__ == "__main__":
    resolve()

Solution (Python):
N,T=map(int,input().split())
A=[]
for i in range(N):
  a,b=map(int,input().split())
  A.append((a,b))
A=sorted(A)
dp=[[0]*(T) for j in range(N)]


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

bma=[0]
t=0
for i in range(N-1,0,-1):
  t=max(t,A[i][1])
  bma=[t]+bma

ans=0
for i in range(N):
  d=dp[i][-1]+bma[i]
  ans=max(d,ans)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

Solution (Python):

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 = []
    for i in range(N):
        AB.append(LMIIS())
    
    AB.sort()
    dp = [-1] * (T+3000)
    dp[0] = 0
    for a,b in AB:
        tmpdp = dp[:]
        for j in range(T):
            if dp[j] != -1:
                tmpdp[j+a] = max(dp[j+a],dp[j]+b)
        dp = tmpdp
    print(max(dp))






if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, A = getNM()
w = []
v = []
for i in range(N):
    a, b = getNM()
    w.append(a)
    v.append(b)


def knapsack_6(N, upper, limit, weight, value):
    dp = [[[0] * (upper + 1) for i in range(limit + 1)] for j in range(N + 1)]

    for i in range(N):
        
        for j in range(limit + 1):
            for l in range(upper + 1):
                
                dp[i + 1][j][l] = dp[i][j][l]
                
                if l >= weight[i]:
                    dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                
                if l >= 1 and limit >= 1:
                    
                    dp[i + 1][j - 1][l] = max(dp[i + 1][j - 1][l], dp[i][j - 1][l], dp[i][j][l - 1] + value[i])
    return dp[N][0][upper]

print(knapsack_6(N, A, 1, w, v))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, A = getNM()
w = []
v = []
for i in range(N):
    a, b = getNM()
    w.append(a)
    v.append(b)


def knapsack_6(N, upper, limit, weight, value):
    dp = [[[0] * (upper + 1) for i in range(limit + 1)] for j in range(N + 1)]

    for i in range(N):
        
        for j in range(limit + 1):
            for l in range(upper + 1):
                
                dp[i + 1][j][l] = dp[i][j][l]
                
                if l >= weight[i]:
                    dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                
                if l >= 1 and limit >= 1:
                    dp[i + 1][j - 1][l] = max(dp[i + 1][j - 1][l], dp[i][j - 1][l], dp[i][j][l - 1] + value[i])
    return dp[N][0][upper]

print(knapsack_6(N, A, 1, w, v))

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

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

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

b_max = [0]
tmp = 0
for i in range(n-1, -1, -1):
    tmp = max(tmp, ab[i][1])
    b_max = [tmp] + b_max

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

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(n)]
    AB.sort()

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = dp[i - 1][j]
        for k in range(i, n):
            _, b = AB[k]
            res = max(res, dp[i][j - 1] + b)
    print(res)


if __name__ == '__main__':
    resolve()

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

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

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(6001):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])
        if t < T: dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])


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

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

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(6001):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])
    for t in range(T+1):
        if t < T:
            
            dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])


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

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

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

print(ans)

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

dp = [[0 for _ in range(T + 3001)] for _ in range(N + 1)]
for i in range(1, N + 1):
    a, b = a_list[i - 1]
    for j in range(T + 3001):
        dp[i][j] = dp[i - 1][j]
    for j in range(T):
        dp[i][j + a] = max(dp[i - 1][j + a], dp[i - 1][j] + b)
print(max(dp[-1]))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))

dp = [[0] * (t+3001) for _ 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]
    for j in range(t):
        dp[i][j+a] = max(dp[i-1][j+a], dp[i-1][j] + b)

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

Solution (Python):
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

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

    for i in range(N-1):
        for j in range(T):
            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j])
            if 0 <= j - A[i]:
                dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j - A[i]] + B[i])

    for i in range(2, N+1)[::-1]:
        for j in range(T):
            dp2[i][j] = max(dp2[i][j], dp2[i+1][j])
            if 0 <= j - A[i-1]:
                dp2[i][j] = max(dp2[i][j], dp2[i+1][j - A[i-1]] + B[i-1])

    ans = 0
    for i in range(N):
        for j in range(T-1):
            ans = max(ans, dp1[i][j] + dp2[i+2][T - 1 - j] + B[i])
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, T = mapint()
AB = [list(mapint()) for _ in range(N)]
AB.sort()
maxtime = AB[-1][0]
Bs = [b for a, b in AB]
dp = [0]*(T)

ans = 0
for n in range(N-1):
    a, b = AB[n]
    newdp = [0]*(T)
    for i in range(T):
        if a<=i and i-a<T:
            newdp[i] = max(dp[i], dp[i-a]+b)
    dp = newdp
    ans = max(ans, max(dp)+max(Bs[n+1:]))

print(ans)

Solution (Python):
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()

    ans = 0
    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - AB[i][0]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + AB[i][1])
            else:
                dp1[i+1][j] = dp1[i][j]
        ans = max(ans, dp1[i][T-1] + AB[i][1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - A[i]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + B[i])
            else:
                dp1[i+1][j] = dp1[i][j]
    dp2 = [[0]*(T+1) for _ in range(N+2)]
    for i in range(1, N+1)[::-1]:
        for j in range(T):
            t = j - A[i-1]
            if 0 <= t:
                dp2[i][j] = max(dp2[i+1][j], dp2[i+1][t] + B[i-1])
            else:
                dp2[i][j] = dp2[i+1][j]
    ans = 0
    for i in range(N):
        for j in range(T):
            ans = max(ans, dp1[i][j] + dp2[i+2][T - 1 - j] + B[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    ans = 0
    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - A[i]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + B[i])
            else:
                dp1[i+1][j] = dp1[i][j]
        ans = max(ans, dp1[i][T-1] + B[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j])

            t = j - A[i]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i+1][j], dp1[i][t] + B[i])
    ans = 0
    for i in range(N):
        ans = max(ans, dp1[i][T-1] + B[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
def main(N, T, AB):
    dpL = [[0] * (T + 1) for _ in range(N + 2)]
    for i in range(1, N + 1):
        a, b = AB[i - 1]
        for t in range(T):
            dpL[i][t] = dpL[i - 1][t]
            if t >= a:
                dpL[i][t] = max(dpL[i][t], dpL[i - 1][t - a] + b)

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

    ans = 0
    for i in range(1, N + 1):
        a, b = AB[i - 1]
        for t in range(T):
            ans = max(ans, dpL[i - 1][t] + dpR[i + 1][T - 1 - t] + b)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    main(N, T, AB)

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


N,W = map(int,readline().split())
AB = [tuple(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(dp[W])

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: (x[0],x[1]))
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))

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

A = [];B = []
for i in range(N):
  A.append(X[i][0])
  B.append(X[i][1])
dp = [[0 for _ in range(T)] for _ in range(N+1)]

ans = 0
for i in range(N):
  time, aji = X[i]
  for j in range(T):
    if j-time >= 0:
      dp[i+1][j] = max(dp[i][j-time] + aji,dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
  
  if i < N-1:
    last = max(B[i+1:])
  else:
    last = 0
  
  ans = max(ans,dp[i+1][T-1]+last)
print(ans)

Solution (Python):
def solve():
  ans = 0
  N, T = map(int, input().split())
  A = [list(map(int, input().split())) for _ in range(N)]
  A.sort()
  dp = [[0]*(T+A[-1][0]) for _ in range(N+1)]
  for i in range(1,N+1):
    for t in range(1,T+A[-1][0]):
      if t<A[i-1][0] or t>=T+A[i-1][0]:
        dp[i][t] = max(dp[i-1][t],dp[i][t-1])
      else:
        dp[i][t] = max([dp[i-1][t],dp[i][t-1],dp[i-1][t-A[i-1][0]]+A[i-1][1]])
  ans = max(dp[-1])
  return ans
print(solve())

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


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

for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])

ma = 0

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

print(ma)

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+1)]
dp[0][0]=0
ans=0
for i in range(n):
  for j in range(6007):
    dp[i+1][j]=max(dp[i+1][j],dp[i][j])
    if j<t:dp[i+1][j+ab[i][0]]=max(dp[i][j]+ab[i][1],dp[i][j+ab[i][0]])
    ans=max(ans,dp[i+1][j])
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, M = getNM()
query = [getList() for i in range(N)]

w = []
v = []
w_rev = []
v_rev = []
for i in range(N):
    w.append(query[i][0])
    v.append(query[i][1])
    w_rev.append(query[N - i - 1][0])
    v_rev.append(query[N - i - 1][1])

def knapsack_1(N, limit, weight, value):
    dp = [[0] * (limit + 1) for i in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(limit + 1):
            if weight[i] <= j:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
            else:
                dp[i + 1][j] = dp[i][j]
    return dp

dp_1 = knapsack_1(N, M, w, v)
dp_2 = knapsack_1(N, M, w_rev, v_rev)


ans = 0
for i in range(1, N + 1):
    opt = 0
    for j in range(M):
        if i == 1:
            o = query[i - 1][1] + dp_2[N - i][M - j - 1]
        elif i == N:
            o = dp_1[i - 1][j] + query[i - 1][1]
        else:
            
            
            
            o = dp_1[i - 1][j] + query[i - 1][1] + dp_2[N - i][M - j - 1]
        opt = max(opt, o)
    ans = max(ans, opt)
print(ans)