样例文件

题目描述

某商场正在对某种商品进行促销。

商场对该种商品提供了 $N$ 种促销券。顾客只能使用促销券购买该种商品。使用第 $k$ $(1 ≤ k ≤ N)$ 种促销券，顾客可以花 $C_k$ 的价钱购买到 $2^{k-1}$ 件商品。当然，如果 $i < j$，则 $C_i < C_j$ $(1 ≤ i < j ≤ N)$。

顾客可以选择使用任意种促销券购买商品。对于任意一种促销券，顾客可以选择使用任意次。

有 $T$ 个顾客，第 $i$ 个顾客想要得到至少 $M_i$ 件商品。

假设该商品的数量是无限的。

问：每个顾客至少需要花费多少钱？

输入格式

第一行：两个整数 $N, T$，分别表示促销券种数和顾客数量。

第二行：$N$ 个严格升序排列的整数 $C_1, C_2, …, C_N$。

接下来 $T$ 行，每行一个整数 $M_i$，表示第 $i$ 个顾客至少想要得到的商品数量。

输出格式

共 $T$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 个顾客需要的最少花费。

输入样例

3 4
20 30 40
1
2
3
10

输出样例

20
30
40
110

数据范围

100% 的数据：$1 ≤ N ≤ 10^5$, $1 ≤ C_k ≤ 10^9$, $1 ≤ T ≤ 10^4$, $1 ≤ M_i ≤ 10^9$。其中

• 15% 的数据：$N ≤ 2$
• 25% 的数据：$N ≤ 10$