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



Sample input:
2 60
10 10
100 100


Sample output:
110

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# youk_library(debug)
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)
    # tsv出力
    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)]

        # ------------
        # DP準備
        # ------------
        # DPの鉄則1? 「カスタム添え字として使用する」要素でソート。
        #   ->本問題の場合、カスタム添え字は「使用する時間」。この昇順でソート。
        ab_s.sort(key=lambda xx: [xx[0]])

        # DPの鉄則2?「DP対象のリスト[0]に添字調整用のダミーを追加。
        #   ->先頭から1つ選ぶ=ab_s[1]という風に、直観的に扱えるようになる。
        ab_s = [[0, 0]] + ab_s

        # DP配列の作成。
        # dp[0][使用する時間(累計):0~6000] = おいしさの最大値(-1=存在しないパターン)
        dp = [[-1 for j in range(6000 + 1)]]

        # DP配列の初期化。(何も選ばない場合の値をセット) ※ここは問題により固有※
        # 今回は・・料理を何も食べない=おいしさ0
        dp[0][0] = 0

        # ------------
        # DP
        # ------------
        # 先頭からi個選ぶループ
        for i in range(1, 9999999):

            # 次の行を追加(前の行を複写して追加) ※適時append()すると見やすい。
            dp.append(dp[i - 1].copy())

            # 最後の要素まで検証したならDP終了
            if len(ab_s) <= i:
                break

            # 検証対象の情報を取り出し ※ここは問題により固有※
            time, delicious = ab_s[i]

            # カスタム添え字ループ
            for j in range(9999999):

                # 制限時間を超えたら要素の検証を終える。次の要素へ。 ※ここは問題ごとに設定※
                if j > t - 1:
                    break

                # 値が0未満は「存在しないパターン」なので検証しない。
                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)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main(verbosity=2)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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],# 1つまえの時間でも達成できる
                    dp[i][j]# i番目を選ばない
                    )
                if j-a>=0:
                    dp[i+1][j]=max(
                        dp[i+1][j],
                        dp[i][j-a]+b
                    )
        return dp
                
    dp=calc(A,B)
    # dp[i][j]はi番目までみて，j分以内に食べられる最大値
    
    dp2=calc(A[::-1],B[::-1])
    # dp2[i][j]は後ろからi個みて，j分以内に食べられる最大値
    

              
    ans=0
    for i in range(N):
        a=A[i]
        b=B[i]
        temp=0
        for j in range(T):#最後にi番目をオーダーするので，T-1秒の間にどこまでいけるか
            aa=dp[i][j]
            bb=dp2[N-i-1][T-j-1]
            temp=max(temp,aa+bb)
        ans=max(ans,temp+b)
            
        # print(i,a,b,ans)
            
    print(ans)
                
 

main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
# sys.setrecursionlimit(1000000)

# input aliases
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):
            # tmp[idx] = max(tmp[idx], dd)
            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(dp)
    # print(li)
    print(ans)





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

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
"""
食べるのにかかる時間順にソートしてナップサックするのがよい。
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
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)

Submission status: Accepted

Solution code:
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)
#     L.append((b/a,a,b))
# L.sort(key = lambda x:(-x[0],x[1]))
# hq = []
# ans = []
# print(L)
# import heapq
# for c,a,b in L:
#     if a>=t:
#         heapq.heappush(hq,(-b,a,c))
#     else:
#         ans.append((b,a,c))
#         t-=a
# heapq.heapify(ans)
# if t ==0 and hq:
#     nb,nc,na = heapq.heappop(hq)
#     bb,bc,ba = heapq.heappop(ans)
#     if nb>bb:
#         heapq.heappush(ans,(-nb,nc,na))
#     else:
#         heapq.heappush(ans,(bb,b,c,ba))
# elif hq:
#     nb,nc,na = heapq.heappop(hq)
#     heapq.heappush(ans,(-nb,nc,na))
# res = 0
# for b,c,a in ans:
#     res += b
# print(ans)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

#最終商品をラストオーダ(t-1)で注文する
for i ,(wi,vi) in enumerate(ab):
    ans = max(ans, dp[i][t-1]+vi)
   
print(ans)

Submission status: Accepted

Solution code:
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)