1184 - SCU-D

Time Limit: 2s Memory Limit: 128MB

Submissions: 349 Solved: 71
Description
You will be given N integers v0,v1,v2...vN-1 and an integer M. Can you tell me the number of distinct integer values of x such that: |v0 - x| + |v1 - x| + ... + |vN-1 - x| ≤ M.
Input
The first line of the input will be a integer to represent the number of test cases. For each case there is two lines. The first line contains two integers N and M. The second line contains N integers v0,v1,v2...vN-1. ( 1 <= N <= 50000 , 0 <= M <= 10^9 , -10^9 <= vi <= 10^9 ) There is a blank line before each test case.
Output
For each test case output the answer on a line: The number of distinct integer values of x.
Sample Input
3

3 100
1 10 50

3 10
1 10 50

5 12345
123 456 7890 -555 -321
Sample Output
67
0
2337
Hint
Source
SCUPC