Note that this is a harder version of the problem
You are given $n$
points in the plane. You are asked to cover these points with
$k$ squares. The squares
must all be the same size, and their edges must all be parallel
to the coordinate axes. A point is covered by a square if it
lies inside the square, or on an edge of the square. Squares
Find the minimum length for the squares’ edges such that you
can cover the $n$ points
with $k$ squares.
The first line of input gives the number of cases,
$T\leq 10$. $T$ test cases follow. The first line
of each test contains two positive integers $n$ and $k$. Each of the next $n$ lines contains a point as two
integers separated by exactly one space. No point will occur
more than once within a test case.
You may assume that the points’ coordinates are non-negative
integers smaller than 64000 and $1 \leq k < n \leq 15$.
For each test case, you should output one line containing
"Case #$X$: $Y$" (quotes for clarity), where
$X$ is the number of the
test case, starting from 1, and $Y$ is the minimum length for the
squares’ edges for that test case.
|Sample Input 1
||Sample Output 1
Case #1: 2
Case #2: 3