题目描述

在国家牛奶日，农夫约翰正在提供桶装牛奶的独家优惠！他有 $N$（$1 \leq N \leq 10^5$）个交易，编号从 $1$ 到 $N$。对于第 $i$ 个交易，他以 $a_i$（$1 \leq a_i \leq 10^9$，$a_i < a_{i+1}$）牛币的价格提供 $2^{i-1}$ 桶牛奶。同一个交易可以被购买任意非负整数次。

你正在考虑 $Q$（$1 \leq Q \leq 10^4$）个独立的询问。对于每个询问，你心中有一个整数 $x$（$1 \leq x \leq 10^9$），你想知道购买至少 $x$ 桶牛奶的最小成本。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

接下来的一行包含 $a_1, a_2, \ldots, a_N$。

接下来的 $Q$ 行，每行包含一个整数 $x$，表示一个询问。

输出格式

对于每个询问，在新的一行输出最小成本。

注意：本题中可能涉及大整数，需要使用 64 位整数数据类型（例如，C/C++ 中的 long long）。

输入输出样例 #1

输入 #1

2 4
10 15
1
2
6
7

输出 #1

10
15
45
55

输入输出样例 #2

输入 #2

4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101

输出 #2

10
20
30
30
40
50
60
60
120
760

说明/提示

样例 1 解释

在上面的例子中，农夫约翰提供两个交易：1 桶牛奶 10 牛币和 2 桶牛奶 15 牛币。 购买 1 桶牛奶的最便宜成本就是 1 桶交易的价格，购买 2 桶牛奶的最便宜成本就是 2 桶交易的价格。

要获得 6 桶牛奶，最便宜的方式是购买 3 次 2 桶交易，总共 45 牛币。

要获得 7 桶牛奶，最便宜的方式是购买 3 次 2 桶交易和 1 次 1 桶交易，总共 55 牛币。

样例 2 解释

在这个例子中，农夫约翰总共提供 4 个交易，分别对应 1、2、4、8 桶牛奶。对于这 10 个询问，对应的输出表示购买至少指定数量牛奶的最小成本。有时，购买超过指定数量的牛奶反而更便宜。

评分

• 输入 3-4：$N \leq 2$
• 输入 5-8：$N \leq 10$
• 输入 9-16：无额外约束。

翻译由 DeepSeek 完成