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