C.买单

小聪和小潘出去旅游。他们都是选择困难症，他们决定今天先一次性把接下来 $m$ 顿饭的餐厅给选了。

他们总共有 $n$ 个备选餐厅，要从其中选出 $m$ 个不同的作为以后 $m$ 顿的吃饭地点。第 $i$ 个餐厅的预计开销是 $c_i$。

每顿饭，他们的饭钱是这样支付的：

如果这顿饭不超过 $k$ 元，那么小聪直接全部支付。 否则，小聪支付 $k$ 元，小潘支付剩下的 $c_i - k$。 我们用 $C$ 表示小聪总共支付的饭钱，用 $P$ 表示小潘总共支付的饭钱。

小聪想要最小化 $C - P$ 的值，即他付的钱与小潘付的钱的差值。

但是小潘还没想决定好他们要吃几顿饭，以及小聪的支付上限 $k$ 应该是多少。

小聪决定先考虑好 $q$ 种给定可能性下的最优解。

输入格式

第一行两个整数 $n$ 和 $q$，表示可选餐厅数目以及小聪需要计算的 $q$ 种情况。

接下来 $n$ 个整数 $c_1, c_2, \dots, c_n$ 表示每个餐厅的预计开销。

接下来 $q$ 行，每行两个整数 $k_i$ 和 $m_i$，表示一种需要计算的情况对应的 $k$ 和 $m$。

输出格式

$q$ 行，每行一个整数表示该情况 $C-P$ 的最小值。

样例输入1

5 2
1 9 22 10 19
18 4
5 2

样例输出1

34
-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

数据范围

对于 $40\%$ 的数据，有 $1 \leq n, q \leq 10^3, c_i, k_i \leq 10 ^ 6$。

对于另外 $30\%$ 的数据，有 $k_1 = \dots k_q$。

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