모서리 가득한 제빵

제빵사 Mr. Maillard는 쿠키 반죽을 밀어 편 뒤 잘라서 각각 직사각형인 N개의 쿠키를 만들었다. 막 쿠키를 오븐에 넣으려던 참에, 바삭하고 캐러멜화된 쿠키의 가장자리가 특히 맛있다는 사실이 떠올랐다. 구체적으로 그는 모든 쿠키의 둘레의 합이 P밀리미터(mm)를 넘지 않으면서 가능한 한 P에 가까우면 가장 행복할 것이라고 생각한다. (쿠키 묶음에 가장자리가 너무 많으면 타 버릴지도 모른다!)

각 쿠키에 대해 Mr. Maillard는 그대로 둘지, 한 번의 직선 절단으로 넓이가 같은 두 조각(반드시 직사각형일 필요는 없음)으로 나눌지 결정할 수 있다. (이러한 절단은 반드시 쿠키의 중심을 지나야 한다는 점에 유의하라.) 이런 방식으로 새로 만들어진 두 쿠키는 다시 자를 수 없다.

Mr. Maillard가 최적의 결정을 내릴 때, P를 초과하지 않으면서 얼마나 가깝게 만들 수 있는가?

제한

1 ≤ T ≤ 100. 1 ≤ N ≤ 100. 모든 i에 대해, 1 ≤ $W_{i}$ ≤ 250. 모든 i에 대해, 1 ≤ $H_{i}$ ≤ 250. P ≥ 모든 i에 대한 ($W_{i}$ + $H_{i}$)의 합 × 2. (P는 절단하기 전 모든 쿠키의 둘레의 합보다 크거나 같다.) P ≤ $10^{8}$. 시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

모든 i와 j에 대해, $W_{i}$ = $W_{j}$. 모든 i와 j에 대해, $H_{i}$ = $H_{j}$. (주어진 모든 쿠키의 크기는 같다.)

테스트 세트 2 (비공개)

일반 제한 외에 추가 제한은 없다. (특히, 주어진 모든 쿠키의 크기가 반드시 같지는 않다.)

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 쿠키의 수와 원하는 둘레의 합(mm)을 각각 나타내는 두 정수 N과 P가 있는 한 줄로 시작한다. 그다음 N개의 줄이 주어진다. 이 중 i번째 줄에는 두 정수 $W_{i}$와 $H_{i}$가 주어지며, 이는 i번째 쿠키의 너비와 높이(둘 다 mm 단위)를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 실수로, Mr. Maillard가 절단을 마친 뒤 모든 쿠키의 둘레의 합 중 P를 초과하지 않는 가능한 최댓값(mm 단위)이다. y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내라면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참조하라.

마지막 예제 케이스는 테스트 세트 1에 나타나지 않는다는 점에 유의하라.

예제 케이스 #1에는 쿠키가 하나뿐이며, 한 변의 길이가 1인 정사각형이다. Mr. Maillard는 한 모서리에서 대각선 반대편 모서리까지 자를 수 있으며, 그러면 각각의 변의 길이가 1, 1, sqrt(2)인 두 직각삼각형이 만들어진다. 그러면 둘레의 합은 4 + 2 × sqrt(2)이다. 이는 P = 7보다 작지만, 이보다 더 가깝게 만드는 것은 불가능하다.

예제 케이스 #2에서 Mr. Maillard는 첫 번째 쿠키를 긴 축을 따라 잘라 새로운 25 x 120 직사각형 두 개를 만들고, 두 번째 쿠키는 그대로 둘 수 있다. 그러면 전체 둘레는 580 + 340 = 920이며, 이는 정확히 P이다.

예제 케이스 #3에서 Mr. Maillard는 쿠키를 잘라 각각 변의 길이가 2, 4, 5, 5인 두 사다리꼴을 만들 수 있다. 그러면 새로운 둘레의 합은 32이며, 이는 정확히 P이다.

예제 케이스 #4에서는 처음 둘레의 합이 정확히 P이므로, Mr. Maillard는 어떤 절단도 하지 않아야 한다.