자유를 향한 회전 (작은 입력)

"우리는 뒤가 아니라 앞으로 나아가야 하고, 앞이 아니라 위로 올라가야 하며, 언제나 빙글빙글, 빙글빙글, 자유를 향해 돌아야 합니다!"

전 미국 대통령 후보 코도스

코도스는 리겔 7 행성에서 왔다. 이 연설에 감명받은 당신도 자유를 향해 회전하기로 했다. 이 문제에서 자유란 출발점에서 최대한 멀리 떨어지는 것이다.

은하는 2차원 평면이다. 우주선은 원점 $(0, 0)$ 에서 출발하고, 은하에는 별이 $N$ 개 있다. 1분마다 별을 하나 골라 그 별을 중심으로 우주선을 시계 방향으로 90도 회전시킬 수 있다. 그냥 그 자리에 머무를 수도 있다.

$M$ 분이 지난 뒤 원점에서 최대 얼마나 멀어질 수 있는가?

그림은 첫 번째 예제에서 가능한 어떤 경로의 처음 세 번의 회전을 보여 준다. 이 경로가 최적인 것은 아니다.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 $N$ 이 적힌 줄과 $M$ 이 적힌 줄로 시작한다. 이어지는 $N$ 개의 줄에는 별의 위치를 나타내는 두 정수 $X_i$ 와 $Y_i$ 가 주어진다.

각 테스트 케이스마다 Case #x: D 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $D$ 는 원점에서 최적의 최종 위치까지의 거리다. $D$ 는 소수점 아래 여섯째 자리까지 반올림해 출력한다.