小拉娜（Lana）和小弗兰（Fran）正在参观一家巧克力工厂。他们参观了巧克力的制作过程，品尝了许多巧克力，现在他们想买一些巧克力。

商店里有 $n$ 种不同的巧克力，第 $i$ 种巧克力的价格为 $c_i$。拉娜和弗兰想要购买 $m$ 块巧克力。

弗兰在店里找到了一种分摊费用的方法：

• 如果巧克力的价格低于 $k$ 库纳，则由拉娜支付。
• 否则，拉娜支付 $k$ 库纳，剩下的部分（即 $c_i - k$ 库纳）由弗兰支付。

设 $l$ 为拉娜需要支付的总金额，$f$ 为弗兰需要支付的总金额。拉娜对弗兰的方案感到不满，她想通过选择巧克力来刁难弗兰，使得表达式 $l - f$ 的值尽可能小。由于弗兰犹豫不决，不知道自己想买多少块巧克力，拉娜想知道对于 $q$ 组不同的 $k_i$ 和 $m_i$，表达式 $l - f$ 的最小值是多少。

请帮助她选择巧克力，并确定每组查询中 $l - f$ 的最小值。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示巧克力的数量和查询的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，按顺序表示每块巧克力的价格。

接下来的 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$ ($1 \le k_i \le 10^9, 1 \le m_i \le n$)，分别表示弗兰设定的价格界限以及他们要购买的巧克力数量。

输出格式

输出 $q$ 行。第 $i$ 行输出拉娜第 $i$ 次查询的答案。

子任务

样例

输入格式 1

5 2
1 9 22 10 19
18 4
5 2

输出格式 1

34
-21

说明 1

在第一次查询中，拉娜可以选择价格为 1, 9, 22, 10 的巧克力。拉娜将支付 38 库纳，弗兰支付 4 库纳。答案为 $38 - 4 = 34$。

在第二次查询中，拉娜可以选择价格为 22 和 19 的巧克力。她将支付 10 库纳，弗兰支付 31 库纳。答案为 $10 - 31 = -21$。

输入格式 2

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

输出格式 2

4
16
7
1

输入格式 3

3 3
5 6 7
10 1
5 3
3 3

输出格式 3

5
12
0