Background

Simplified statement: $\texttt{Link}$.

Problem Description

Your initial ability is $0$.

There are $n$ problem sets. In the $i$-th set, all problems have the same difficulty $a_i$, and the number of problems can be considered infinite. Now you need to solve $m$ problems. Each time, you choose one problem from all available problems.

Suppose the difficulty of the problem you are currently solving is $x$. Then:

• If your ability is greater than or equal to $x$, you will spend your ability to defeat this problem (your ability decreases by $x$).
• Otherwise, you will study this problem carefully. After you figure it out, your ability increases by $x$ (this does not cause your ability to decrease).

Now you want to know the maximum possible ability after solving $m$ problems. Since your friends also want to solve problems, there are multiple queries. The queries are independent, meaning that in each query your initial ability is $0$.

Input Format

The first line contains $2$ integers $n, T$.

The second line contains $n$ integers, representing the array $a$.

The next $T$ lines each contain one integer, representing a query.

Output Format

For each query, output the corresponding result.

5 3
1 2 3 4 6
1
2
3

6
10
11

1 2
1
1
2

1
0

Hint

• Sample $1$ explanation:

  When $m=1$, choose $6$ in order.

  When $m=2$, choose $4,6$ in order.

  When $m=3$, choose $1,4,6$ in order.

• Sample $2$ explanation:

  When $m=1$, choose $1$ in order.

  When $m=2$, choose $1,1$ in order.

This problem uses bundled Subtask testdata.

For $100\%$ of the data, $1 \le T \le 10^5$, $1 \le n\le 2000$, $1 \le m \le 10^{18}$, and $\forall i,0 \le a_i \le 2000$。

Translated by ChatGPT 5