Playing Drums

0

0 votes
Problem

Once DJ Boy was travelling from Chandni Chowk to China . In his journey he encountered N cities on his way numbered 0 to N-1 and also played Drums in some of the cities. But since he is crazy he thought of playing drums in such a way that the minimum distance between any two cities in which he played drums should be as large as possible. Also he wished to play drums in atleast M cities(He never plays drums in source and destination city). Given the distance of each of the N cities from the source city( Chandni Chowk ), DJ Boy wants to know the largest of the minimum distance between any two cities in which he played drums.

Input: First line of input contains an interger T denoting number of test cases. First line of each test case contains two space seperated intergers N,M. Second line of each test case contains array A of N intergers denoting distance from source city (A[i] is distance from of ith city from source city). ( 0th city is city just after the source city and (N-1)th city is city just before the destination city)

Output: For each test case,output the maximum value that is required.

Constraints: • 1<= T <= 1000

• 2<= N <= 1000

• 2<= M <= N

• 1<= A[i] <= 10^9

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In second test case, he can play drums in 0th, 2nd and 4th city. The minimum difference will be 10 in this case. In any other case the minimum difference will be less than 10.

Editor Image

?