P9029 [COCI 2022/2023 #1] Čokolade

Lana 和 Fran 正在参观一家巧克力工厂，现在他们想买些巧克力。

巧克力工厂里有 $n$ 块不同的巧克力，其中第 $i$ 块的价格为 $c_i$。Lana 和 Fran 想买 $m$ 块巧克力。 Fran 有一个消费方案： •如果巧克力价格低于 $k$ 元，这块巧克力的费用将全部由 Lana 支付。 •否则，Lana 将支付 $k$ 元，而 Fran 将支付其余的部分，即 $c_i−k$ 元。 Lana 对 Fran 的方案不满意，想要报复 Fran。设 $l$ 为 Lana 需要支付的金额，$f$ 为 Fran 需要支付的金额。Lana 将选择使 $l−f$ 的值最小的购买方案。 由于 Fran 还在犹豫，不知道要买多少巧克力，所以 Lana 想知道对于给出的 $q$ 种不同的购买方案 $k_i$ 和 $m_i$，每种方案 $l−f$ 的最小值。

第一行包含两个整数 $n$ 和 $q$，分别表示巧克力的数量和询问数量。 第二行包含 $n$ 个整数 $c_i$，依次表示每块巧克力的价格。 接下来 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$，分别表示 Fran 的付款阈值和购买的巧克力总数量。

输出 $q$ 行，每行一个整数表示 Lana 询问的答案。

| 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n,q \leq 1000,c_i,k_i\leq 10^6$ | | $2$ | $20$ | 所有询问的 $k$ 都相等 | | $3$ | $35$ | 无特殊性质 | 对于 $100\%$ 的数据，$1\leq m_i\leq n,q\leq 10^5,1\leq c_i,k_i \leq 10^9$。 本题满分 $70$ 分。