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, and the price of the $i$-th chocolate is $c_i$. Lana and Fran want to buy $m$ chocolates.

Fran has a payment plan:

• If the chocolate price is less than $k$, the full cost of this chocolate will be paid by Lana.
• Otherwise, Lana will pay $k$, and Fran will pay the remaining part, i.e. $c_i-k$.

Lana is not happy with Fran's plan and wants to get back at Fran. Let $l$ be the amount Lana needs to pay, and $f$ be the amount Fran needs to pay. Lana will choose a buying plan that minimizes the value of $l-f$.

Since Fran is still hesitating and does not know how many chocolates to buy, Lana wants to know, for the given $q$ different plans $k_i$ and $m_i$, the minimum value of $l-f$ for each plan.

Input Format

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

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

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 buy.

Output Format

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

5 2
1 9 22 10 19
18 4
5 2

34
-21

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

4
16
7
1

3 3
5 6 7
10 1
5 3
3 3

5
12
0

Hint

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

The full score of this problem is $70$ points.

Translated by ChatGPT 5