问题 5419 --特殊的硬币

5419: 特殊的硬币★★

时间限制: 2 Sec  内存限制: 256 MB
提交: 150  解决: 64
[提交][状态][命题人:]

题目描述

嘉航拥有 n 枚硬币,第 i 枚硬币的面额为 a[i],保证 a[i] 是 2 的非负整数幂(即对于某个非负整数 d ,a[i] = 2^d)。

嘉航会用这些硬币做 q 次游戏,第 j 次游戏嘉航都会获得一个正整数 b[j],嘉航希望能用尽可能少的硬币来凑出这个正整数 b[j] ,如果嘉航无法用他的硬币凑出 b[j] ,则输出 -1。

每次游戏都是独立的,不会影响到嘉航拥有的硬币,嘉航只能用他拥有的硬币来做游戏。

输入

第一行为 2 个整数 n,q(1<=n,q<=2e5),分别代表嘉航拥有的硬币数量与游戏次数。

第二行为 n 个整数 a[1],...,a[n](1<=a[i]<=2e9),分别代表第 i 枚硬币的面额,保证 a[i] 是 2 的非负整数幂(即对于某个非负整数 d ,a[i] = 2^d)。

接下来的 q 行,每行输入 1 个整数 b[j](1<=b[j]<=1e9),分别代表第 j 次游戏时嘉航想要凑出的正整数。

输出

共有 q 行,对于第 j 行,如果嘉航能用他的硬币凑出 b[j],则输出所需的最小硬币数 k ,否则输出 -1。 
样例输入
Copy
5 4
2 4 8 2 4
8
5
14
10
样例输出
Copy
1
-1
3
2

提示

对于样例数据中的第 1 次游戏,嘉航有多种方法凑出 8,但是使用 1 枚面额为 8 的硬币能获得最小的答案。

来源

 

[提交][状态]