概要

各商品のカテゴリに対応するお店の中で最も安いところで購入することで、全商品を買うときの最小費用を求める問題。

考察

この問題では、それぞれの商品カテゴリについて、最も安い価格で購入するお店を選ぶ必要があります。

素朴な方法として、「各商品に対して、該当するカテゴリのお店を全部見て最も安い価格を探す」というやり方がありますが、これは商品数 \(N\) とお店数 \(M\) が最大で \(2 \times 10^5\) なので、計算量が \(O(N \times M)\) となり、間に合いません（TLE）。

そこで、事前に「各カテゴリにおける最小価格」を前処理しておけば、各商品に対して定数時間で最安値が求められます。この前処理は、お店の情報を読みながら各カテゴリの最小価格を記録していけば実現可能です。

また、もし商品リストの中に、どのお店でも取り扱っていないカテゴリがある場合は、その時点で -1 を出力して終了します。

アルゴリズム

1. 各カテゴリ \(S_j\) について、最小の価格 \(C_j\) を記録しておく（辞書型などを使う）。
2. 商品リスト \(T_i\) を順番に見ていき、それぞれのカテゴリに対応する最安値を合計に加える。
3. もし対応するカテゴリのお店が一つもない場合は -1 を出力して終了。
4. すべての商品を買えた場合は、合計金額を出力。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(M)\) （カテゴリ数に比例）

実装のポイント

• 各カテゴリの最小価格を効率よく管理するために、dict や defaultdict を使うと良い。
• 入力を高速に読み込むために sys.stdin.read を使用している（Pythonでは重要）。
• 存在しないカテゴリがあったら即座に -1 を出力して終了するようにすることで、無駄な計算を省く。

## ソースコード

```python
import sys
from collections import defaultdict
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    idx = 2
    T = list(map(int, data[idx:idx+N]))
    idx += N
    
    # shops[S] = min cost for category S
    shops = {}
    for _ in range(M):
        s = int(data[idx])
        c = int(data[idx+1])
        idx += 2
        if s not in shops:
            shops[s] = c
        else:
            if c < shops[s]:
                shops[s] = c
    
    total_cost = 0
    for t in T:
        if t not in shops:
            print(-1)
            return
        total_cost += shops[t]
    
    print(total_cost)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。