Overview

The total payment amount is calculated by subtracting the “discount received at the supermarket” from the “total price of all products.”
Therefore, this problem is not about “which subset to choose,” but rather about “when is the discount maximized.”

Analysis

First, let the sum of the regular prices of all products be \(S\) yen.

If the total of products bought at the supermarket is \(X\) yen, the remaining \(S-X\) yen worth of products are purchased at regular price from other stores.
In this case, the total payment is

\[ \left(X - \left\lfloor \frac{X \times P_i}{100} \right\rfloor\right) + (S-X) = S - \left\lfloor \frac{X \times P_i}{100} \right\rfloor \]

where \(P_i\) is the discount rate of the tier corresponding to \(X\).

In other words, since \(S\) is fixed, to minimize the total payment, we just need to maximize the discount amount $\( \left\lfloor \frac{X \times P_i}{100} \right\rfloor \)$

---

Key Insight

Let’s consider what happens when we increase the amount \(X\) spent at the supermarket.

• As \(X\) increases, the applicable tier either stays the same or goes up
• The discount rate \(P_i\) never decreases as the tier goes up (\(P_1 \leq P_2 \leq \cdots \leq P_K\))
• Therefore, \(\displaystyle \frac{X \times P_i}{100}\) never decreases as \(X\) increases
• Even after applying the floor \(\lfloor \cdot \rfloor\), the discount amount does not decrease

In other words, the larger the total amount \(X\) spent at the supermarket, the discount amount never decreases.

Therefore, the best strategy to maximize the discount is

\[ X = S \]

That is, buy all products at the supermarket.

---

Why a Naive Approach Is Unnecessary

Looking only at the problem statement, one might think:

• Which combination of products should be bought at the supermarket?
• Do we need to consider subset sums?

However, since \(N \leq 2 \times 10^5\), brute-forcing all subsets is obviously impossible, and subset-sum DP is also infeasible because the amounts are too large.

But in this problem, due to the monotonicity observation above, there is no need to consider subsets at all.
We just need to compute the total \(S\) of all products and calculate the discount for the tier corresponding to that amount.

Algorithm

1. Compute the total price \(S\) of all products
2. Find the highest tier applicable to \(S\)
   • That is, find the largest \(i\) such that \(T_i \leq S\)
   • Since \(T\) is sorted in ascending order, this can be found using binary search
3. Compute the discount amount $\( \left\lfloor \frac{S \times P_i}{100} \right\rfloor \)$
4. The answer is $\( S - \left\lfloor \frac{S \times P_i}{100} \right\rfloor \)$

---

For example, if the product total is \(S=1200\) yen, and:

• \(T_1=0, P_1=0\)
• \(T_2=1000, P_2=10\)

then buying everything at the supermarket gives a discount of

\[ \left\lfloor 1200 \times 10 / 100 \right\rfloor = 120 \]

and the payment is \(1080\) yen.

On the other hand, if only \(800\) yen worth is bought at the supermarket, the discount rate is \(0\%\), so the discount is \(0\) yen.
As shown, reducing the purchase amount never results in a benefit.

Complexity

• Time complexity: \(O(N + K)\)
• Space complexity: \(O(K)\)

Implementation Notes

• For tier determination, using bisect_right makes the code concise.

  • bisect_right(T, total) - 1 gives the largest \(i\) such that \(T_i \leq total\).

• The total price can be as large as $\( N \times 10^9 \leq 2 \times 10^{14} \)$ so depending on the language, 64-bit integers may be required.

• In Python, integers automatically use arbitrary precision, so there is no issue.

  Source Code

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    K = next(it)

    T = [0] * K
    P = [0] * K
    for i in range(K):
        T[i] = next(it)
        P[i] = next(it)

    total = 0
    for _ in range(N):
        total += next(it)

    idx = bisect_right(T, total) - 1
    discount = total * P[idx] // 100
    print(total - discount)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.