Overview

Select some items from \(N\) products so that the total cost is exactly \(S\) yen, and find the maximum total satisfaction. If no valid selection exists, output \(-1\).

Analysis

This problem is a constrained optimization problem where we must “select products that cost exactly \(S\) yen.” This is a typical application of the subset sum problem, where we need to track “the maximum satisfaction obtainable when spending exactly a certain amount.”

A naive brute-force search (trying all \(2^N\) combinations) is not feasible since \(N\) can be up to 3000 (it would be too slow). A simple greedy approach also cannot guarantee an optimal solution.

Therefore, we use dynamic programming (DP). In particular, using “DP keyed by amount” allows us to solve this efficiently.

However, in this problem there is a constraint that “at least one product must be selected.” Therefore, while “0 yen, 0 items selected, satisfaction 0” is fine as the initial DP state, it must not be the only solution in the end. This point requires careful attention.

Algorithm

This problem is solved using dynamic programming keyed by price (knapsack-type DP).

DP Table Definition

\[ dp[w] := \text{the maximum satisfaction obtainable by spending exactly}~w~\text{yen} \]

However, since at least one product must be selected, we initialize the state as follows: - \(dp[0] = 0\) (spend 0 yen, select 0 items) - For all other values, \(dp[w] = -\infty\)

Transitions

For each product \((V_i, C_i)\), we update from larger amounts downward to prevent using the same product multiple times.

Transition formula: $\( dp[w + C_i] = \max(dp[w + C_i],~dp[w] + V_i) \quad \text{where}~w + C_i \leq S \)$

However, if \(dp[w] = -\infty\), we do not update (that amount cannot be formed).

Final Result

Finally, check the value of \(dp[S]\): - If \(dp[S] = -\infty\), there is no way to buy items for exactly \(S\) yen, so output \(-1\) - Otherwise, the value of \(dp[S]\) is the answer

Implementation Details

• For each product, copy the current DP array and update it (prev/curr approach) to prevent selecting the same product multiple times
• \(-\infty\) is used to represent “amounts that cannot be formed”

Complexity

• Time complexity: \(O(N \times S)\)
• Space complexity: \(O(S)\)

Implementation Notes

• The case of selecting no products (\(dp[0]=0\)) is allowed as an initial value, but be careful that it must not be the only solution in the end

• During updates, always copy the “current DP” to create a new DP, ensuring that a single product is not used multiple times

• math.inf is used to represent infinity, and != -math.inf is used to determine whether a state is valid

  Source Code

import sys
import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    
    V = [0] * N
    C = [0] * N
    
    index = 2
    for i in range(N):
        V[i] = int(data[index])
        C[i] = int(data[index+1])
        index += 2

    # dp[i][w] := 最初のi個の商品を使って、ちょうどw円を使う時の最大満足度
    # ただし、選んだ商品が1個以上必要なので、適切に管理する
    # 初期化: -1 で初期化し、作れない場合は-1とする
    # dp[0][0] = 0 （0個使って0円使うのは可能、満足度0）
    
    prev_dp = [-math.inf] * (S + 1)
    prev_dp[0] = 0

    for i in range(N):
        curr_dp = prev_dp[:]
        v = V[i]
        c = C[i]
        for w in range(S + 1):
            if prev_dp[w] != -math.inf and w + c <= S:
                if curr_dp[w + c] < prev_dp[w] + v:
                    curr_dp[w + c] = prev_dp[w] + v
        prev_dp = curr_dp

    result = prev_dp[S]
    if result == -math.inf:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.