Overview

For each of the \(N\) items, we select the cheapest shop among those that handle that item’s category, and minimize the total cost. If there is a category that no shop handles, we output -1.

Analysis

Key Insight

Since each item’s purchase location can be chosen independently, the key point is that we should buy each item at the cheapest shop available for it.

For example, if there are \(4\) items of category \(3\) and two shops handling category \(3\) — one priced at 100 yen and the other at 150 yen — the cheapest option is to buy all 4 items at the 100 yen shop.

In other words, it is optimal to buy all items of the same category at the same cheapest shop.

Problem with the Naive Approach

If we search through all \(M\) shops for each item to find the minimum price, it would be \(O(NM)\), which requires \(4 \times 10^{10}\) operations when \(N, M\) are at most \(2 \times 10^5\), resulting in TLE.

Solution

By precomputing the minimum price per category in a dictionary (hash map), we can look up the minimum price for each item in \(O(1)\).

Algorithm

1. Preprocessing: Read the information of \(M\) shops and build a dictionary min_cost with category \(S_j\) as the key and the minimum price as the value. If multiple shops handle the same category, only the cheapest price is retained.

2. Total Calculation: For each of the \(N\) items, check whether category \(T_i\) exists in min_cost.

   • If it does not exist, the item cannot be purchased, so output -1 and terminate.
   • If it exists, add min_cost[T_i] to the total.

3. Output: If all items can be purchased, output the total cost.

Concrete Example

N=3, M=3
Item categories: [1, 2, 1]
Shops: (category 1, 100 yen), (category 2, 200 yen), (category 1, 80 yen)

• Preprocessing: min_cost = {1: 80, 2: 200} (For category 1, 80 yen is chosen over 100 yen)
• Item 1 (category 1) → 80 yen
• Item 2 (category 2) → 200 yen
• Item 3 (category 1) → 80 yen
• Total: \(80 + 200 + 80 = 360\) yen

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) to read shop information and build the dictionary, \(O(N)\) to look up the minimum price for each item (dictionary lookup is \(O(1)\) on average)
• Space complexity: \(O(N + M)\)
  • \(O(N)\) for the item list, \(O(M)\) for the minimum price dictionary per category

Implementation Notes

• Managing the minimum price per category with a dictionary: Since category values can be as large as \(10^9\), we need to use a dictionary (Python’s dict) instead of an array.

• Beware of overflow: Since \(N\) can be up to \(2 \times 10^5\) and \(C_j\) up to \(10^9\), the total can reach up to \(2 \times 10^{14}\). In Python, integer overflow does not occur, but in C++ and similar languages, long long must be used.

• Fast input: Since \(N, M\) can be large, input is sped up by reading all at once using sys.stdin.buffer.read().

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = []
    for i in range(N):
        T.append(int(input_data[idx])); idx += 1
    
    # For each category, find the minimum cost among all shops selling that category
    min_cost = {}
    for j in range(M):
        s = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        if s not in min_cost or c < min_cost[s]:
            min_cost[s] = c
    
    total = 0
    for t in T:
        if t not in min_cost:
            print(-1)
            return
        total += min_cost[t]
    
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.