P9029 [COCI 2022/2023 #1] Čokolade

Lana and Fran are visiting a chocolate factory, and now they want to buy some chocolates.

There are $n$ different chocolates in the factory, and the price of the $i$-th chocolate is $c_i$. Lana and Fran want to buy $m$ chocolates. Fran has a payment plan: - If the chocolate price is less than $k$, the full cost of this chocolate will be paid by Lana. - Otherwise, Lana will pay $k$, and Fran will pay the remaining part, i.e. $c_i-k$. Lana is not happy with Fran's plan and wants to get back at Fran. Let $l$ be the amount Lana needs to pay, and $f$ be the amount Fran needs to pay. Lana will choose a buying plan that minimizes the value of $l-f$. Since Fran is still hesitating and does not know how many chocolates to buy, Lana wants to know, for the given $q$ different plans $k_i$ and $m_i$, the minimum value of $l-f$ for each plan.

The first line contains two integers $n$ and $q$, representing the number of chocolates and the number of queries. The second line contains $n$ integers $c_i$, in order, representing the price of each chocolate. The next $q$ lines each contain two integers $k_i$ and $m_i$, representing Fran's payment threshold and the total number of chocolates to buy.

Output $q$ lines, each containing one integer representing the answer to Lana's query.

| Subtask | Score | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n,q \leq 1000,c_i,k_i\leq 10^6$ | | $2$ | $20$ | All queries have the same $k$ | | $3$ | $35$ | No special properties | For $100\%$ of the data, $1\leq m_i\leq n,q\leq 10^5,1\leq c_i,k_i \leq 10^9$. The full score of this problem is $70$ points. Translated by ChatGPT 5