Chocolate Purchase Minimization

You are given n chocolates with distinct prices \(c_1, c_2, \ldots, c_n\). Lana and Fran want to purchase some chocolates. Fran uses the following spending plan when buying a chocolate:

• If the price of the chocolate is less than \(k\), then the entire cost \(c_i\) is paid by Lana.
• If the price is at least \(k\), then Lana pays \(k\) and Fran pays the remaining \(c_i-k\) (so the net contribution is \(2k-c_i\)).

For a set of chosen chocolates, let \(l\) be the total amount Lana pays and \(f\) be the total amount paid by Fran. Thus, for each chocolate, the effective contribution toward the difference \(l-f\) is:

[ \text{diff}(c_i)=\begin{cases} c_i, & \text{if } c_i<k,\ 2k-c_i, & \text{if } c_i\ge k. \end{cases} ]

Lana wishes to choose exactly \(m\) chocolates (from the \(n\) available) such that the total difference \(l-f\) is minimized. In other words, if you denote the chosen set as \(S\) (with \(|S|=m\)), Lana wants to minimize:

[ \sum_{c_i\in S} \text{diff}(c_i). ]

You are given \(q\) queries. In each query, you are provided two integers \(k\) and \(m\). For each query, determine the minimum possible value of \(l-f\) over all choices of \(m\) chocolates.

inputFormat

The first line contains an integer (n) (the number of chocolates). The second line contains (n) space-separated integers (c_1, c_2, \ldots, c_n) representing the prices of the chocolates. The third line contains an integer (q) (the number of queries). Each of the following (q) lines contains two integers (k) and (m), representing a query.

outputFormat

For each query, output the minimum value of (l-f) in a separate line.

sample

5
3 10 20 8 16
3
10 2
15 3
12 4

3
21
23