Overview

For each category, we match the “required quantity” with the “unit price at the cheapest store selling that category,” compute the total minimum cost if all categories can be fulfilled, and output -1 if any category cannot be fulfilled.

Analysis

The two key observations are:

1. Each category can be optimized independently
   There are no intertwined constraints between products or between categories.
   Products of category \(x\) can only be purchased at stores that handle category \(x\), and since each store can sell any number of items, it is optimal to buy all items of category \(x\) from the store with the lowest unit price among those handling that category.

2. All we need is “the quantity for each category” and “the minimum unit price for each category”

   • Product side: the number of occurrences of category \(T_i\) (required quantity)
     
   • Store side: the minimum price for category \(S_j\)
     Once we know these, the answer is: $\( \sum_{\text{category } c} (\text{required quantity } \mathrm{cnt}[c]) \times (\text{minimum unit price } \mathrm{minPrice}[c]) \)\( However, if \)\mathrm{minPrice}[c]\( does not exist (no store handles it) for a required category \)c$, then the purchase is impossible and we output -1.

Naively “searching all stores for the cheapest one for each product” would result in up to \(N \times M = 4 \times 10^{10}\) comparisons, which would certainly TLE.
Instead, we first aggregate the minimum unit price per category from the store information, then multiply by the required quantity per category, reducing the complexity to about \(O(N+M)\).

Concrete example: - Product categories: [1, 1, 3] → Required quantities: 2 of category 1, 1 of category 3 - Stores: (1, 100), (1, 80), (2, 50) → Minimum unit prices: category 1 is 80, category 2 is 50
In this case, no store handles category 3, so the answer is -1.

Algorithm

1. Count the product category sequence \(T\) and build the required quantity need[cat] per category (using Counter).
2. Read each store \((S_j, C_j)\) and update the minimum unit price min_price[cat] per category (taking the min).
3. For each category cat in need:
   • If min_price[cat] does not exist, output -1 and terminate.
   • If it exists, add total += need[cat] * min_price[cat].
4. Output total.

Complexity

• Time complexity: \(O(N + M)\) (hash table operations are assumed to be \(O(1)\) on average)
• Space complexity: \(O(K)\) (\(K\) is the number of distinct category types, at most around \(N+M\))

Implementation Notes

• Category values can be up to \(10^9\), so they cannot be used as array indices. Use a dictionary (dict) or Counter to manage them.

• Since multiple stores may handle the same category, it suffices to keep only the minimum value found in min_price[s].

• Since the input can be up to \(2 \times 10^5\) lines, we read everything at once using sys.stdin.buffer.read() to ensure speed.

  Source Code

import sys
from collections import Counter

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

    T = [next(it) for _ in range(N)]
    need = Counter(T)

    min_price = {}
    for _ in range(M):
        s = next(it)
        c = next(it)
        prev = min_price.get(s)
        if prev is None or c < prev:
            min_price[s] = c

    total = 0
    for cat, cnt in need.items():
        price = min_price.get(cat)
        if price is None:
            print(-1)
            return
        total += cnt * price

    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.