

AirportTime Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2916 Accepted Submission(s): 937 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^{9} ¡Ü x_{i}, y_{i} ¡Ü 10^{9}), 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
Source  
