Problem Description

The country of jiuye composed by N cites. Each city can be viewed as a point in a two- dimensional plane with integer coordinates (x,y). The distance between city i and city j is defined by d_ij = |x_i - x_j| + |y_i - y_j|. jiuye want to setup airport in K cities among N cities. So he need your help to choose these K cities, to minimize the maximum distance to the nearest airport of each city. That is , if we define d_i(1 ≤ i ≤ N ) as the distance from city i to the nearest city with airport. Your aim is to minimize the value max{d_i|1 ≤ i ≤ N }. You just output the minimum.

 

Input

The first line of the input is T (1 ≤ T ≤ 100), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,K (1 ≤ N ≤ 60,1 ≤ K ≤ N ),as mentioned above.

The next N lines, each lines contains two integer x_i and y_i (-10⁹ ≤ x_i, y_i ≤ 10⁹), denote the coordinates of city i.

 

Output

For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then a single integer means the minimum.

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

#define mem(x,y) memset(x,y,sizeof(x))

const int MAXN=1e5+10;

int a[65][65];

int cmp(int a,int b){

	return a>b;

}

struct Node{

	int x,y;

};

Node dt[65];

int getl(Node a,Node b){

	return abs(a.x-b.x)+abs(a.y-b.y);

}

int main(){

	int T,N,K,kase=0;

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&N,&K);

		for(int i=0;i<N;i++){

			scanf("%d%d",&dt[i].x,&dt[i].y);

		}

		for(int i=0;i<N;i++)for(int j=0;j<N;j++){

			a[i][j]=getl(dt[i],dt[j]);

		}

		for(int i=0;i<N;i++)sort(a[i],a[i]+N,cmp);

	/*	for(int i=0;i<N;i++){

			for(int j=0;j<N;j++)printf("%d ",a[i][j]);

			puts("");

		}*/

		int mx=0x3f3f3f3f;

		for(int i=0;i<N;i++)mx=min(mx,a[i][K-1]);

		printf("Case #%d: %d\n",++kase,mx);

	}

	return 0;

}