P17026 [NWERC 2020] 原子能 / Atomic Energy

译自 [Northwestern Europe Regional Contest (NWERC) 2020](http://2020.nwerc.eu)。

“下一波能源研究俱乐部”（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$ 个中子的原子被爆能化时释放的最小能量。

【数据规模与约定】 - $1 \le n \le 100$。 - $1 \le q \le 10^5$。 - $1 \le a_i \le 10^9$。 - $1 \le k \le 10^9$。