26393번 - Čokolade 서브태스크다국어

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 n different chocolates, and the i-th of them has the price c_i. Lana and Fran want to buy m chocolates.

Fran found a way to split the cost in the shop:

• If the chocolate is cheaper than k kunas, Lana will pay for it.
• Otherwise, Lana will pay k kunas, and Fran will pay the rest, that is c_i − k kunas.

Let’s denote l as the amount Lana has to pay, and f 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 l − f 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 l − f for q different numbers k_i and m_i.

Help her choose the chocolates and determine the minimum value of the expression l − f for each of the q queries.

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵), the number of chocolates, and the number of queries.

The second line contains n integers c₁, c₂, . . . , c_q (1 ≤ c_i ≤ 10⁹), the prices of the individual chocolates, in order.

The following q lines contain integers k_i and m_i (1 ≤ k_i ≤ 10⁹, 1 ≤ m_i ≤ n), Fran’s bound, and the number of chocolates they are going to buy.

Print q lines. In the i-th line print the answer to Lana’s i-th query.

Clarification of the first example:

In the first query, Lana can take chocolates with prices 1, 9, 22, and 10. Lana will pay 38 kunas, and Fran 4 kunas. The answer is 38 − 4 = 34.

In the second query, Lana will choose chocolates with prices 22 and 19. She will pay 10 kunas, and Fran will pay 31 kunas. The answer is 10 − 31 = −21.