Overview

You purchase \(N\) items either at a “supermarket (with discount)” or at “another store (regular price).” At the supermarket, the discount rate \(P_i\) is determined by the total amount \(X\), and this discount rate is non-decreasing with respect to the total amount. The problem is to minimize the total payment.

Analysis

Organizing the Total Payment Formula

First, let’s organize how the total payment is expressed. Let \(S\) be the sum of regular prices of all items, and \(X\) be the sum of regular prices of items brought to the supermarket checkout. Then, the sum of regular prices of items purchased at the other store is \(S - X\).

If we denote the discount amount at the supermarket as \(D(X)\), the total payment becomes: $\((\text{Payment at supermarket}) + (\text{Payment at other store}) = (X - D(X)) + (S - X) = S - D(X)\)$

Since \(S\) is a constant (the total of all items), to minimize the total payment, we need to maximize the discount amount \(D(X)\).

Properties of the Discount Amount \(D(X)\)

The discount amount \(D(X)\) is calculated as \(\lfloor X \times P_i / 100 \rfloor\). Let’s focus on how the tier (discount rate) is determined. From the problem statement, the following conditions are given: - Minimum applicable amounts: \(T_1 < T_2 < \cdots < T_K\) - Discount rates: \(P_1 \leq P_2 \leq \cdots \leq P_K\)

As the amount \(X\) increases, the applicable tier index \(i\) either increases or stays the same. And as the index \(i\) increases, the discount rate \(P_i\) also increases (or stays equal), so the larger the total amount \(X\), the larger the discount amount \(D(X)\) becomes.

Therefore, to maximize the discount amount, we should maximize the total amount \(X\) brought to the supermarket, meaning “buying all items at the supermarket” is optimal.

Algorithm

1. Calculate the sum \(S\) of regular prices of all items.
2. Determine the tier \(i\) that applies when \(X = S\).
   • Find the largest \(i\) such that \(T_i \leq S\).
   • Since \(T\) is sorted in ascending order, this can be efficiently found using binary search (e.g., bisect_right).
3. Using the discount rate \(P_i\) of the identified tier, calculate the discount amount \(\lfloor S \times P_i / 100 \rfloor\).
4. Output the value of the total \(S\) minus the discount amount as the answer.

Complexity

• Time complexity: \(O(N + \log K)\)
  • \(O(N)\) for computing the sum of all items, and \(O(\log K)\) for binary searching the tier.
• Space complexity: \(O(N + K)\)
  • Memory is needed to store the list of item prices and the tier information.

Implementation Notes

• Size of the total amount: Since \(T_K\) can be \(2 \times 10^{14}\) and the sum of items can be even larger, 64-bit integers (standard int in Python) must be used.

• Binary search: When finding the applicable tier, using bisect_right returns “the index of the first element greater than \(S\),” so subtracting \(1\) from it gives “the index of the largest element less than or equal to \(S\).”

• Rounding: The “floor (truncation of decimal places)” in the discount amount calculation can be performed using integer division (the // operator in Python).

  Source Code

import sys
import bisect

def solve():
    # Use sys.stdin.read().split() to read all input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Convert all input strings to integers for processing
    data = list(map(int, input_data))
    
    # N is the number of items, K is the number of discount tiers
    N = data[0]
    K = data[1]
    
    # Extract tier lower bounds (T) and their corresponding discount rates (P)
    # They are given in pairs T_1, P_1, T_2, P_2, ..., T_K, P_K
    T = []
    P = []
    for i in range(K):
        T.append(data[2 + 2*i])
        P.append(data[3 + 2*i])
    
    # Extract item prices (C_j) and calculate the total sum of all items
    # Prices start after N, K, and the 2*K tier parameters
    C_start = 2 + 2*K
    total_sum = sum(data[C_start : C_start + N])
    
    # The discount D(X) = floor(X * P_i / 100) is non-decreasing with X
    # because the tier discount rate P_i is non-decreasing with X (P_1 <= P_2 <= ... <= P_K).
    # Therefore, to maximize the discount (and minimize the total cost), 
    # we should maximize the amount X spent at the supermarket.
    # The maximum possible X is the sum of all items bought by Takahashi.
    X = total_sum
    
    # Find the applicable tier for X. The tier i is the largest i such that T_i <= X.
    # Since T is sorted in strictly increasing order, we use binary search (bisect_right).
    # bisect_right returns the insertion point that maintains order, so subtracting 1
    # gives the index of the largest element T_i <= X.
    idx = bisect.bisect_right(T, X) - 1
    
    # Calculate the discount based on the identified tier index.
    # idx will be at least 0 because T_1 = 0 and X >= 0.
    discount = (X * P[idx]) // 100
    
    # Total cost = (X - discount) + (TotalSum - X) = TotalSum - discount
    print(total_sum - discount)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.