Sleepy Jimma

All submissions for this problem are available.
Jimma had not been able to sleep for the last few days because Chingam kept waking her up to play with him. To keep him busy for a few hours Jimma gave Chingam an array A of N distinct integers and told him to play with it.
After observing the array for a while Chingam noticed that there are too many different elements and too much chaos. So he decided to fix the array and make each of the elements equal to either H or L.
To do this, in one second, Chingam can choose any element of the array A and either increment it or decrement it. Chingam can choose the same element multiple times. He is willing to work for at most K seconds and he wants to choose H and L such that the difference between them is minimized.
Chingam always shares his toys with Jimma, so he has asked Jimma to find the minimum possible difference HL he can achieve.
Jimma's plan to get rid of Chingam has backfired and now Chingam will keep annoying her until she tells him the answer. Jimma is too sleepy to think properly, so she has asked you for help. She will tell you the array A and the value of K, please find the solution for her.
Note:
N will always be even.
It is guaranteed that there will always be at least one pair H,L such that it possible for Chingam to get an array where each elements is equal to either H or L in at most K seconds.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two space separated integers N and K. The next line contains N space separated integers denoting the array A.
Output
 For each test case, output a single line containing the minimum possible value of HL that can be achieved in K seconds.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 10^{5}, N even
 K ≤ 10^{13}
 1 ≤ A[i] ≤ 10^{8}
Example
Input: 1 4 2 2 1 4 5 Output: 2
Explanation
Example case 1.
There is only one test case. There are 5 elements and K = 2.
Chingam can get the array {1,1,5,5} , {1,1,4,4} , {2,2,5,5}, {2,2,4,4} in 2 seconds. You can check that it is not possible to get a valid array in less than 2 seconds. H and L have smallest difference in the last array. So the answer is 42 = 2.
Author:  meteora 
Tags  meteora 
Date Added:  6022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions