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
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def main():
    N,T = map(int,input().split())        
    AB = [(0,0)] + [tuple(map(int,input().split())) for _ in range(N)]

    
    

    
    
    
    
    

    
    dp1 = [[0 for _ in range(T+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        a,b = AB[i]
        for j in range(T+1):
            
            if j >= a:
                dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-a] + b)
            
            else:
                dp1[i][j] = dp1[i-1][j]

    
    dp2 = [[0 for _ in range(T+1)] for _ in range(N+2)]
    for i in range(N,0,-1):
        a,b = AB[i]
        for j in range(T+1):
            
            if j >= a:
                dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-a] + b)
            
            else:
                dp2[i][j] = dp2[i+1][j]
    
    
    ans = 0
    for i in range(1,N+1):
        a,b = AB[i]
        for j in range(T):
            ans = max(ans, dp1[i-1][j] + b + dp2[i+1][T-1-j])
    
    print(ans)

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):
                
                if j < limit:
                    dp[i + 1][j + 1][l] = dp[i][j + 1][l]
                    if l >= weight[i]:
                        dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                        dp[i + 1][j + 1][l] = max(dp[i][j + 1][l], dp[i][j][l - 1] + value[i])
                    elif l >= 1:
                        dp[i + 1][j][l] = max(dp[i + 1][j][l], dp[i][j][l])
                        dp[i + 1][j + 1][l] = max(dp[i + 1][j + 1][l], dp[i][j][l - 1] + value[i])
                    else:
                        dp[i + 1][j][l] = dp[i][j][l]
                
                else:
                    if l >= weight[i]:
                        dp[i + 1][j][l] = max(dp[i + 1][j][l], dp[i][j][l - weight[i]] + value[i])
    return dp[N][limit][upper]

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

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+3001) for _ in range(n+1)]

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

ans = 0

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

print(ans)

Solution (Python):




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

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

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

dp = [0]*T
counter = 0
for i in range(N-1):
    A,B = li[i]
    counter = max(counter,max(dp)+B)
    if A>T-1:
        continue
    for t in range(T-A-1,-1,-1):
        dp[t+A]=max(dp[t]+B,dp[t+A])

print(max(max(dp)+li[N-1][1],counter))

Solution (Python):




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

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

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

dp = [0]*T
counter = 0
for i in range(N-1):
    A,B = li[i]
    counter = max(counter,max(dp)+B)
    if A>T-1:
        continue
    for t in range(T-A-1,-1,-1):
        dp[t+A]=max(dp[t]+B,dp[t+A])

