该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

你需要处理 $Q$（$1 \leq Q \leq 10^4$）个独立的查询。对于每个查询，你有一个整数 $x$（$1 \leq x \leq 10^9$），想知道购买至少 $x$ 桶牛奶的最小成本是多少。

输入格式

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

第二行包含 $a_1, a_2, \dots, a_N$，表示每个优惠的价格。

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

输出格式

对于每个查询，输出一行，表示购买至少 $x$ 桶牛奶的最小成本。

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

样例

2 4
10 15
1
2
6
7

10
15
45
55

样例解释

农夫约翰提供 2 个优惠：

• 优惠 1：1 桶牛奶，价格 10 月亮币

• 优惠 2：2 桶牛奶，价格 15 月亮币

• 购买 1 桶：直接使用优惠 1，成本 10

• 购买 2 桶：直接使用优惠 2，成本 15

• 购买 6 桶：购买 3 次优惠 2（3 × 15 = 45）

• 购买 7 桶：购买 3 次优惠 2 和 1 次优惠 1（45 + 10 = 55）

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

10
20
30
30
40
50
60
60
120
760

样例解释

农夫约翰提供 4 个优惠，分别对应 1、2、4、8 桶牛奶。输出显示购买至少指定数量牛奶的最小成本。有时购买多于所需数量反而更便宜。

数据规模与约定

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