레이팅 미적용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 \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}\), . . . , \(c_{q}\) (\(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.
Print \(q\) lines. In the \(i\)-th line print the answer to Lana’s \(i\)-th query.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | n, \(q \le 1000\), \(c\)\(i\), k\(i \le 10^{6}\) |
2 | 20점 | \(k_{1}\) = . . . = \(k_{n}\) |
3 | 35점 | No additional constraints. |
5 2
1 9 22 10 19
18 4
5 234
-217 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 54
16
7
13 3
5 6 7
10 1
5 3
3 35
12
0Clarification 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.