Overview

This problem is a subset optimization problem: “Which dishes to choose from \(N\) dishes?”
Since \(N \le 19\) is small, it is sufficient to enumerate all possible selections and find the maximum satisfaction.

Analysis

Each dish has 2 choices: “select / don’t select,” so there are \(2^N\) total combinations.

Normally, you might worry “aren’t there too many combinations?” for this kind of problem, but in this case:

• \(N \le 19\)
• Therefore \(2^{19} = 524288\)

That’s all.
With only about 500,000 combinations, computing the total for each combination is fast enough.

Key Insight

The important thing about this problem is that the order in which dishes are selected doesn’t matter — only which subset is chosen matters.
In other words, what we need to consider are “subsets.”

When a particular subset is chosen, let:

• \(S_A\) be the total deliciousness
• \(S_B\) be the total heaviness

Then the satisfaction is:

\[ S_A - D \times \max(0, S_B - K) \]

Therefore, for each subset:

1. Compute \(S_A\)
2. Compute \(S_B\)
3. Calculate the satisfaction using the formula above
4. Update the maximum value

This is all we need to do.

On the Naive Approach

For this problem, a naive brute-force search is actually optimal.
You might think “don’t I need to use dynamic programming?”, but:

• \(K\) and \(B_i\) can be up to \(10^6\)
• The total heaviness can become quite large

So a DP with heaviness as a state tends to be too expensive.

On the other hand, since \(N\) is very small, brute-force enumeration is simpler and more reliable.

Example

Suppose there are 3 dishes:

• Dish 1: \((A_1, B_1) = (5, 3)\)
• Dish 2: \((A_2, B_2) = (4, 2)\)
• Dish 3: \((A_3, B_3) = (8, 7)\)
• \(K = 5, D = 2\)

If we choose dishes 1 and 2:

• Total deliciousness \(= 5 + 4 = 9\)
• Total heaviness \(= 3 + 2 = 5\)

There is no excess, so the satisfaction is:

\[ 9 - 2 \times \max(0, 5 - 5) = 9 \]

If we choose dishes 1 and 3:

• Total deliciousness \(= 5 + 8 = 13\)
• Total heaviness \(= 3 + 7 = 10\)

The excess is \(5\), so the satisfaction is:

\[ 13 - 2 \times 5 = 3 \]

In this way, by comparing all combinations, we can find the maximum value.

Algorithm

We perform a bitmask enumeration.

For each dish:

• If the bit is \(1\), select it
• If the bit is \(0\), don’t select it

For example, by iterating mask from \(0\) to \((1 \ll N) - 1\), we can represent all subsets.

Procedure

1. Initialize the answer ans to \(0\)
   (The option of ordering nothing is allowed, and its satisfaction is \(0\))
2. Enumerate mask from \(0\) to \((1 \ll N)-1\)
3. For each mask, compute:
   • Total deliciousness sa
   • Total heaviness sb of the selected dishes
4. Calculate the satisfaction: $\( \text{score} = sa - D \times \max(0, sb - K) \)$
5. Update with ans = max(ans, score)
6. Output ans at the end

Complexity

• Time complexity: \(O(N \times 2^N)\)
• Space complexity: \(O(N)\)

Even when \(N = 19\):

\[ 19 \times 2^{19} \approx 10^7 \]

This is small enough to execute well within the time limit.

Implementation Notes

• The empty set (ordering nothing) is also allowed, so the answer is at least \(0\).
  Therefore, it is natural to initialize ans = 0.

• Bit operations are used to enumerate subsets.
  if (mask >> i) & 1: can be used to check “whether the \(i\)-th dish is selected.”

• In Python, integers automatically use arbitrary precision, so there is no need to worry about overflow even if the total values become large.

  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):
        sa = 0
        sb = 0
        for i in range(N):
            if (mask >> i) & 1:
                sa += A[i]
                sb += B[i]
        score = sa - D * max(0, sb - K)
        if score > ans:
            ans = score

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.