Atomic Energy

문제

The Next Wave Energy Research Club is looking at several atoms as potential energy sources, and has asked you to do some computations to see which are the most promising.

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 fact, for this problem you might want to forget everything you thought you knew about chemistry.). 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 $kk$:

• If the atom contains $k\le nk\; \backslash leq\; n$ neutrons, it will be converted into $a_{k}a\_k$ joules of energy.
• If the atom contains $k>nk\; >\; n$ neutrons, it will decompose into two atoms with $ii$ and $jj$ neutrons respectively, satisfying $i,j\ge 1i,j\; \backslash geq\; 1$ and $i+j=ki+j=k$. These two atoms will then themselves explodificate.

When an atom with $kk$ 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.

입력

The input consists of:

• One line with two integers $nn$ and $qq$ ($1\le n\le 1001\; \backslash leq\; n\; \backslash leq\; 100$, $1\le q\le {10}^{5}1\; \backslash leq\; q\; \backslash leq\; 10^5$), the neutron threshold and the number of experiments.
• One line with $nn$ integers $a_1,\dots ,a_{n}a\_1,\backslash ldots,a\_n$ ($1\le a_i\le {10}^{9}1\; \backslash leq\; a\_i\; \backslash leq\; 10^9$ for each $ii$), where $a_{i}a\_i$ is the amount of energy released when an atom with $ii$ neutrons is explodificated.
• Then $qq$ lines follow, each with an integer $kk$ ($1\le k\le {10}^{9}1\; \backslash leq\; k\; \backslash leq\; 10^9$), asking for the minimum energy released when an atom with $kk$ neutrons is explodificated.

출력

For each query $kk$, output the minimum energy released when an atom with $kk$ 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