COCI '22 Contest 1 #2 Čokolade

View as PDF

Submit solution

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

Input Specification

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

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

The following q lines contain integers k_i and m_i (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 lines. In the i-th line print the answer to Lana's i-th query.

Constraints

Subtask Points Constraints
1 15 n, q \le 1\,000; c_i, k_i \le 10^6
2 20 k_1 = \dots = k_n
3 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, 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.

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

Comments

There are no comments at the moment.