#include <bits/stdc++.h>
using namespace std;
int T, N; double P, H[1009], W[1009], dp[109][25252];
long double solve() {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N * 250; j++) dp[i][j] = -1e9;
}
dp[0][0] = 0.0L;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= N * 250; j++) {
if (dp[i][j] <= -1e8) continue;
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
int U = j + min(H[i], W[i]);
dp[i + 1][U] = max(1.0L*dp[i + 1][U], 1.0L*dp[i][j] + sqrtl(H[i] * H[i] + W[i] * W[i]));
}
}
long double sum1 = 0.0L;
for (int i = 0; i < N; i++) { P -= 2.0L*(H[i] + W[i]); sum1 += 2.0L*(H[i] + W[i]); }
P /= 2;
long double ret = 0.0L;
for (int j = 0; j <= N * 250; j++) {
if (dp[N][j] <= -1e8 || 1.0L*j >= P + 1e-7) continue;
ret = max(ret, 1.0L*min(P, dp[N][j]));
}
return ret*2.0L + sum1;
}
int main() {
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N >> P;
for (int j = 0; j < N; j++) cin >> H[j] >> W[j];
printf("Case #%d: %.12Lf\n", i + 1, solve());
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgVCwgTjsgZG91YmxlIFAsIEhbMTAwOV0sIFdbMTAwOV0sIGRwWzEwOV1bMjUyNTJdOwoKbG9uZyBkb3VibGUgc29sdmUoKSB7Cglmb3IgKGludCBpID0gMDsgaSA8PSBOOyBpKyspIHsKCQlmb3IgKGludCBqID0gMDsgaiA8PSBOICogMjUwOyBqKyspIGRwW2ldW2pdID0gLTFlOTsKCX0KCWRwWzBdWzBdID0gMC4wTDsKCWZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPD0gTiAqIDI1MDsgaisrKSB7CgkJCWlmIChkcFtpXVtqXSA8PSAtMWU4KSBjb250aW51ZTsKCgkJCWRwW2kgKyAxXVtqXSA9IG1heChkcFtpICsgMV1bal0sIGRwW2ldW2pdKTsKCQkJaW50IFUgPSBqICsgbWluKEhbaV0sIFdbaV0pOwoJCQlkcFtpICsgMV1bVV0gPSBtYXgoMS4wTCpkcFtpICsgMV1bVV0sIDEuMEwqZHBbaV1bal0gKyBzcXJ0bChIW2ldICogSFtpXSArIFdbaV0gKiBXW2ldKSk7CgkJfQoJfQoJbG9uZyBkb3VibGUgc3VtMSA9IDAuMEw7Cglmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgeyBQIC09IDIuMEwqKEhbaV0gKyBXW2ldKTsgc3VtMSArPSAyLjBMKihIW2ldICsgV1tpXSk7IH0KCVAgLz0gMjsKCWxvbmcgZG91YmxlIHJldCA9IDAuMEw7Cglmb3IgKGludCBqID0gMDsgaiA8PSBOICogMjUwOyBqKyspIHsKCQlpZiAoZHBbTl1bal0gPD0gLTFlOCB8fCAxLjBMKmogPj0gUCArIDFlLTcpIGNvbnRpbnVlOwoJCXJldCA9IG1heChyZXQsIDEuMEwqbWluKFAsIGRwW05dW2pdKSk7Cgl9CglyZXR1cm4gcmV0KjIuMEwgKyBzdW0xOwp9CgppbnQgbWFpbigpIHsKCWNpbiA+PiBUOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBUOyBpKyspIHsKCQljaW4gPj4gTiA+PiBQOwoJCWZvciAoaW50IGogPSAwOyBqIDwgTjsgaisrKSBjaW4gPj4gSFtqXSA+PiBXW2pdOwoKCQlwcmludGYoIkNhc2UgIyVkOiAlLjEyTGZcbiIsIGkgKyAxLCBzb2x2ZSgpKTsKCX0KCXJldHVybiAwOwp9