Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.