第 1 题 Čokolade (okolade)

CSP-S 复赛模拟赛 22 · 时间限制 1.0 s · 空间限制 256 MB · 40 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 okolade.in，输出文件 okolade.out。

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

输入：

5 2
1 9 22 10 19
18 4
5 2

输出：

34
-21

样例 2

输入：

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

输出：

4
16
7
1

样例 3

输入：

3 3
5 6 7
10 1
5 3
3 3

输出：

5
12
0

提示

对于 100% 的数据，$1 \le m_i \le n, q \le 10^5$，$1 \le c_i, k_i \le 10^9$。

本题满分 70 分。