P15256 [USACO26JAN2] Purchasing Milk B

在国家牛奶日，农夫约翰正在提供桶装牛奶的独家优惠！他有 $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 桶牛奶 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 完成