【题目描述】

小拉娜和小弗兰正在参观巧克力工厂。他们看到了巧克力做好了，尝了很多巧克力，现在又想买一些巧克力。

在商店里，有n种不同的巧克力，第i种巧克力有价格ci。 

拉娜和小弗兰想买巧克力。

小弗兰找到了一个分摊成本的方法:

•如果巧克力比k 库纳便宜，拉娜会付钱。

•否则，拉娜 将支付k库纳，而弗兰将支付剩余的，即ci - k库纳。

我们设l为拉娜需要支付的金额，f为弗兰需要支付的金额。拉娜,不满意在与弗兰的交易中，他想要激怒弗兰并选择巧克力，因此表达式l−f的值为越小越好。由于弗兰犹豫不决，不知道自己想买多少，Lana想买知道q个不同的数ki和mi时表达式l - f的最小值．

请帮助她选择巧克力，并确定每个q的表达式l - f的最小值。

【输入格式】

第一行包含两个整数n和q(1≤n, q≤10^5))，表赤巧克力的数量，以及

查询。

第二行包含n个整数c1, c2，…， cq(1≤ci≤10^9)，表示巧克力的价格。

下面的q行包含整数ki和mi(1≤ki≤10^9)，1≤mi≤n)， Fran界，和

他们要买多少巧克力。

【输出格式】

打印q行。在第i行打印Lana的第i个查询的答案。

【输入样例一】

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

【样例一说明】

在第一个查询中，Lana可以选择价格为1、9、22和10的巧克力。拉娜会付38库纳，弗兰4 kuna。答案是38−4 = 34。

在第二个查询中，Lana将选择价格为22和19的巧克力。她会付10库纳，弗兰会付31库纳。答案是10−31 =−21。

【数据约束】