Universal ATM

You are developing a Universal ATM that supports n banknote denominations \(a_1, a_2, \ldots, a_n\) in strictly increasing order (i.e. \(a_1=1\) and for every \(i>1,\ a_i > a_{i-1}\)). When a customer requests an amount \(c\), the ATM dispenses money using the following greedy algorithm:

1. While the total dispensed is less than \(c\), choose the largest denomination that does not cause the total to exceed \(c\).
2. Dispense that banknote and update the total.

Since there is always a banknote of denomination 1, this algorithm terminates for every \(c\). To evaluate its efficiency, you want to know, for a given number \(b\), what is the maximum number of banknotes that might be dispensed over all requests \(c\) with \(1 \le c \le b\). In other words, if we define a function \(f(c)\) which is the number of banknotes given by the ATM for request \(c\) (as computed by the above greedy algorithm), your task is to compute

[ \max_{1 \le c \le b} f(c). ]

You are given the list of denominations and have to answer \(q\) independent scenarios with values \(b_1, b_2, \ldots, b_q\).

Greedy Algorithm Details

For an amount \(x\), the ATM does:

[ f(x) = \begin{cases} x, &\text{if }x < a_2,
1 + f(x - d), &\text{where }d=\max{a_i, :, a_i \le x} \quad (x \ge a_2). \end{cases} ]

Notice that when \(x\) is large enough, the largest available denomination will be \(a_n\) and if \(x \ge a_n\) then greedy always picks \(a_n\) so that

[ f(x) = \left\lfloor \frac{x}{a_n} \right\rfloor + f\Bigl(x \bmod a_n\Bigr). ]

You can precompute the values of \(f(x)\) for \(0 \le x

[ M = \max_{0 \le x < a_n} f(x). ]

Then for a query with \(b \ge a_n\), if we write \(b = k \cdot a_n + r\) with \(0 \le r

[ \max\Bigl{ (k-1) + M,; k + \max_{0 \le x \le r} f(x) \Bigr} \quad (\text{if } k \ge 1), ]

and if (b < a_n) simply by (\max_{1 \le x \le b} f(x).)

inputFormat

The first line contains two integers \(n\) and \(q\) (the number of denominations and the number of queries).

The second line contains \(n\) space‐separated integers \(a_1, a_2, \ldots, a_n\) in strictly increasing order with \(a_1 = 1\).

Each of the following \(q\) lines contains a single integer \(b_i\) representing a business scenario.

outputFormat

For each query, output a single integer on its own line representing the maximum number of banknotes the ATM will dispense for some request \(c\) with \(1 \le c \le b_i\).

sample

3 3
1 3 4
7
8
11

3
3
4