分数: 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