
Little Lana and little Fran are visiting a chocolate factory. They have seen how chocolate is made, tasted many chocolates, and now they want to buy some of the chocolates.
In the shop, there are different chocolates, and the
-th of them has the price
. Lana and Fran want to buy
chocolates.
Fran found a way to split the cost in the shop:
- If the chocolate is cheaper than
kunas, Lana will pay for it.
- Otherwise, Lana will pay
kunas, and Fran will pay the rest, that is
kunas.
Let's denote as the amount Lana has to pay, and
as the amount Fran has to pay. Lana, dissatisfied
with Fran's deal, wants to spite Fran and choose the chocolates so the value of the expression
is as
small as possible. Since Fran is hesitant and doesn't know how many he wants to buy, Lana wants to
know the minimal value of the expression
for
different numbers
and
.
Help her choose the chocolates and determine the minimum value of the expression for each of the
queries.
Input Specification
The first line contains two integers and
, the number of chocolates, and the number of
queries.
The second line contains integers
, the prices of the individual chocolates, in
order.
The following lines contain integers
and
, Fran's bound, and the
number of chocolates they are going to buy.
Output Specification
Print lines. In the
-th line print the answer to Lana's
-th query.
Constraints
Subtask | Points | Constraints |
---|---|---|
No additional constraints. |
Sample Input 1
5 2
1 9 22 10 19
18 4
5 2
Sample Output 1
34
-21
Explanation for Sample Output 1
In the first query, Lana can take chocolates with prices ,
,
, and
. Lana will pay
kunas, and Fran
kunas. The answer is
.
In the second query, Lana will choose chocolates with prices and
. She will pay
kunas, and Fran
will pay
kunas. The answer is
.
Sample Input 2
7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5
Sample Output 2
4
16
7
1
Sample Input 3
3 3
5 6 7
10 1
5 3
3 3
Sample Output 3
5
12
0
Comments