자유를 향해 빙글빙글

"나는 우리가 뒤로가 아니라 앞으로 나아가야 한다고 말한다; 앞으로가 아니라 위로; 그리고 언제나 자유를 향해 twirling, twirling, twirling 해야 한다!" — 전 U.S 대통령 후보 Kodos.

행성 Rigel VII 출신으로는 미국 최초의 대통령 후보가 남긴 이 감명 깊은 말을 들은 후, 당신 역시 자유를 향해 빙글빙글 돌고(회전하고) 싶다고 결심했다. 이 문제에서는 "freedom"을 시작 위치에서 가능한 한 멀리 떨어지는 것으로 생각할 수 있다.

은하는 이차원 평면이다. 우주선은 원점, 즉 위치 (0, 0)에서 출발한다. 은하에는 N개의 별이 있다. 매분 별 하나를 선택하고 그 별을 중심으로 우주선을 시계 방향으로 90도 회전시킬 수 있다. 현재 위치에 그대로 머무르는 것을 선택할 수도 있다.

M분 후 원점에서 얼마나 멀리 이동할 수 있는가?

이 그림은 예제 케이스 1에서 가능한 한 경로의 처음 3번 회전을 보여 준다. 이 경로가 반드시 어떤 최적해의 일부인 것은 아니라는 점에 유의하라.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100; -1000 ≤ $X_{i}$ ≤ 1000; -1000 ≤ $Y_{i}$ ≤ 1000. 서로 같은 위치에 있는 두 별은 없다. 원점에 별이 있을 수도 있다.

테스트 세트 1 (Visible Verdict)

시간 제한: 30초. 1 ≤ N ≤ 10. 1 ≤ M ≤ 10.

테스트 세트 2 (Hidden Verdict)

시간 제한: 60초. 1 ≤ N ≤ 5000. 1 ≤ M ≤ $10^{8}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 정수 N과 M을 담은 두 줄로 시작한다. 다음 N개의 줄에는 각각 별의 위치를 나타내는 두 정수 $X_{i}$와 $Y_{i}$가 주어진다.

각 테스트 케이스마다 "Case #x: D"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며(1부터 시작한다), D는 원점에서 최적의 최종 위치까지의 거리이다. 절대 오차 또는 상대 오차가 10^{-6} 이하인 답은 정답으로 인정된다.