问题 N: ATM机器

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:43 通过:10

题目描述

        某国的ATM取款机可以提供n种不同面值的纸币,每种面值的纸币的数量可以视为无限。但是该取款机有特殊的限制,一次取款最多出k张纸币,而且最多包含两种不同的面值的纸币。

        比如,有6种不同的纸币,10,50,100,500,1000和5000,当k=20时,你可以取出100000或者96000,但是不能取99000和101000。

        现在你一共要取q次钱,请计算每次取钱ATM取款机最少吐出多少张纸币,如果某个金额没有办法构成,输出错误信息。

输入格式

第一行,两个整数n和k。(1≤n≤5000,1≤k≤20)。

第二行,n个整数a_i ,表示n种不同的面值a_i(1≤ai ≤10^7),按从小到大的顺序给出。

第三行,一个整数q,表示有q(1≤q≤20)次取钱。

接下来q行,每行一个整数x_i (1≤x_i ≤2×10^8),表示每次取钱的数量。

输出格式

输出共k行,每行一个整数,依次表示每次取钱最少的纸币张数,无解则输出-1。
Examples
Input
6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950
Output
6
20
19
20
-1
3
-1
-1
Input
5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15
Output
1
1
1
2
2
2
2
-1

输入样例 复制

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