B - お買い物プラン 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は買い物リストに書かれた N 個の商品を、それぞれ 1 個ずつすべて購入したいと考えています。

買い物リストの i 番目 (1 \leq i \leq N) の商品のカテゴリは T_i です。なお、買い物リストには同じカテゴリの商品が複数含まれることもあります。

商品を購入できるお店は全部で M 店あります。j 番目 (1 \leq j \leq M) のお店はカテゴリ S_j の商品のみを取り扱っており、1 個あたり C_j 円で販売しています。同じカテゴリを取り扱うお店が複数存在することもあります。また、各お店では在庫の制限なく何個でも購入できます。

高橋君は買い物リストの商品 1 つ 1 つについて、その商品のカテゴリを取り扱っているお店の中から購入先を 1 つ選びます。同じカテゴリの商品であっても、商品ごとに異なるお店を選んで構いませんし、同じお店を繰り返し選んでも構いません。

買い物リストに含まれるカテゴリのうち、どのお店でも取り扱っていないものが 1 つでもある場合、すべての商品を購入することは不可能です。

すべての商品を購入できるかどうかを判定し、可能ならば合計購入金額の最小値を出力してください。ここで合計購入金額とは、買い物リストの N 個の商品それぞれについて選んだお店の価格を合計したものです。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 1 \leq S_j \leq 10^9
  • 1 \leq C_j \leq 10^9
  • 入力はすべて整数である。
  • 答えは 2 \times 10^{14} 以下であることが保証される（購入可能な場合）。

入力

N M
T_1 T_2 \ldots T_N
S_1 C_1
S_2 C_2
\vdots
S_M C_M
  • 1 行目には、買い物リストの商品の数 N と、お店の数 M が、スペース区切りで与えられる。
  • 2 行目には、各商品のカテゴリを表す T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
  • 続く M 行にわたって、各お店の情報が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、j 番目のお店が取り扱うカテゴリ S_j と、1 個あたりの価格 C_j が、スペース区切りで与えられる。

出力

すべての商品を購入できる場合は、合計購入金額の最小値を 1 行で出力せよ。すべての商品を購入することが不可能な場合は -1 を 1 行で出力せよ。

入力例 1

3 3
1 2 1
1 100
1 150
2 200

出力例 1

400

入力例 2

3 2
1 2 3
1 100
2 200

出力例 2

-1

入力例 3

8 7
5 1000000000 5 3 1000000000 3 5 3
5 500
5 300
1000000000 1000000000
1000000000 999999999
3 700
3 600
3 800

出力例 3

2000002698

Score : 300 pts

Problem Statement

Takahashi wants to purchase all N items written on his shopping list, buying exactly 1 of each.

The i-th item (1 \leq i \leq N) on the shopping list belongs to category T_i. Note that the shopping list may contain multiple items of the same category.

There are M shops in total where items can be purchased. The j-th shop (1 \leq j \leq M) sells only items of category S_j, at a price of C_j yen per item. Multiple shops may sell items of the same category. Each shop has unlimited stock, so any number of items can be purchased from it.

For each item on the shopping list, Takahashi chooses exactly one shop that handles that item's category to purchase it from. Even for items of the same category, he may choose a different shop for each item, or he may choose the same shop repeatedly.

If there exists even one category on the shopping list that is not handled by any shop, it is impossible to purchase all items.

Determine whether it is possible to purchase all items, and if so, output the minimum total purchase cost. Here, the total purchase cost is the sum of the prices at the chosen shops for each of the N items on the shopping list.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 1 \leq S_j \leq 10^9
  • 1 \leq C_j \leq 10^9
  • All inputs are integers.
  • It is guaranteed that the answer is at most 2 \times 10^{14} (when purchasing is possible).

Input

N M
T_1 T_2 \ldots T_N
S_1 C_1
S_2 C_2
\vdots
S_M C_M
  • The first line contains the number of items on the shopping list N and the number of shops M, separated by a space.
  • The second line contains T_1, T_2, \ldots, T_N, representing the category of each item, separated by spaces.
  • The following M lines contain information about each shop.
  • The (2 + j)-th line (1 \leq j \leq M) contains the category S_j handled by the j-th shop and the price per item C_j, separated by a space.

Output

If it is possible to purchase all items, output the minimum total purchase cost on a single line. If it is impossible to purchase all items, output -1 on a single line.

Sample Input 1

3 3
1 2 1
1 100
1 150
2 200

Sample Output 1

400

Sample Input 2

3 2
1 2 3
1 100
2 200

Sample Output 2

-1

Sample Input 3

8 7
5 1000000000 5 3 1000000000 3 5 3
5 500
5 300
1000000000 1000000000
1000000000 999999999
3 700
3 600
3 800

Sample Output 3

2000002698