The Art of Dealing with ATM

Problem 某国的ATM取款机可以提供n种不同面值的纸币，每种面值的纸币的数量可以视为无限。但是该取款机有特殊的限制，一次取款最多出k张纸币，而且最多包含两种不同的面值的纸币。 比如，有6种不同的纸币，10，50，100，500，1000和5000，当k=20时，你可以取出100000或者96000，但是不能取99000和101000。 现在你一共要取q次钱，请计算每次取钱ATM取款机最少吐出多少张纸币，如果某个金额没有办法构成，输出错误信息。 Input Data 第一行，两个整数n和k。(1≤n≤5000,1≤k≤20)。 第二行，n个整数a_i ，表示n种不同的面值a_i(1≤a ​i ​​ ≤10^7)，按从小到大的顺序给出。 第三行，一个整数q，表示有q(1≤q≤20)次取钱。 接下来q行，每行一个整数x_i ​​ (1≤x_i ≤2×10^8),表示每次取钱的数量。 Output Data 输出共k行，每行一个整数，依次表示每次取钱最少的纸币张数，无解则输出-1。

ATMs of a well-known bank of a small country are arranged so that they can not give any amount of money requested by the user. Due to the limited size of the bill dispenser (the device that is directly giving money from an ATM) and some peculiarities of the ATM structure, you can get at most $ k $ bills from it, and the bills may be of at most two distinct denominations. For example, if a country uses bills with denominations $ 10 $ , $ 50 $ , $ 100 $ , $ 500 $ , $ 1000 $ and $ 5000 $ burles, then at $ k=20 $ such ATM can give sums $ 100000 $ burles and $ 96000 $ burles, but it cannot give sums $ 99000 $ and $ 101000 $ burles. Let's suppose that the country uses bills of $ n $ distinct denominations, and the ATM that you are using has an unlimited number of bills of each type. You know that during the day you will need to withdraw a certain amount of cash $ q $ times. You know that when the ATM has multiple ways to give money, it chooses the one which requires the minimum number of bills, or displays an error message if it cannot be done. Determine the result of each of the $ q $ of requests for cash withdrawal.

The first line contains two integers $ n $ , $ k $ ( $ 1<=n<=5000 $ , $ 1<=k<=20 $ ). The next line contains $ n $ space-separated integers $ a_{i} $ ( $ 1<=a_{i}<=10^{7} $ ) — the denominations of the bills that are used in the country. Numbers $ a_{i} $ follow in the strictly increasing order. The next line contains integer $ q $ ( $ 1<=q<=20 $ ) — the number of requests for cash withdrawal that you will make. The next $ q $ lines contain numbers $ x_{i} $ ( $ 1<=x_{i}<=2·10^{8} $ ) — the sums of money in burles that you are going to withdraw from the ATM.

For each request for cash withdrawal print on a single line the minimum number of bills it can be done, or print $ -1 $ , if it is impossible to get the corresponding sum.

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

5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15

1
1
1
2
2
2
2
-1