← 返回题目列表

Codeforces · 524/C

C. 处理 ATM 的艺术

中文机器翻译题面 查看原题

某小国知名银行的 ATM 机被安排为无法提供用户要求的任何金额。由于提款机(直接从ATM取款的设备)的尺寸有限以及ATM结构的一些特殊性,您最多可以从中取出k张钞票​​,并且钞票最多可以有两种不同的面额。

例如,如果一个国家使用面额为 10、50、100、500、1000 和 5000 伯尔的钞票,则在 k = 20 时,此类 ATM 可以给出 100,000 伯尔和 96,000 伯尔的总和,但不能给出 99,000 和 101,000 伯尔的总和布尔斯。

假设该国家/地区使用 n 种不同面额的钞票,并且您使用的 ATM 上每种类型的钞票数量不受限制。您知道白天您需要提取一定数量的现金 q 次。大家知道,当ATM机有多种取款方式时,它会选择需要最少张数的取款方式,如果无法完成则显示错误消息。确定q个现金提取请求中每一个的结果。

输入

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

下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 107) — 该国使用的纸币面额。数字 ai 按严格递增的顺序排列。

下一行包含整数 q (1 ≤ q ≤ 20) — 您将提出的现金提取请求数。

接下来的 q 行包含数字 xi (1 ≤ xi ≤ 2·108) — 您要从 ATM 机提取的金额(以 burles 为单位)。

输出

对于每个提现请求,在一行中打印可以完成的最小账单数量,如果无法获得相应的金额,则打印 - 1。

示例

输入 #1

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

输出 #1

6
20
19
20
-1
3
-1
-1

输入 #2

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

输出 #2

1
1
1
2
2
2
2
-1