시럽 듬뿍 (라지)

무한 팬케이크 하우스의 주방에 팬케이크 $K$장을 쌓은 더미를 달라는 주문이 들어왔다. 주방에 남은 팬케이크는 $N$장이고 $N \ge K$이다. 팬케이크는 모두 원기둥 모양이며 반지름과 높이는 서로 다를 수 있다.

부주방장인 당신은 팬케이크 $N$장 중 $K$장을 고르고 나머지는 버린 다음, 고른 $K$장을 접시 위에 이렇게 쌓는다. 먼저 고른 팬케이크 중 반지름이 가장 큰 것을 원형 면이 접시에 닿도록 놓는다. 반지름이 가장 큰 팬케이크가 여러 장이면 그중 아무거나 놓아도 된다. 그다음 남은 팬케이크 중 반지름이 가장 큰 것을 그 위에 올리고, 같은 방식으로 $K$장을 모두 쌓는다. 원형 면의 중심은 모두 접시에 수직인 한 직선 위에 놓인다. 아래 그림이 그 예다.

손님들이 팬케이크만큼 좋아하는 것이 하나 있다. 바로 시럽이다. 겉으로 드러난 팬케이크 표면이 넓을수록 시럽을 부을 자리가 많아지므로, 드러난 표면적의 합을 최대로 만드는 편이 좋다. 다른 팬케이크에도 닿지 않고 접시에도 닿지 않은 부분을 드러난 표면으로 센다.

팬케이크 $K$장을 가장 좋게 골랐을 때 드러난 표면적의 합이 얼마인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $K$가 주어진다. $N$은 주방에 있는 팬케이크의 수이고 $K$는 손님이 주문한 더미의 크기다. 이어지는 $N$개의 줄에는 각각 정수 $R_i$와 $H_i$가 주어지며, $i$번째 팬케이크의 반지름과 높이를 밀리미터 단위로 나타낸다.

제한

• $1 \le T \le 100$
• $1 \le K \le N \le 1000$
• $1 \le R_i \le 10^6$
• $1 \le H_i \le 10^6$

드러난 표면적의 최댓값은 항상 $\pi$의 정수배가 된다. 각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 표면적의 최댓값을 $y\pi$ 제곱밀리미터로 적었을 때의 정수 $y$다. 면적을 소수로 적지 말고 정수 $y$를 출력한다.

첫 번째 테스트 케이스에서 더미는 팬케이크 한 장으로만 이루어진다. 첫 번째 팬케이크만 놓으면 드러난 넓이가 $\pi R_0^2 + 2 \pi R_0 H_0 = 14000\pi$ mm$^2$이고, 두 번째 팬케이크만 놓으면 $44000\pi$ mm$^2$다. 두 번째 팬케이크가 더 낫고 답은 44000이다.

두 번째 테스트 케이스에서는 첫 번째 케이스와 같은 팬케이크 두 장을 모두 쓴다. 첫 번째 팬케이크는 윗면 전체와 옆면을 드러내 $14000\pi$ mm$^2$를 차지한다. 두 번째 팬케이크는 윗면 중 가려지지 않은 부분과 옆면을 드러내 $34000\pi$ mm$^2$를 차지한다. 합치면 $48000\pi$ mm$^2$이므로 답은 48000이다.

세 번째 테스트 케이스에서는 팬케이크가 모두 반지름 100, 높이 10이다. 이 중 두 장을 쌓으면 반지름 100, 높이 20인 원기둥 한 개와 같아지고 드러난 표면적은 $14000\pi$ mm$^2$이므로 답은 14000이다.

네 번째 테스트 케이스에서는 반지름이 8과 9인 팬케이크를 쌓는 것이 가장 좋다. 넓이는 $199\pi$ mm$^2$이고 답은 199다.