풍부한 시럽

Infinite House of Pancakes의 주방에 방금 K개의 팬케이크로 이루어진 더미 주문이 들어왔다! 현재 요리사는 N개의 팬케이크를 가지고 있으며, N ≥ K. 각 팬케이크는 원기둥이고, 서로 다른 팬케이크는 반지름과 높이가 다를 수 있다.

부주방장인 당신은 준비된 N개의 팬케이크 중 K개를 선택하고 나머지는 버린 뒤, 선택한 K개의 팬케이크를 다음과 같이 접시 위에 쌓아야 한다. 먼저 반지름이 가장 큰 팬케이크를 골라 원형 면 중 하나가 접시에 닿도록 놓는다. (여러 팬케이크의 반지름이 같다면 그중 아무것이나 사용할 수 있다.) 그런 다음 남은 팬케이크 중 그다음으로 반지름이 큰 팬케이크를 가져와 그 팬케이크 위에 놓는 과정을 반복한다. 모든 K개의 팬케이크가 더미에 놓이고 원형 면의 중심들이 접시에 수직인 한 직선 위에 정렬될 때까지 계속한다. 다음 예시에 이 모습이 나와 있다.

손님들이 팬케이크만큼이나 좋아하는 것은 딱 하나 더 있는데, 바로 시럽이다! 노출된 팬케이크 표면적이 클수록 맛있는 시럽을 부을 곳도 많아지므로, 더미에서 노출된 팬케이크 표면적의 합을 최대화하는 것이 가장 좋다. 다른 팬케이크의 일부나 접시에 닿지 않는 팬케이크의 모든 부분은 노출된 것으로 간주한다.

K개의 팬케이크를 최적으로 선택할 때, 달성할 수 있는 노출된 팬케이크 표면적의 최대 합은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ K ≤ N. 모든 i에 대해, 1 ≤ $R_{i}$ ≤ $10^{6}$. 모든 i에 대해, 1 ≤ $H_{i}$ ≤ $10^{6}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 K가 주어지는 한 줄로 시작한다. 이들은 각각 준비된 팬케이크의 총개수와 손님이 주문한 더미의 크기이다. 이어서 N개의 줄이 더 주어진다. 각 줄에는 두 정수 $R_{i}$와 $H_{i}$가 주어지며, 각각 i번째 팬케이크의 반지름과 높이를 밀리미터 단위로 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 가능한 노출된 팬케이크 표면적의 최댓값을 제곱밀리미터 단위로 나타낸 것이다. y의 절대 오차 또는 상대 오차가 정답의 10^{-6} 이내이면 정답으로 간주한다. 이것이 의미하는 바와 허용되는 실수 형식에 관한 설명은 FAQ를 참고한다.

예제 케이스 #1에서 "stack"는 팬케이크 하나로만 이루어진다. 첫 번째 팬케이크만 쌓으면 노출 면적은 π × $R_{0}^{2}$ + 2 × π * $R_{0}$ × $H_{0}$ = 14000π $mm^{2}$이다. 두 번째 팬케이크만 쌓으면 노출 면적은 44000π $mm^{2}$이다. 따라서 두 번째 팬케이크를 사용하는 것이 더 좋다.

예제 케이스 #2에서는 케이스 #1의 동일한 팬케이크 두 개를 모두 사용할 수 있다. 첫 번째 팬케이크는 윗면과 옆면이 포함되어 총 14000π $mm^{2}$만큼 기여한다. 두 번째 팬케이크는 윗면의 일부(첫 번째 팬케이크에 덮이지 않은 부분)와 옆면이 포함되어 총 34000π $mm^{2}$만큼 기여한다. 노출된 표면적의 합은 48000π $mm^{2}$이다.

예제 케이스 #3에서는 모든 팬케이크의 반지름이 100이고 높이가 10이다. 이 중 두 개를 함께 쌓으면 사실상 반지름이 100이고 높이가 20인 새로운 원기둥 하나가 된다. 노출된 표면적은 14000π $mm^{2}$이다.

예제 케이스 #4에서 최적의 더미는 반지름이 8와 9인 팬케이크를 사용한다.