Overview

Since we can independently choose whether to sell or not sell each product, this is a problem of finding the total profit (maximum value) when selecting only the products that yield a positive profit.

Analysis

The profit when selecting a set of products \(S\) can be transformed as follows: $\(\sum_{i \in S} A_i - \sum_{i \in S} B_i = \sum_{i \in S} (A_i - B_i)\)\( In other words, the problem reduces to summing up the "net profit" \)d_i = A_i - B_i\( for each product \)i$.

The key observation is as follows:

• If \(d_i\) for a product \(i\) is positive, selecting that product increases the profit by \(d_i\).
• If \(d_i\) is 0 or negative, selecting that product does not increase the profit (it stays the same or decreases).

Since the selection of each product is independent, there are no interactions such as “combining with other products yields a benefit.” Therefore, the optimal strategy is:

• Always sell products where \(d_i > 0\)
• Do not sell products where \(d_i \le 0\)

A naive approach of “trying all subsets” would require checking \(2^N\) combinations, which is far too slow for \(N \le 2 \times 10^5\) (TLE). With the above observation, the optimal solution is determined by examining each product just once.

Examples: - \((A,B)=(100,70)\) gives \(d=30\) → sell - \((A,B)=(50,80)\) gives \(d=-30\) → do not sell

We simply sum up only the positive values of \(d\).

Algorithm

1. Initialize the answer ans = 0.
2. For each product, compute \(d = A_i - B_i\).
3. If \(d > 0\), add it to the answer: ans += d (add only the portion that increases profit).
4. Output ans at the end.

Since not selecting a product is always an option, there is no need to add negative values, and as a result, the maximum profit is naturally \(0\) or greater.

Complexity

• Time complexity: \(O(N)\) (each product is processed once)
• Space complexity: \(O(1)\) (no large additional arrays are needed)

Implementation Notes

• \(A_i, B_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), so the total can reach approximately \(2 \times 10^{14}\). Python’s int handles this fine, but in other languages, 64-bit integers are required.

• Since the input can be large, in Python it is safe to use sys.stdin.buffer.readline for faster input.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    ans = 0
    for _ in range(N):
        a, b = map(int, input().split())
        d = a - b
        if d > 0:
            ans += d
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.