题目背景

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 询问的答案。

5 2
1 9 22 10 19
18 4
5 2

34
-21

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

4
16
7
1

3 3
5 6 7
10 1
5 3
3 3

5
12
0

提示

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

本题满分 $70$ 分。