COCI '22 Contest 1 #2 Čokolade

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

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

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

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

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

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

Input Specification

The first line contains two integers $n$ ~n~ and $q$ ~q~ $(1 \le n, q \le 10^5)$ ~(1 \le n, q \le 10^5)~, the number of chocolates, and the number of queries.

The second line contains $n$ ~n~ integers $c_1, c_2, \dots, c_n$ ~c_1, c_2, \dots, c_n~ $(1 \le c_i \le 10^9)$ ~(1 \le c_i \le 10^9)~, the prices of the individual chocolates, in order.

The following $q$ ~q~ lines contain integers $k_i$ ~k_i~ and $m_i$ ~m_i~ $(1 \le k_i \le 10^9, 1 \le m_i \le n)$ ~(1 \le k_i \le 10^9, 1 \le m_i \le n)~, Fran's bound, and the number of chocolates they are going to buy.

Output Specification

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

Constraints

Subtask	Points	Constraints
$1$ ~1~	$15$ ~15~	$n, q \le 1\,000$ ~n, q \le 1\,000~; $c_i, k_i \le 10^6$ ~c_i, k_i \le 10^6~
$2$ ~2~	$20$ ~20~	$k_1 = \dots = k_n$ ~k_1 = \dots = k_n~
$3$ ~3~	$35$ ~35~	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 $1$ ~1~, $9$ ~9~, $22$ ~22~, and $10$ ~10~. Lana will pay $38$ ~38~ kunas, and Fran $4$ ~4~ kunas. The answer is $38 - 4 = 34$ ~38 - 4 = 34~.

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

Sample Input 2

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

Sample Output 2

Sample Input 3

Sample Output 3

5
12
0

Comments

There are no comments at the moment.