AGGRCOW - Aggressive cows

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1 ... xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

t – the number of test cases, then t test cases follows.
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

For each test case output one integer: the largest minimum distance.

Example

Input:

1
5 3
1
2
8
4
9

Output:

3

Output details:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8,
resulting in a minimum distance of 3.


Added by:Roman Sol
Date:2005-02-16
Time limit:2s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:USACO February 2005 Gold Division

hide comments
2016-03-26 19:53:55
must try...... loved this question
2016-03-05 12:36:27
gud one!!!
2016-02-08 16:58:24 ankur jaiswal
yes giriprasad kemburu he can put; infact its one of the solutions
2016-02-03 16:00:32 ankurverma1994
Weak Test Cases
1
2 2
5 10
Answer should be 5 but 4 is also accepted. I think for C=2 there is no test case present in test file
2016-01-25 19:10:39
Excellent Problem,looks hard but it is easy just read the topcoder binary search tutorial and solve this one
2016-01-25 11:23:11
It's definitely not as easy as it seems to be.Try to relate it with the example given in Topcoder binary search tutorial.Try the following testcases for confirmation.
input:
6
10 3
1 2 9 8 4 4 8 9 2 1
5 3
1 2 8 4 9
20 3
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
3 3
0 1000000000 500000000
20 4
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
20 5
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
output:
3
3
9
500000000
6
4
2016-01-24 13:37:51
Really nice one and awesome tutorial on Topcoder
2016-01-21 06:42:05 Devashish Mathur
Great Question..
2016-01-17 10:03:18
F*** -_- [2WA]- forgot to loop for test cases.
Awesome concept - made me understand the actual use of binary search - Simple Implementation
Must read - Topcoder Tutorial.
2015-12-23 19:49:23 Junaid
I would say this is the best problem I have done on SPOJ till now..I took a whole day just to solve this one....but finally AC in one go...my 44th..:P...All THANKS to topcoder.....:)...highly recommended problem..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.