Problem G
Atomic Energy

Plasma ball by Halacious, Unsplash

Although an atom is composed of various parts, for the purposes of this method only the number of neutrons in the atom is relevant¹. In the method, a laser charge is fired at the atom, which then releases energy in a process formally called explodification. Exactly how this process proceeds depends on the number of neutrons $k$:

• If the atom contains $k \leq n$ neutrons, it will be converted into $a_ k$ joules of energy.

• If the atom contains $k > n$ neutrons, it will decompose into two atoms with $i$ and $j$ neutrons respectively, satisfying $i,j \geq 1$ and $i+j=k$. These two atoms will then themselves explodificate.

When an atom with $k$ neutrons is explodificated, the total energy that is released depends on the exact sequence of decompositions that occurs in the explodification process. Modern physics is not powerful enough to predict exactly how an atom will decompose—however, for explodification to be a reliable energy source, we need to know the minimum amount of energy that it can release upon explodification. You have been tasked with computing this quantity.

Input

The input consists of:

• One line with two integers $n$ and $q$ ($1 \leq n \leq 100$, $1 \leq q \leq 10^5$), the neutron threshold and the number of experiments.

• One line with $n$ integers $a_1,\ldots ,a_ n$ ($1 \leq a_ i \leq 10^9$ for each $i$), where $a_ i$ is the amount of energy released when an atom with $i$ neutrons is explodificated.

• Then $q$ lines follow, each with an integer $k$ ($1 \leq k \leq 10^9$), asking for the minimum energy released when an atom with $k$ neutrons is explodificated.

Output

For each query $k$, output the minimum energy released when an atom with $k$ neutrons is explodificated.

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