Problem Background

Lana and Fran are visiting a chocolate factory and now they want to buy some chocolates.

Problem Description

There are $n$ different chocolates in the factory, with the $i$-th chocolate priced at $c_i$. Lana and Fran want to buy $m$ chocolates.

Fran has a spending plan:

• If the chocolate price is less than $k$ dollars, Lana will pay the full amount for this chocolate.
• Otherwise, Lana will pay $k$ dollars, and Fran will pay the remaining part, which is $c_i - k$ dollars.

Lana is dissatisfied with Fran's plan and wants to retaliate. Let $l$ be the amount Lana needs to pay, and $f$ be the amount Fran needs to pay. Lana will choose the purchasing scheme that minimizes the value of $l - f$.

Since Fran is still hesitating and unsure about how many chocolates to buy, Lana wants to know the minimum value of $l - f$ for each of the $q$ different purchasing schemes given $k_i$ and $m_i$.

Input Format

The first line contains two integers $n$ and $q$, representing the number of chocolates and the number of queries, respectively.

The second line contains $n$ integers $c_i$, representing the price of each chocolate in order.

The next $q$ lines each contain two integers $k_i$ and $m_i$, representing Fran's payment threshold and the total number of chocolates to be purchased, respectively.

Output Format

Output $q$ lines, each containing an integer representing the answer to Lana's query.

Sample Input and Output

Sample Input #1

5 2
1 9 22 10 19
18 4
5 2

Sample Output #1

34
-21

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

Notes

For $100\%$ of the data, $1 \leq m_i \leq n, q \leq 10^5, 1 \leq c_i, k_i \leq 10^9$.

This problem is worth $70$ points.

见题面 Input 部分

见题面 Output 部分