가장자리가 바삭한 쿠키

제빵사 마이야르 씨가 쿠키 반죽을 밀어 펴서 잘라 $N$개의 쿠키를 만들었다. 모든 쿠키는 직사각형이다. 막 오븐에 넣으려다가, 바삭하게 캐러멜화된 쿠키 가장자리가 특히 맛있다는 사실을 떠올렸다. 구체적으로, 그는 모든 쿠키의 둘레 합이 $P$ mm(밀리미터)에 최대한 가깝되 $P$를 넘지 않을 때 가장 만족스러울 것이라고 생각한다. (가장자리가 너무 많으면 탈 수도 있다!)

각 쿠키마다 그대로 둘지, 직선으로 한 번 잘라 넓이가 같은 두 조각으로 나눌지 정할 수 있다. (이 절단선은 반드시 쿠키의 중심을 지난다.) 이렇게 만든 두 쿠키는 다시 자를 수 없다.

마이야르 씨가 최적으로 결정한다면, $P$를 넘지 않으면서 $P$에 가장 가깝게 만들 수 있는 값은 얼마인가?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 쿠키의 개수 $N$과 목표 둘레 합 $P$(mm)가 정수로 주어진다. 이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 $i$번째 쿠키의 너비 $W_i$와 높이 $H_i$(둘 다 mm 단위)가 정수로 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 절단을 마친 뒤 모든 쿠키의 둘레 합 중 $P$를 넘지 않는 최댓값(mm)이다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

$1 \le T \le 100$.

$1 \le N \le 100$.

모든 $i$에 대해 $1 \le W_i \le 250$.

모든 $i$에 대해 $1 \le H_i \le 250$.

$P \ge 2 \times \sum_i (W_i + H_i)$. ($P$는 어떤 쿠키도 자르기 전의 모든 쿠키 둘레 합 이상이다.)

$P \le 10^8$.

테스트 셋 1에서는 마지막 예제 케이스가 나오지 않는다는 점에 유의하라.

예제 케이스 #1에는 한 변의 길이가 1인 정사각형 쿠키 하나만 있다. 한쪽 모서리에서 대각선 반대편 모서리까지 자르면, 변의 길이가 1, 1, $\sqrt{2}$인 직각삼각형 두 개가 생긴다. 이때 둘레 합은 $4 + 2\sqrt{2}$이고, 이는 $P = 7$보다 작지만 더 가깝게 만들 수는 없다.

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

예제 케이스 #3에서는 쿠키를 잘라 변의 길이가 2, 4, 5, 5인 사다리꼴 두 개를 만든다. 그러면 새 둘레 합은 32가 되어 정확히 $P$와 같다.

예제 케이스 #4에서는 처음 둘레 합이 이미 정확히 $P$이므로, 마이야르 씨는 자르지 않아야 한다.