Overview

This is a problem where you choose to “buy or not buy” food from each stall, and maximize the total satisfaction while keeping the total cost within \(M\) yen. It can be solved as a classic 0/1 knapsack problem.

Analysis

• Since each stall’s food can be bought at most once, the choice is “0/1” (buy or not buy).
• The objective is to “maximize total satisfaction” under the constraint “total cost \(\le M\)”, which directly maps to the 0/1 knapsack formulation.

As naive approaches: - Greedy (e.g., buying in order of highest satisfaction/price ratio) is generally incorrect.
For example, with \(M=10\) and (price, satisfaction) being \((6,9),(5,8),(5,8)\), choosing \((6,9)\) (highest ratio) leaves 4 yen with nothing else to buy, giving satisfaction 9. However, \((5,8)+(5,8)\) gives satisfaction 16, which is better. - Exhaustive search (trying all combinations) has \(2^N\) possibilities. Since \(N \le 15\) in this problem, it could theoretically work in time, but the standard and reliable approach is DP (dynamic programming). Moreover, since \(M \le 10^4\), an \(O(NM)\) DP is sufficiently fast.

Therefore, we use DP to track “the maximum satisfaction achievable using only the stalls considered so far, within a certain budget.”

Algorithm

Define the DP array dp[w] as follows:

• dp[w] = “the maximum satisfaction when buying items (from the stalls processed so far) with a total cost of exactly \(w\) yen (remains 0 if impossible)”
  ※ Since this code does not propagate from dp[w-1] to dp[w], the state represents “exactly \(w\)” rather than “\(\le w\)”. Therefore, at the end we take max(dp) to obtain the maximum over all costs “\(\le M\)”.

The initial state is buying nothing, so dp[*]=0.

For each item (price \(t\), satisfaction \(p\)), do the following:

• Iterate budget w from \(M\) down to \(t\) in reverse order:
  • dp[w] = max(dp[w], dp[w-t] + p)

Reason for iterating in reverse: - If we update in the forward direction (from small w), a transition can occur where the same item is “used twice within the same pass,” resulting in behavior closer to an unbounded knapsack rather than 0/1 (each item at most once). - In reverse order, dp[w-t] references the value “before this item was used,” ensuring each item is used at most once.

Finally, since any total cost from \(0\) to \(M\) is acceptable: - The answer is max(dp) (the maximum satisfaction among all total costs \(\le M\)).

Complexity

• Time complexity: \(O(NM)\)
  (For each item, we scan \(w=0..M\) once)
• Space complexity: \(O(M)\)
  (A 1-dimensional DP array of length \(M+1\))

Implementation Notes

• The update loop must iterate in reverse, such as for w in range(M, t - 1, -1): (a critical point for 0/1 knapsack).

• Since dp[w] primarily represents the state of “exactly \(w\) yen,” the final output should be max(dp) rather than dp[M], to capture the maximum value over all costs “\(\le M\)”.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]  # (T, P)

    dp = [0] * (M + 1)
    for t, p in items:
        for w in range(M, t - 1, -1):
            cand = dp[w - t] + p
            if cand > dp[w]:
                dp[w] = cand

    print(max(dp))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.