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 io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def list_to_tsv_string(target: [], limit_row: int = 0, limit_column: int = 0):
    import csv

    
    if limit_row is not 0:
        target = target[:limit_row]
    if limit_column is not 0:
        target = [i[:limit_column] for i in target]

    
    
    target = [[cnt] + i for cnt, i in enumerate(target)]
    
    work = [i for i in range(len(target[0]))]
    target.insert(0, work)
    
    with open("temp.txt", "w", newline="") as f:
        writer = csv.writer(f, delimiter="\t")
        writer.writerows(target)



def resolve(test=""):
    try:
        
        n, t = map(int, input().split())
        ab_s = [list(map(int, input().split())) for i in range(n)]

        
        
        
        
        
        ab_s.sort(key=lambda xx: [xx[0]])

        
        
        ab_s = [[0, 0]] + ab_s

        
        
        dp = [[-1 for j in range(6000 + 1)]]

        
        
        dp[0][0] = 0

        
        
        
        
        for i in range(1, 9999999):

            
            dp.append(dp[i - 1].copy())

            
            if len(ab_s) <= i:
                break

            
            time, delicious = ab_s[i]

            
            for j in range(9999999):

                
                if j > t - 1:
                    break

                
                if dp[i][j] < 0:
                    continue

                
                val = max(dp[i][j + time], dp[i - 1][j] + delicious)

                
                dp[i][j + time] = val

        
        
        
        print(max(dp[i]))

    except IndexError as err:
        print("インデックスエラー:", err.args[0])



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    
    def test_original1(self):
        test_input = """3 10
1 10
3000 20
1 20"""
        output = """50"""
        self.assertIO(test_input, output)

    def test_original2(self):
        test_input = """2 10
9 1
3000 3000"""
        output = """3001"""
        self.assertIO(test_input, output)

    def test_original3(self):
        test_input = """3000 3000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
3000 3000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1"""
        output = """5999"""
        self.assertIO(test_input, output)

    def test_input_1(self):
        test_input = """2 60
10 10
100 100"""
        output = """110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 60
10 10
10 20
10 30"""
        output = """60"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """3 60
30 10
30 20
30 30"""
        output = """50"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25"""
        output = """145"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main(verbosity=2)

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

ans = 0
dp = [0]*W
for a, b in ab:
    if ans < dp[-1]+b:
        ans = dp[-1]+b
    for j in reversed(range(W)):
        if j-a < 0:
            break
        if dp[j] < dp[j-a]+b:
            dp[j] = dp[j-a]+b
print(ans)

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

dp = [[0]*W for _ in range(n+1)]
for i in range(1, n+1):
    w, v = ab[i-1]
    for j in range(W):
        if dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]

        if 0 <= j-w and dp[i][j] < dp[i-1][j-w]+v:
            dp[i][j] = dp[i-1][j-w]+v


ans = 0
for i in range(n):
    a, b = ab[i]
    if ans < dp[i][W-1]+b:
        ans = dp[i][W-1]+b
print(ans)

Solution (Python):
n, W = map(int, input().split())
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(range(W)):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print(max(dp))

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
最後に食べるもので場合わけ，最後のもの以外を使う．
[0,i)と(i,N-1]の2つのdpで
"""
def main():
    mod=10**9+7
    N,T=MI()
    A=[0]*N
    B=[0]*N
    for i in range(N):
        A[i],B[i]=MI()
        
    M=3000
    
    def calc(A,B):
        dp=[[0]*(M+1) for _ in range(N+1)]
        for i in range(N):
            a=A[i]
            b=B[i]
            for j in range(1,M+1):
                dp[i+1][j]=max(
                    dp[i+1][j], 
                    dp[i+1][j-1],
                    dp[i][j]
                    )
                if j-a>=0:
                    dp[i+1][j]=max(
                        dp[i+1][j],
                        dp[i][j-a]+b
                    )
        return dp
                
    dp=calc(A,B)
    
    
    dp2=calc(A[::-1],B[::-1])
    
    

              
    ans=0
    for i in range(N):
        a=A[i]
        b=B[i]
        temp=0
        for j in range(T):
            aa=dp[i][j]
            bb=dp2[N-i-1][T-j-1]
            temp=max(temp,aa+bb)
        ans=max(ans,temp+b)
            
        
            
    print(ans)
                
 

main()

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

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

Solution (Python):











n, t = map(int, input().split())
dp = [0] * (t+1)
itm = [list(map(int, input().split())) for _ in range(n)]
itm.sort()
for w_ , v_ in itm:
    for i in range(1,t+1):
        dp[max(0,i-w_)] = max(dp[max(0,i-w_)], dp[i] + v_)
print(dp[0])

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

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

AB.sort()

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

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

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

b_max = 0
for i in range(N):
    b_max = max(b_max, dp[i][T-1] + AB[i][1])

print(b_max)

Solution (Python):
n,t=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i],b[i]=map(int,input().split())
dp1=[[0]*t for _ in range(n+1)]
dp2=[[0]*t for _ in range(n+1)]
for i in range(n):
  for j in range(t):
    if j>=a[i]:dp1[i+1][j]=max(dp1[i][j],dp1[i][j-a[i]]+b[i])
    else:dp1[i+1][j]=dp1[i][j]
for i in range(n-1,-1,-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=0
for i in range(n):
  for j in range(t):
    ans=max(ans,dp1[i][j]+dp2[i+1][t-j-1]+b[i])
print(ans)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[0] + x[1])
    dp = [0] * t
    ans = 0
    for a, b in li:
        tmp = copy.copy(dp)
        ans = max(ans, dp[-1] + b)
        for idx, dd in enumerate(dp):
            
            if idx + a < t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
        for j in range(len(dp) - 1):
            dp[j+1] = max(dp[j], dp[j+1])
    
    
    print(ans)





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):

