概要

各商品を高々1回ずつ選んで、合計金額をちょうど \(S\) にできる場合の「満足度合計の最大値」を求める問題です。ちょうど \(S\) にできない場合は \(-1\) を出力します。

考察

• 「選ぶ/選ばない」を各商品について決めるため、素朴に全探索すると \(2^N\) 通りになり、\(N \le 3000\) では到底間に合いません。
• 目標は「合計金額がちょうど \(S\)」なので、金額（コスト）を状態にした動的計画法（DP）が自然です。
• 典型的な 0/1 ナップサック（各品物は1回まで）で、
  • 重さ（コスト）＝ \(C_i\)
  • 価値（満足度）＝ \(V_i\)
  • ただし「重さ \(S\) 以下」ではなく 「重さがちょうど \(S\)」 のときの最大価値が欲しい、という点がポイントです。
• 「ちょうど」を扱うには、到達不可能な状態を明確に区別する必要があります。例えば dp[j] = -∞ を「金額 \(j\) は作れない」として持つと扱いやすいです。

（例） \(S=5\)、商品が \((V,C)=(10,2),(7,3)\) のとき、金額 \(2\) は満足度 \(10\)、金額 \(5\) は \(10+7=17\) と更新され、最終的に dp[5]=17 が答えになります。

アルゴリズム

1. dp[j] を「合計金額がちょうど \(j\) 円になるように選んだときの満足度合計の最大値」と定義します。
2. 初期化：
   • dp[0] = 0（何も選ばず金額0は作れる）
   • それ以外は dp[j] = -∞（作れない）
3. 各商品 \((V_i, C_i)\) について、0/1 なので 金額を大きい方から 逆順に更新します：
   • \(j = S, S-1, \dots, C_i\) について
     もし dp[j - C_i] が到達可能（-∞ でない）なら
     dp[j] = max(dp[j], dp[j - C_i] + V_i)

逆順にする理由は、同じ商品を同一ループ内で複数回使ってしまう（無制限ナップサックになってしまう）のを防ぐためです。 4. 最後に dp[S] が -∞ のままなら不可能なので -1、そうでなければその値が最大満足度です。

計算量

• 時間計算量: \(O(NS)\)（各商品ごとに \(0 \sim S\) の範囲を更新）
• 空間計算量: \(O(S)\)（1次元DP配列のみ）

実装のポイント

• 「到達不可能」を表す値として十分小さい数（コードでは NEG = -10^18）を使うと、max を安全に取れます。

• 0/1 ナップサックなので、更新は必ず for j in range(S, c-1, -1) のように 降順 にします。

• C_i > S の商品はどう頑張っても使えないのでスキップしてOKです。

• 問題文では「1個以上選ぶ」とありますが、\(S \ge 1\) なので dp[S] が到達可能なら必ず何かを選んでいます（dp[0]=0 が答えになることはない）ため、追加の処理は不要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    S = next(it)

    NEG = -10**18
    dp = [NEG] * (S + 1)
    dp[0] = 0

    for _ in range(N):
        v = next(it)
        c = next(it)
        if c > S:
            continue
        for j in range(S, c - 1, -1):
            prev = dp[j - c]
            if prev != NEG:
                val = prev + v
                if val > dp[j]:
                    dp[j] = val

    ans = dp[S]
    if ans == NEG:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。