背景

译自 Northwestern Europe Regional Contest (NWERC) 2020。

题目描述

“下一波能源研究俱乐部”（Next Wave Energy Research Club）正在研究若干原子，看看它们是否可能成为潜在的能源来源。为了判断哪些原子最有前景，他们请你做一些计算。

虽然一个原子由许多部分组成，但在这个方法中，唯一相关的是原子中中子的数量。事实上，在这道题里，你可能应该忘掉你原本以为自己知道的所有化学知识。在这种方法中，会向原子发射一束激光电荷，原子随后会在一个正式称为“爆能化”（explodification）的过程中释放能量。这个过程具体如何进行，取决于中子的数量 $k$：

• 如果该原子含有 $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,\ldots,a_n$（对每个 $i$，有 $1 \le a_i \le 10^9$），其中 $a_i$ 表示一个含有 $i$ 个中子的原子被爆能化时释放的能量。
• 接下来 $q$ 行，每行包含一个整数 $k$（$1 \le k \le 10^9$），询问一个含有 $k$ 个中子的原子被爆能化时，最少会释放多少能量。

输出格式

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

4 5
2 3 5 7
2
3
5
6
8

3
5
8
10
13

1 3
10
1
2
100

10
20
1000

提示

【数据规模与约定】

• $1 \le n \le 100$。
• $1 \le q \le 10^5$。
• $1 \le a_i \le 10^9$。
• $1 \le k \le 10^9$。