메탈

지하에서 아주 드물고 값비싼 금속을 찾아냈다. 금속이 땅속에 넓게 흩어져 있어서 채굴 계획을 신중하게 세워야 한다. 계획은 수직 엘리베이터로 이어진 수평 터널 여러 개로 이루어진다. 엘리베이터는 한 터널의 오른쪽 끝과 다른 터널의 왼쪽 끝을 잇는다. 터널과 엘리베이터의 연결 구조는 땅에 대해 단조로워야 한다. 즉 가장 왼쪽 터널의 끝에서 출발해 가장 오른쪽 터널의 끝까지 가는 동안, 다시 왼쪽으로 되돌아가는 일 없이 모든 터널을 지날 수 있어야 한다.

예산이 한정되어 있어 수평 터널은 $k$개만 만들기로 했다. $k$는 양의 정수이고, 수평 터널을 잇는 수직 엘리베이터는 최대 $k-1$개 만들 수 있다. 금속마다 수평 터널에서 내려가는 수직 터널을 하나씩 뚫는다. 금속 하나를 채굴하는 비용은 그 금속과 담당 수평 터널 사이의 수직 거리다. 금속 $n$개를 채굴하는 비용은 각 금속의 채굴 비용 중 최댓값이다.

금속은 2차원 평면 위의 점 $P = \{p_1, p_2, \dots, p_n\}$으로, 수평 터널은 수평선으로, 수직 터널과 엘리베이터는 수직선으로 나타낸다. 금속 $p_i$의 채굴 비용 $\mathrm{cost}(p_i)$는 $p_i$를 담당하는 수평 터널까지의 수직 거리이고, 전체 채굴 비용은 $\mathrm{cost}(P) = \max_{1 \le i \le n} \mathrm{cost}(p_i)$다. 단조 조건 때문에 한 수평 터널이 담당하는 금속은 $x$좌표 순으로 늘어놓았을 때 연속한 구간을 이룬다.

점 $n$개의 집합 $P$와 양의 정수 $k$가 주어졌을 때, 수평 터널을 최대 $k$개 놓아 $\mathrm{cost}(P)$를 가장 작게 만드는 값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 금속의 개수 $n$과 만들 수 있는 수평 터널의 최대 개수 $k$가 주어진다. ($2 \le n \le 10\,000$, $k \ge 1$) 둘째 줄에 점 $p_1, p_2, \dots, p_n$의 좌표를 나타내는 정수 $2n$개 $x_1$, $y_1$, $x_2$, $y_2$, $\dots$, $x_n$, $y_n$이 공백으로 구분되어 주어진다. ($-100\,000\,000 \le x_i, y_i \le 100\,000\,000$) $x$좌표가 같은 두 점은 없다.

각 테스트 케이스마다 $\mathrm{cost}(P)$의 최솟값을 한 줄에 출력한다. 이 최솟값은 항상 $0.5$의 배수이므로 소수점 첫째 자리까지 정확하게 출력한다. 최솟값이 $2$면 2.0을, $2.5$면 2.5를 출력한다.