Metal

A very rare and expensive metal has been found underground. The deposits are spread out through the rock, so the mining plan needs care. The plan is a set of horizontal tunnels joined by vertical elevators. Every elevator connects the right end of one tunnel to the left end of another, and the structure of tunnels and elevators has to be monotone with respect to the ground. That is, starting at the end of the leftmost tunnel and travelling to the end of the rightmost one, you can pass through every tunnel without ever moving left again.

The budget allows only $k$ horizontal tunnels, where $k$ is a positive integer, so at most $k-1$ vertical elevators can join them. Each deposit then gets its own vertical shaft dropped from a horizontal tunnel. The cost of mining one deposit is the vertical distance between it and the tunnel that serves it. The cost of mining all $n$ deposits is the largest of the individual costs.

The deposits are points $P = \{p_1, p_2, \dots, p_n\}$ in the plane, a horizontal tunnel is a horizontal line, and vertical shafts and elevators are vertical lines. The cost of deposit $p_i$ is $\mathrm{cost}(p_i)$, the vertical distance to the tunnel that serves it, and the total is $\mathrm{cost}(P) = \max_{1 \le i \le n} \mathrm{cost}(p_i)$. Because of the monotone condition, the deposits served by one horizontal tunnel form a contiguous run once the points are ordered by $x$ coordinate.

Given the set $P$ of $n$ points and a positive integer $k$, write a program that finds the smallest $\mathrm{cost}(P)$ obtainable with at most $k$ horizontal tunnels.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains the number of deposits $n$ and the largest number of horizontal tunnels $k$. ($2 \le n \le 10\,000$, $k \ge 1$) The second line contains $2n$ integers $x_1$, $y_1$, $x_2$, $y_2$, $\dots$, $x_n$, $y_n$, the coordinates of $p_1, p_2, \dots, p_n$, separated by spaces. ($-100\,000\,000 \le x_i, y_i \le 100\,000\,000$) No two points share an $x$ coordinate.

For each test case, print the minimum value of $\mathrm{cost}(P)$ on its own line. That minimum is always a multiple of $0.5$, so print it with exactly one digit after the decimal point. A minimum of $2$ prints as 2.0 and a minimum of $2.5$ prints as 2.5.