问题 5418 --糖果超甜

5418: 糖果超甜★★★

时间限制: 4 Sec  内存限制: 256 MB
提交: 78  解决: 44
[提交][状态][命题人:]

题目描述

嘉航有 n 种糖果,第 i 种糖果的糖分为 a[i] 。嘉航每天只会吃 q 次糖果,第 j 次进食时他摄取的糖分下限为 x[j] 。嘉航希望每次吃尽量少的糖果,他觉得这样比较健康。对于第 j 次进食,请你帮助嘉航找出最少的糖果数量 k,k 颗糖的糖分之和大于等于 x[j] ;如果不存在这样的 k,请输出 -1。

注意:每次进食时,每种糖果嘉航最多只能吃 1 次。

输入

第一行为 1 个整数 t(1<=t<=1000),代表有 t 组测试数据;

每组测试数据的第一行为 2 个整数 n,q(1<=n,q<=1.5e5),分别代表糖果总数与进食次数。

第二行为 n 个整数 a[1],...,a[n](1<=a[i]<=1e4),代表第 i 种糖果的糖分;

接下来的 q 行,每行一个正数 x[j](1<=x[j]<=2e9),代表嘉航第 j 次进食时希望获取的糖分下限。

保证对于所有测试数据,q 之和不会超过 1.5e5 。

输出

共有 q 行,每行输出一个整数 k 或 -1 ,代表嘉航至少要吃 k 颗糖或是答案不存在
样例输入
Copy
3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6
样例输出
Copy
1
2
-1
2
3
4
8
1
1
-1

提示

来源

 

[提交][状态]