CF524C The Art of Dealing with ATM

一个小国的某知名银行的 ATM 设计成无法满足用户请求的任意金额。由于出钞口容量有限以及 ATM 结构特殊，用户一次最多只能取出 $k$ 张钞票，并且这些钞票最多只能包含两种不同面值。 例如，如果一个国家有 $10$、$50$、$100$、$500$、$1000$ 和 $5000$ 巴勒面值的钞票，当 $k=20$ 时，这样的 ATM 可以取到 $100000$ 巴勒和 $96000$ 巴勒，但无法取出 $99000$ 或 $101000$ 巴勒。 现假设该国共有 $n$ 种不同面值的钞票，且当前使用的 ATM 每种面值的钞票数量均无限。你已知今天需要取款 $q$ 次。每次取款时，如有多种方案，ATM 会选择用钞票最少的方案，否则显示错误。请你计算每次取款能否取到所需金额，并输出所需最少的钞票数；无法取出时输出 $-1$。

第一行包含两个整数 $n$、$k$（$1 \leq n \leq 5000$，$1 \leq k \leq 20$）。 第二行包含 $n$ 个严格递增的正整数 $a_i$（$1 \leq a_i \leq 10^7$），表示该国的钞票面值。 第三行包含一个整数 $q$（$1 \leq q \leq 20$），表示你要取款的次数。 接下来的 $q$ 行中，每行一个正整数 $x_i$（$1 \leq x_i \leq 2 \cdot 10^8$），表示你每次取款想要的金额。

每次取款请求输出一行，你能取到所需金额的情况下，输出所需的最少钞票数；否则输出 $-1$。

由 ChatGPT 5 翻译