def resolve():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    dp = [[0] * (T + 1) for _ in range(N + 1)]

    for i in range(N):
        t, v = AB[i]
        for j in range(T + 1):
            if t + j <= T:
                dp[i + 1][j + t] = max(dp[i + 1][j + t], dp[i][j] + v)
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    ans = 0
    for i, (t, v) in enumerate(AB):
        ans = max(ans, dp[i][T - 1] + v)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
t = [tuple(map(int, input().split())) for _ in range(N)]
t.sort()
dp = [0] * (T + 1)
for a, b in t:
  for i in range(T - 1, -1, -1):
    if i + a < T: dp[i + a] = max(dp[i + a], dp[i] + b)
    else: dp[-1] = max(dp[-1], dp[i] + b) 
print(max(dp))

Solution (Python):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:,:]), cache=True)
def main(N,T,A):
  dp = np.zeros(T+1, np.int64)
  for i in range(N):
    for t in range(T-1,-1,-1):
      u = min(T,t+A[i,0])
      dp[u] = max(dp[u],dp[t]+A[i,1])
  ans = dp[-1]
  return ans

N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A = np.array(sorted(A),np.int64)
print(main(N,T,A))

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

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

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

Solution (Python):
"""
食べるのにかかる時間順にソートしてナップサックするのがよい。
dp[i][j]
"""
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) for _ in range(N+1)]
for i in range(1,N+1):
    a,b = AB[i-1]
    for j in range(1,T):
        if j-a >= 0:
            dp[i][j] = max(dp[i-1][j-a]+b,dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

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

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

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

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

ans = 0
for j in range(1, N):
    ans = max(ans, dp[-1][j-1] + AB[j][1])

print(ans)

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

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

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

A = [0] + sorted(A, key=lambda x: x[0])
dp = [[0 for t in range(T+1)] for i in range(N+1)]
dp[0][0] = 0

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

    dp[i][T] = max(max(dp[i-1][max(0,T-A[i][0]):T]) + A[i][1], dp[i-1][T])

print(max(dp[N]))

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq


import bisect
n,t=map(int,input().split())
d1=[[0]*t for i in range(n+1)]
d2=[[0]*t for i in range(n+1)]

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

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

Solution (Python):
n,t = map(int,input().split())
L = []
m = 0
for _ in range(n):
    a,b = map(int,input().split())
    m = max(b,m)
    L.append((a,b))
L.sort()
dp =[[0]*(t+m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(t+m+1):
        if j-L[i][0]>=0 and t>j-L[i][0]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-L[i][0]]+L[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
ans = 0
for i in range(n+1):
    ans = max(ans,max(dp[i]))

print(ans)

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

Solution (Python):
import numpy as np
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, t = map(int, input().split())
    dp = np.zeros(t,dtype=int)
    food = []
    for _ in range(n):
        a, b = map(int, input().split())
        food.append([a, b])
    food.sort(key=lambda x: x[0]*-1)
    for j in range(n):
        a, b = food[j][0], food[j][1]
        a=min(a,t)
        dptmp=np.zeros(t,dtype=int)
        dptmp[a:] = np.maximum(dp[a:],dp[:-a]+b)
        dptmp[:a] = np.maximum(np.full(a,b,dtype=int), dp[:a])
        dp=dptmp
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    food=[]
    for _ in range(n):
        a,b=map(int, input().split())
        food.append([a,b])
    food.sort(key=lambda x:x[0]*-1)
    for j in range(n):
        a,b=food[j][0],food[j][1]
        dptmp=[0]*t
        for i in range(t):
            if i < a: 
                dptmp[i]=max(b,dp[i])
            else:
                dptmp[i]=max(dp[i-a]+b,dp[i])
        dp=dptmp
    print(dp[t-1])
 
if __name__=='__main__':
    main()

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

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

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

Solution (Python):
n,t = map(int,input().split())
a,b = [],[]
for i in range(n):
    x,y = map(int,input().split())
    a.append(x)
    b.append(y)
dp1 = [[0]*(t+1) for _ in range(n+2)]
dp2 = [[0]*(t+1) for _ in range(n+2)]
for i in range(1,n+1):
    w,v = a[i-1],b[i-1]
    for j in range(1,t+1):
        if j < w:
            dp1[i][j] = dp1[i-1][j]
        else:
            dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-w]+v)
for i in range(n,0,-1):
    w,v = a[i-1],b[i-1]
    for j in range(1,t+1):
        if j < w:
            dp2[i][j] = dp2[i+1][j]
        else:
            dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-w]+v)


ans = 0
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-1])
print(ans)

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

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


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

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




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

print(max(ans, dp[-1][-1]))

Solution (Python):
import numpy as np
N,T = map(int,input().split())

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




dp1 = np.zeros(T,dtype=int)
dp2 = np.zeros(T,dtype=int)

for a,b in meals:
    ndp1 = dp1.copy()
    ndp1[a:] = np.maximum(dp1[a:],dp1[:-a]+b)

    ndp2 = dp2.copy()
    ndp2[a:] = np.maximum(dp2[a:],dp2[:-a]+b)
    ndp2 = np.maximum(ndp2,dp1+b)
    dp1,dp2 = ndp1,ndp2

print(ndp2[-1])

Solution (Python):

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

dp = [[-1] * (T + 1) for _ 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]))