Overview

Given the selling price and preparation cost for each product, this is a problem of selecting products to maximize profit. Profit is the total selling price of selected products minus the total preparation cost.

Analysis

For each product, we can independently decide “whether to sell it or not.” To maximize profit, it is effective to consider whether each product contributes positively to the overall profit.

For each product \(i\), the profit gained by selling that product is \(A_i - B_i\). If this is positive, we should sell it; if negative, we should not. In particular, since we cannot select the same product multiple times, making this decision for all products gives us the optimal selection.

For example, consider the following input:

3
5 3
2 4
6 1

The profit for each product is:

• Product 1: \(5 - 3 = 2\) (worth selling)
• Product 2: \(2 - 4 = -2\) (better not to sell)
• Product 3: \(6 - 1 = 5\) (worth selling)

Therefore, by selecting products 1 and 3, the profit is \(2 + 5 = 7\), which is the maximum.

As shown, we only need to check whether the profit for each product is positive to decide whether to select it.

A naive approach would be to enumerate all subsets, but since the number of products \(N\) can be up to \(2 \times 10^5\), enumerating \(2^N\) combinations is far from feasible. However, since each product can be judged independently, exhaustive search is unnecessary.

Algorithm

1. For each product, read the selling price \(A_i\) and preparation cost \(B_i\).
2. For each product, if \(A_i - B_i > 0\), add that difference to the total profit.
3. Output the final total profit.

In other words, the optimal solution is obtained simply by selecting only the products with positive profit and summing them up.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input data)

Since it suffices to examine each product once, the problem can be solved in linear time.

Implementation Notes

• We simply check whether each product’s profit \(A_i - B_i\) is positive, and if so, add it. This can be implemented with a simple loop.

• The profit when no products are selected is 0 yen, so by initializing the total to 0, this case is handled naturally.

  Source Code

n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

total_profit = 0
for a, b in items:
    if a > b:
        total_profit += a - b

print(total_profit)

---

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