Use Minimum Tokens

Each request a b selects one warehouse, whose capacity must be at least a, while the total capacity of all other warehouses must be at least b; spending 1 token increases the capacity of any warehouse by 1. Spare capacity in the selected warehouse cannot be used toward the backup. Each request is independent and is computed again from the original capacities; return the minimum number of tokens.

输入格式

The first line contains n q, the second line contains n warehouse capacities, followed by q lines of a b. The complete original bounds are 2≤n≤100000, 1≤q≤100000, capacities and a in 1..10^9, and b in 1..10^15.

输出格式

Output the minimum number of tokens for each request, one per line in request order, for q lines in total.

样例 1

输入：

4 1
2 4 1 3
5 7

输出：

2

样例 2

输入：

4 3
5 1 1 4
5 7
4 10
7 9

输出：

1
3
5

样例 3

输入：

3 1
1 10 20
1 30

输出：

0

样例说明

The three public inputs have outputs 2; 1, 3, 5; and 0. The source's first example output was still TO-DO; this site independently filled it in as 2 from the per-warehouse costs.