2016 Al-Baath University Training Camp Contest-1 I

Description

It is raining again! Youssef really forgot that there is a chance of rain in March, so he didn't fix the roof of his house. Youssef's roof is 1-D, and it contains n holes that make the water flow into the house, the position of hole i is denoted as xi where (0 ≤ i < n). Youssef has to put strips at the bottoms of those holes in order to prevent the water from flowing. Let's say there is a hole in position 4 and another hole in position 6, and Youssef decided to use a strip of length 3 to cover those two holes, then he places the strip from position 4 to 6 (it covers positions 4,5,6) and it covers the two holes. He can buy exactly k strips, and he must pay a price equal to the longest strip he buys. What is the minimum length l he can choose as the longest strip in order to keep his house safe?

Input

The input consists of several test cases. The first line of the input contains a single integer T, the number of the test cases. Each test case consists of two lines: the first line contains two space-separated integers, n and k (1 ≤ k < n ≤ 100000), denoting the number of the holes in the roof, and the number of the strips he can buy respectively. The second line of the test case contains n integers (x0, x1, ..., xn - 1): (0 ≤ xi ≤ 109), denoting the positions of holes (these numbers are given in an increasing order).

Output

For each test case print a single line containing a single integer denoting the minimum length l he can choose in order to buy k strips (the longest of them is of length l) and cover all the holes in his house using them.

Example

input

3
5 2
1 2 3 4 5
7 3
1 3 8 9 10 14 17
5 3
1 2 3 4 20

output

3
4
2

Note

                                 

In the second test case the roof looks like this before and after putting the strips.

 题意：屋顶漏水，现在知道xi处是漏的，可以使用k块布盖住，问最短布的长度为多少

解法：二分，首先当然是最大的数字/k，得到最长的长度，然后二分判断

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[100005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		int l=0,r=a[n-1]/m+1;
		while(l<=r){
			int mid=(l+r)/2;
			int x=a[0]+mid-1,cnt=1;
			for(int i=0;i<n;i++){
				if(a[i]>x){
					cnt++;
					x=a[i]+mid-1;
				}
			}
			if(cnt<=m){
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		printf("%d
",r+1);
	}
}