넉넉한 시럽 (스몰)

무한 팬케이크 하우스 주방에 팬케이크 $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 N \le 10$
• $1 \le K \le N$
• $1 \le R_i \le 10^6$
• $1 \le H_i \le 10^6$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고 1부터 시작한다. $y$는 드러난 표면적의 최댓값을 $\pi$로 나눈 값이다.

드러난 표면적은 언제나 $\pi$의 정수배이므로 $y$는 정수이다. 소수점이나 지수 표기 없이 정수 그대로 출력한다. 단위는 제곱밀리미터이다.

첫 번째 예제에서는 팬케이크를 한 장만 쌓는다. 첫 번째 팬케이크만 쓰면 드러난 면적이 $\pi R_0^2 + 2 \pi R_0 H_0 = 14000\pi$ mm²이고, 두 번째 팬케이크만 쓰면 $44000\pi$ mm²이다. 두 번째가 더 넓으므로 답은 $44000$이다.

두 번째 예제에서는 같은 팬케이크 두 장을 모두 쓴다. 첫 번째 팬케이크는 윗면과 옆면을 합쳐 $14000\pi$ mm²를 내놓고, 두 번째 팬케이크는 가려지지 않은 윗면과 옆면을 합쳐 $34000\pi$ mm²를 내놓는다. 합이 $48000\pi$ mm²이므로 답은 $48000$이다.

세 번째 예제에서는 팬케이크가 모두 반지름 100, 높이 10이다. 두 장을 쌓으면 반지름 100, 높이 20인 원기둥 하나와 같아지고, 드러난 면적은 $14000\pi$ mm²이다.

네 번째 예제에서는 반지름이 8인 팬케이크와 9인 팬케이크를 고르는 것이 최적이다.