“下一波”能源研究俱乐部（Next Wave Energy Research Club）正在寻找几种原子作为潜在的能源，并邀请你进行一些计算，以确定哪些原子最有前景。

虽然原子由多个部分组成，但就本方法而言，只有原子中的中子数是相关的$^\dagger$。在该方法中，激光电荷被发射到原子上，随后原子在一个被称为“爆炸化”（explodification）的过程中释放能量。这个过程具体如何进行取决于中子数 $k$：

Plasma ball by Halacious, Unsplash

• 如果原子包含的中子数 $k \le n$，它将被转化为 $a_k$ 焦耳的能量。
• 如果原子包含的中子数 $k > n$，它将分解为两个中子数分别为 $i$ 和 $j$ 的原子，满足 $i, j \ge 1$ 且 $i + j = k$。这两个原子随后也会进行爆炸化。

当一个含有 $k$ 个中子的原子进行爆炸化时，释放的总能量取决于爆炸化过程中发生的具体分解序列。现代物理学还不足以精确预测原子将如何分解——然而，为了使爆炸化成为一种可靠的能源，我们需要知道它在爆炸化时可能释放的最小能量。你的任务就是计算这个数值。

输入格式

输入包含：

• 第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 100, 1 \le q \le 10^5$)，分别表示中子阈值和实验次数。
• 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$，对于每个 $i$)，其中 $a_i$ 表示含有 $i$ 个中子的原子爆炸化时释放的能量。
• 接下来 $q$ 行，每行包含一个整数 $k$ ($1 \le k \le 10^9$)，询问含有 $k$ 个中子的原子爆炸化时释放的最小能量。

输出格式

对于每个查询 $k$，输出含有 $k$ 个中子的原子爆炸化时释放的最小能量。

$^\dagger$ 事实上，对于这个问题，你可能需要忘记你所知道的关于化学的一切。

样例

输入格式 1

4 5
2 3 5 7
2
3
5
6
8

输出格式 1

3
5
8
10
13

输入格式 2

1 3
10
1
2
100

输出格式 2

10
20
1000