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 \leq n, q \leq 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 \leq c_{i} \leq 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 \leq k_{i} \leq 10^{9}, 1 \leq m_{i} \leq 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 \leq 1 000$ ; $c_i, k_i \le 10^6$ $c_{i}, k_{i} \leq 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

Copy

5 2
1 9 22 10 19
18 4
5 2

Sample Output 1

Copy

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

Copy

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

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

5
12
0

Comments

There are no comments at the moment.