Overview

Considering 2 choices for each dish — “select / don’t select” — the total number of combinations is at most \(2^{19}\).
We perform this exhaustive search, compute the satisfaction for each combination: \( \sum A_i - D \times \max(0, \sum B_i - K)\) and take the maximum value to solve the problem.

Analysis

This problem requires deciding for each dish whether to “order it or not.”
In other words, it is a subset optimization problem.

Given the conditions: - The number of dishes \(N \le 19\) is small - Each dish can be selected at most once - The evaluation formula for each combination can be computed directly

the approach of trying all subsets is natural.

Why exhaustive search is fast enough

The total number of combinations is \(2^N\), which is at most \(2^{19} = 524{,}288\).
Even if we compute the total tastiness and total heaviness of the selected dishes for each combination, it is sufficiently fast.

Concerns about the brute-force approach and their resolution

You might feel that “exhaustive search seems too slow,” but since the constraints are small, it will not result in TLE.
On the other hand, a greedy approach (e.g., selecting dishes in order of highest tastiness) may miss the optimal solution because the penalty can take effect later, resulting in WA.
Therefore, under these constraints, an exact exhaustive search is the most reliable approach.

Algorithm

1. Read the input (\(A_i, B_i\)).
2. Initialize the answer ans to 0 (the case where nothing is ordered).
3. Iterate mask from \(0\) to \((1<<N)-1\), representing each subset.
   • Consider the dishes corresponding to the set bits of mask as selected.
   • Compute the total tastiness sum_a and total heaviness sum_b.
4. Compute the satisfaction:
   • If \(sum_b \le K\), then score = sum_a
   • If \(sum_b > K\), then score = sum_a - D \times (sum_b - K)
5. Update with ans = max(ans, score).
6. Output ans at the end.

Visualizing bit exhaustive search

For example, if \(N=3\), then mask=5 (101_2) represents: - Dish 0: select
- Dish 1: don’t select
- Dish 2: select

Complexity

• Time complexity: \(O(N \cdot 2^N)\)
• Space complexity: \(O(N)\) (constant aside from the input arrays)

Implementation Notes

• By setting the initial value ans = 0, the “select nothing” case is naturally included.

• The penalty applies only to the excess, so it is subtracted only when sum_b > K.

• Even in Python, this exhaustive search is fast enough for \(N \le 19\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, D = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    ans = 0  # 何も選ばない場合

    for mask in range(1 << N):
        sum_a = 0
        sum_b = 0
        m = mask
        i = 0
        while m:
            if m & 1:
                sum_a += A[i]
                sum_b += B[i]
            i += 1
            m >>= 1
        # m が 0 でも i 未満のビットしか見ていないが、それで十分
        if sum_b > K:
            score = sum_a - D * (sum_b - K)
        else:
            score = sum_a
        if score > ans:
            ans = score

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.