print(max(max(dp)+li[N-1][1],counter))

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 = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    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] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    N, T = list(map(int, input().split(' ')))
    foods = [list(map(int, input().split(' '))) for _ in range(N)]
    
    foods.sort(key=lambda food: food[0])
    
    dp = [[0 for _ in range(T + 1)] for _ in range(N + 1)]
    for i, food in enumerate(foods):
        n = i + 1
        A, B = food
        for t in range(T + 1):
            val = dp[n - 1][t]
            if t - A >= 0 and dp[n - 1][t - A] + B > val:
                val = dp[n - 1][t - A] + B
            dp[n][t] = val
    
    
    ans = 0
    for n in range(1, N + 1):
        v = dp[n - 1][T - 1] + foods[n - 1][1]
        ans = max(ans, v)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    ans = 0
    for i, (a, b) in enumerate(D[:-1]):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b

        if ans < dp[T - 1] + D[i + 1][1]:
            ans = dp[T - 1] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    max_sum = [0] * N
    for i, (a, b) in enumerate(D):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b
        max_sum[i] = dp[T - 1]

    ans = max(max_sum[i] + D[i + 1][1] for i in range(N - 1))

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    max_sum = [0] * N
    for i, (a, b) in enumerate(D):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b
        max_sum[i] = dp[T - 1]

    ans = 0
    for i in range(N - 1):
        if ans < max_sum[i] + D[i + 1][1]:
            ans = max_sum[i] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [[0] * T for _ in range(N + 1)]
    for i, (a, b) in enumerate(D):
        for t in range(T):
            if 0 <= t - a:
                dp[i + 1][t] = dp[i][t - a] + b
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N - 1):
        if ans < dp[i + 1][T - 1] + D[i + 1][1]:
            ans = dp[i + 1][T - 1] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [[0] * T for _ in range(N + 1)]
    for i, (a, b) in enumerate(D):
        for t in range(T):
            if 0 <= t - a:
                dp[i + 1][t] = dp[i][t - a] + b
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N - 1):
        if ans < dp[i + 1][T - 1] + D[i + 1][1]:
            ans = dp[i + 1][T - 1] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()
    A, B = zip(*D)

    dp = [[0] * T for _ in range(N + 1)]
    for i, (a, b) in enumerate(D):
        for t in range(T):
            if 0 <= t - a:
                dp[i + 1][t] = dp[i][t - a] + b
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        tmp = dp[i + 1][T - 1] + max(B[i + 1 :], default=0)
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()
    A, B = zip(*D)

    dp = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp[i + 1][t] = dp[i][t - A[i]] + B[i]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    ans = 0
    for i in range(N):
        tmp = dp[i+1][T - 1] + max(B[i + 1 :], default=0)
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

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

    dp2 = [[0] * T for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for t in range(T):
            if 0 <= t - A[i]:
                dp2[i][t] = dp2[i + 1][t - A[i]] + B[i]
            if dp2[i][t] < dp2[i + 1][t]:
                dp2[i][t] = dp2[i + 1][t]

    ans = 0
    for i in range(N):
        tmp = max(dp1[i][t] + dp2[i + 1][T - t - 1] for t in range(T)) + B[i]
        if ans < tmp:
            ans = tmp

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, T = LI()
    AB = []
    for i in range(N):
        _a, _b = LI()
        AB.append((_a, _b))
    AB = sorted(AB, key=lambda x: (x[0], x[1]))
    a = [elem[0] for elem in AB]
    b = [elem[1] for elem in AB]

    dp = [[0 for _ in range(T + 3001)] for _ in range(N+1)]
    for i in range(N):
        for t in range(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 = 0
    for i in range(N+1):
        for j in range(T + 3001):
            ans = max(dp[i][j], ans)
    print(ans)
main()

Solution (Python):
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, T = map(int, readline().split())
    dishes = []
    for _ in range(N):
        A, B = map(int, readline().split())
        dishes.append([A, B])

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

    for i, dish in enumerate(dishes[:-1]):
        a, b = dish
        i = i + 1
        for t in range(T):
            if a > t:
                dp1[i][t] = dp1[i-1][t]
            else:
                if dp1[i-1][t-a] + b > dp1[i-1][t]:
                    dp1[i][t] = dp1[i-1][t-a] + b
                else:
                    dp1[i][t] = dp1[i-1][t]


    for i, dish in enumerate(reversed(dishes[1:])):
        a, b = dish
        i = N - i - 1
        for t in range(T):
            if a > t:
                dp2[i][t] = dp2[i+1][t]
            else:
                if dp2[i+1][t-a] + b > dp2[i+1][t]:
                    dp2[i][t] = dp2[i+1][t-a] + b
                else:
                    dp2[i][t] = dp2[i+1][t]

    ans = 0
    for last in range(1, N+1):
        for j in range(T):
            a = dishes[last-1][1]
            a += dp1[last-1][T-1-j] + dp2[last][j]
            ans = a if ans < a else ans
    print(ans)


if __name__ == '__main__':
    solve()

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

Solution (Python):
n,t = map(int,input().split())
dishes = [[int(i) for i in input().split()] for _ in range(n)]
dishes.sort(key=lambda x: x[0])
dp = [[0]*(t+1) for _ in range(n+1)]

for i in range(n):
    a,b = dishes[i]
    for j in range(t+1):
        if j < t: dp[i+1][min(j+a,t)] = max(dp[i+1][min(j+a,t)],dp[i][j]+b)
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[n][t])

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

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

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

for i in range(N):
    for j in range(T + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    
        if dp[i][j] >= 0 and j < T:
            dp[i + 1][min(T, j + X[i][0])] = max(dp[i + 1][min(T, j + X[i][0])],
                                                 dp[i][j] + X[i][1])

print(max(dp[-1]))

Solution (Python):
def main():
    import sys
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  

    def S():
        return sys.stdin.readline().rstrip()

    N, T = map(int, S().split())
    A = [0]
    B = [0]
    for i in range(N):
        a, b = LI()
        A.append(a)
        B.append(b)

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

N,T = map(int,S().split())
A = [0]
B = [0]
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

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

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


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

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

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,t = map(int,ipt().split())
    dp = [[0,0] for i in range(t)]
    for _ in range(n):
        a,b = map(int,ipt().split())
        for i in range(t-1,a-1,-1):
            di = dp[i][1]
            dpi = dp[i-a][1]+b
            if di < dpi:
                dp[i][1] = dpi
        for i in dp:
            if i[1] < i[0]+b:
                i[1] = i[0]+b
        for i in range(t-1,a-1,-1):
            di = dp[i][0]
            dpi = dp[i-a][0]+b
            if di < dpi:
                dp[i][0] = dpi

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

    return

if __name__ == '__main__':
    main()

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

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = np.zeros((n+1, t), dtype=np.int64)
for i, (a, b) in enumerate(AB):
  np.maximum(dp[i, a:], dp[i, :-a]+b, out=dp[i+1, a:])
maxB = np.maximum.accumulate(B[::-1])[::-1]
ans = (dp[1:-1, -1]+maxB[1:]).max()
print(ans)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(N, T, AB):
    AB.sort()
    memo = [-1] * (T + max(a for a, b in AB))

    memo[0] = 0
    for a, b in AB:
        nm = memo[:]
        for t in range(T):
            if memo[t] == -1:
                continue
            nm[t+a] = max(nm[t+a], memo[t]+b)
        memo = nm
    
    return max(memo)


def main():
    N, T = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, T, AB))


