主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 A: Furude_Rika and coins

问题 A: Furude_Rika and coins

时间限制: 10 Sec  内存限制: 256 MB
提交: 85  解决: 30
[提交][状态][讨论版]

题目描述

Furude_Rika 有n种硬币,每种硬币的价值都是一定的,且数量都是无限的。
现在有q次查询,每次查询只有一个数字m,求在只用不超过两种硬币,且使用硬币的总数不大于给定的一个数s的条件下,
最少要多少枚硬币才能使他们的价值之和为m。如果无法构造出m或者答案大于s,则输出-1。

输入

第一行两个数n,s(n<=5000,s<=100) 代表硬币种数和给定的数
之后一行n个整数(均小于等于100000且大于0) 代表对应的硬币的价值

之后一行一个整数q(q<=1000) 代表查询次数
之后q行每行一个整数m 代表查询的价值(q<=1000,1<=m<=10000000)

输出

每行输出一个整数即为答案。

样例输入

6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950

样例输出

6
20
19
20
-1
3
-1
-1

提示

对于第一组4200的查询 很明显是用4枚1000的硬币和2枚100的硬币组成的 答案为6


而对于第一组99000的查询 很明显最少需要19枚5000的硬币和4枚1000的硬币 答案为23 由于大于s 则输出-1


有个很关键的点 s是在查询之前给的 而且只给了一次


另外 请注意时限


[提交][状态][讨论版]