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

题目背景

星港即将启动一次远航任务。补给官需要从星仓中调配能量包：不同型号的能量包容量成倍增长，但价格并不一定按容量线性增长。

为了避免飞船在途中缺能，补给量可以超过计划需求；你的任务是为每一次补给申请算出最低能源花费。

题目描述

星仓正在准备一批远航补给。仓库中共有 $N$ 种补给包，第 $i$ 种补给包恰好包含 $2^{i-1}$ 单位补给，购买一个第 $i$ 种补给包需要花费 $a_i$ 点能源。

每种补给包都可以购买任意多个，价格不会随购买数量变化。

现在有 $Q$ 次独立询问。每次询问给定一个整数 $x$，你需要求出购买至少 $x$ 单位补给的最小花费。注意，可以购买超过 $x$ 单位，只要总量不少于 $x$ 即可。

输入格式

第一行包含两个整数 $N,Q$，表示补给包种类数和询问数。

第二行包含 $N$ 个整数 $a_1,a_2,\dots,a_N$，表示每种补给包的价格。

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

输出格式

对每次询问，输出一行一个整数，表示购买至少 $x$ 单位补给的最小花费。

样例

输入 1

2 4
10 15
1
2
6
7

输出 1

10
15
45
55

输入 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$ 种补给包包含 $1$ 单位，价格为 $10$；第 $2$ 种补给包包含 $2$ 单位，价格为 $15$。

若需要至少 $6$ 单位，可以购买 $3$ 个第 $2$ 种补给包，花费 $45$。若需要至少 $7$ 单位，可以购买 $3$ 个第 $2$ 种补给包和 $1$ 个第 $1$ 种补给包，花费 $55$。

样例 2 中，有时购买超过需求量会更便宜。例如需要至少 $7$ 单位时，购买一个包含 $8$ 单位的补给包只需 $70$，但购买两个包含 $4$ 单位的补给包只需 $60$。

数据范围

对于所有测试数据，满足：

• $1\le N\le 10^5$；
• $1\le Q\le 10^4$；
• $1\le a_i\le 10^9$；
• $a_i<a_{i+1}$；
• $1\le x\le 10^9$。

子任务