if __name__ == '__main__':
    main()

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


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

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

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

ans = 0

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

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

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

Solution (Python):
import numpy as np

N, T = map(int, input().split())
C = [tuple(map(int, input().split())) for _ in range(N)]
C.sort(key=lambda x: x[0])

dp = np.zeros(T, dtype=int)
ans = 0
for i, (a, b) in enumerate(C):
    ans = max(ans, dp[T - 1] + b)
    new_dp = dp.copy()
    new_dp[a:] = np.maximum(dp[a:], dp[:-a] + b)
    dp = new_dp
print(ans)

Solution (Python):
import sys
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]
n,t=map(int,input().split())
ab = []
for i in range(n):
    ab.append(list(map(int,input().split())))

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

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

print(ans)

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())
food = []
for _ in range(N):
  food.append(list(map(int,input().split())))
food.sort(key= lambda x: x[0])
dp = knapsack(N,T,food)

C = [0]*(N+1)
for i in range(N)[::-1]:
  C[i] = max(C[i+1], food[i][1])

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

print(ans)

Solution (Python):
N,T,*ABf = map(int, open(0).read().split())
AB = [ABf[i:i+2] for i in range(0, len(ABf), 2)]
AB.sort()
dp = [[0] * 2 for _ in range(6000)]
filled = set([0])
for x in AB:
    temp = set()
    change = []
    for y in filled:
        if y + x[0] <= (T-1) + max(dp[y][1],x[0]):
            if dp[y+x[0]][0] <= dp[y][0] + x[1]:
                change.append((y,y+x[0],dp[y][0]+x[1],x[0]))
    for y in change:
        if dp[y[1]][0] == y[2]:
            dp[y[1]][1] = y[3]
        else:    
            dp[y[1]][0] = y[2]
            dp[y[1]][1] = y[3]
            temp.add(y[0]+x[0])
    filled = filled | temp
print(max(dp)[0])

Solution (Python):

