← 返回题目列表

AtCoder · awc0084_b

B. 购物计划

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥想购买全部 N 物品写在他的购物清单上,准确购买 每个的 1 。

的 i- 第一项 购物清单上的 (1 \leq i \leq N) 属于类别 T_i。请注意,购物清单可能包含同一类别的多个商品。

有 M 可以购买物品的商店总数。的 j第店 (1 \leq j \leq M) 仅销售类别的商品 S_j,价格为 C_j 每件日元。多个商店可以销售同一类别的商品。每个商店都有无限的库存,因此可以从其中购买任意数量的商品。

对于购物清单上的每件商品,高桥都会选择一家处理该商品类别的商店进行购买。即使对于同一类别的商品,他也可能为每件商品选择不同的商店,或者他可能重复选择同一家商店。

如果购物清单上存在任何一个商店不经营的类别,则不可能购买所有商品。

判断是否可以购买所有物品,如果可以,则输出最小的总购买成本。这里,总购买成本是每个所选商店的价格之和。 购物清单上的 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
  • 第一行包含购物清单上的商品数量 N 及店铺数量 M,用空格分隔。
  • 第二行包含 T_1, T_2, \ldots, T_N,代表每一项的类别,以空格分隔。
  • 以下 M 行包含有关每个商店的信息。
  • 的 (2 + j)第行 (1 \leq j \leq M) 包含类别 S_j 由 j第商店和每件商品的价格 C_j,用空格分隔。

输出

如果可以购买所有物品,则在一行中输出最小的总购买成本。如果无法购买所有物品,则输出 -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