Gravy Jobs

import sys
input = sys.stdin.readline

# -----------------------------
# 1. 入力を読む
# -----------------------------
N = int(input()) # 仕事の数
jobs = []        # 仕事を保存するリスト
Dmax = 0         # 最大の締切日（DPのサイズを決めるため）

print("N:", N)
for _ in range(N):
    D, C, S = map(int, input().split())
    print(f"D:{D}, C:{C}, S:{S}")
    # D = 締切日
    # C = かかる日数
    # S = 報酬
    jobs.append((D, C, S))
    Dmax = max(Dmax, D)

# -----------------------------
# 2. 締切が早い順に並べる
# -----------------------------
# 早い締切の仕事から処理すると考えやすい
jobs.sort()

# -----------------------------
# 3. DPテーブルを作る
# -----------------------------
# dp[d] = d日目までで得られる最大報酬
dp = [0] * (Dmax + 1)

# -----------------------------
# 4. 各仕事を順番に処理する
# -----------------------------
for D, C, S in jobs:
    # ---------------------------------
    # (A) その仕事をやる場合を考える
    # ---------------------------------
    # 同じ仕事を2回使わないため、後ろから回す
    # 後ろから回す(正しい)
    # d=7:  dp[7]  ←  dp[4] + S
    # d=6:  dp[6]  ←  dp[3] + S
    # d=5:  dp[5]  ←  dp[2] + S
    # d=4:  dp[4]  ←  dp[1] + S
    # d=3:  dp[3]  ←  dp[0] + S
    # 前から回す(誤り)
    # d=3:  dp[3]  ←  dp[0] + S
    # d=4:  dp[4]  ←  dp[1] + S
    # d=5:  dp[5]  ←  dp[2] + S
    # d=6:  dp[6]  ←  dp[3] + S   ← ★ここが危険
    # d=7:  dp[7]  ←  dp[4] + S   ← ★ここも危険
    print("=======================処理詳細=======================")
    print(f"D:{D}, C:{C}, S:{S}")
    for d in range(D, C-1, -1):
        print(f"dp[{d}] = {dp[d]}, dp[{d - C}] + {S} = {dp[d - C] + S}")
        dp[d] = max(dp[d], dp[d - C] + S)
    print(f"dp = {dp}")

    # ---------------------------------
    # (B) 前の日の最大値を引き継ぐ
    # ---------------------------------
    for d in range(1, Dmax + 1):
        dp[d] = max(dp[d], dp[d - 1])
    print(f"dp = {dp}")

print(dp[Dmax])