def resolve():
    n, t = map(int, input().split())
    foods = []
    limit = 0
    tt = []
    for i in range(n):
        a, b = map(int, input().split())
        foods.append((a,b))
        limit += a
        tt.append(a)
    c = max(tt) * 2
    foods.sort(key=lambda x:(x[0], -x[1]))
    limit = min(limit * 2, t * 2)
    time = [0 for _ in range(limit+c)]
    used = [0] * (limit + c)
    used[0] = 1

    for a,b in foods:
        for i in range(limit+c)[::-1]:
            if used[i] and i+a*2 < limit + c and time[i+a*2] < time[i] + b:
                time[i+a*2] = time[i] + b
                if i+a*2 < limit:
                    used[i+a*2] = 1

    print(max(time))

if __name__ == "__main__":
    resolve()

Solution (Python):
INF = 10 ** 7
N,T = map(int,input().split())
foods = []
for _ in range(N):
    foods.append(list(map(int,input().split())))

foods.sort()
dp = [[-INF for i in range(T)] for j in range(N+1)]
dp[0][0] = 0
ans = 0

for i in range(N):
    food = foods[i]
    for j in range(T):
        ans = max(ans, dp[i][j] + food[1])
        if dp[i][j] != INF:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if j + food[0] < T:
                dp[i+1][j + food[0]] = max(dp[i+1][j + food[0]], dp[i][j] + food[1])

print(ans)

Solution (Python):













'''
dp[i][j] ... 最大の美味しさの総和。[,i)の料理まで考慮したとき。j分以内に食べ終わることができる。
'''

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))



from itertools import product, permutations, combinations





N, T = read_ints()
A, B = read_col(N)
tmp = list(zip(A, B))
tmp.sort()
A, B = map(list, zip(*tmp))


'''
dp[i][j] ... 最大の美味しさの総和。[,i)の料理まで考慮したとき。j分以内に食べ終わることができる。
'''

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

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

ans = 0
for i in ra(N):
    ans = max(ans, dp[i][-1] + B[i])
print(ans)

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

def solve():
    N, T = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    items.sort()

    capW = T-1
    dp = [0] * (capW+1)
    ans = 0
    for wi, vi in items:
        ans = max(ans, dp[-1]+vi)
        for w in reversed(range(wi, capW+1)):
            v0 = dp[w-wi] + vi
            if v0 > dp[w]:
                dp[w] = v0

    print(ans)


solve()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n,t=map(int,readline().split())
    li=[list(map(int,readline().split())) for _ in range(n)]
    li.sort()
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=li[i][0],li[i][1]

    
    inf=-10**9
    dp=[[inf]*(t+1) for _ in range(n+1)]
    dp[0][0]=0
    for i in range(n):
        for j in range(t+1):
            
            if j!=t:
                dp[i+1][min(t,j+a[i])]=max(dp[i+1][min(t,j+a[i])],dp[i][j]+b[i])
            
            
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])

    print(max(dp[n]))

if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n,t=map(int,readline().split())
    li=[list(map(int,readline().split())) for _ in range(n)]
    li.sort()
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=li[i][0],li[i][1]

    
    inf=-float("inf")
    dp=[[inf]*(t+1) for _ in range(n+1)]
    dp[0][0]=0
    for i in range(n):
        for j in range(t+1):
            
            if j!=t:
                dp[i+1][min(t,j+a[i])]=max(dp[i+1][min(t,j+a[i])],dp[i][j]+b[i])
            
            
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])

    print(max(dp[n]))

if __name__=="__main__":
    main()

Solution (Python):
n,T = map(int, raw_input().split(' '))
dishes = [map(int, raw_input().split(' ')) for _ in range(n)]



h = [0 for iii in range(T + 1)]
dishes.sort(key = lambda x:x[0])
m = dishes[0][1] if len(dishes) == 1 else 0
for u,v in dishes:
	m = max(m , h[T-1] + v)
	for tt in range(T - 1, -1, -1):
		if tt - u >= 0:
			h[tt] = max(h[tt], v + h[tt - u])
		
print m

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])
import numpy as np
ans=0
dp=np.zeros(t,np.int64)

for i in range(n):
  a,b=ab[i]
  ans=max(ans,dp[-1]+b)
  dp[a:]=np.maximum(dp[a:],dp[:-a]+b)
print(ans)

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

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

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

ans = 0
for i in range(1,T+3001):
    ans = max(dp[i][N],ans)
print(ans)