// Arup Guha
// 5/7/2018
// Solution to 2018 Code Jam Round 1A Problem C: Edgy Baking
// (Written after contest...)

import java.util.*;

public class Solution {

	public static int n;
	public static int p;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			int add = 0;
			n = stdin.nextInt();
			p = stdin.nextInt();

			int[] low = new int[n];
			double[] range = new double[n];
			int sum = 0;

			// Read in the rectangles and adjust perimeter by subbing out minimum.
			for (int i=0; i<n; i++) {
				int w = stdin.nextInt();
				int h = stdin.nextInt();
				p -= (2*(w+h));
				add += 2*(w+h);

				// Stores range of how we can adjust the perimeter.
				low[i] = 2*Math.min(w,h);
				sum += low[i];
				range[i] = 2*Math.sqrt(w*w+h*h) - low[i];
			}

			// Set up array for adjusted knapsack. If dp[i] > 0, then we can hit i
			// exactly and all values in the range [i, i+dp[i]].
			double[] dp = new double[sum+1];
			Arrays.fill(dp, -1);
			dp[0] = 0;

			// Usual knapsack structure.
			for (int i=0; i<n; i++)
				for (int j=sum; j>=low[i]; j--)

					// This means there's a valid subset that adds to j-low[i].
					if (dp[j-low[i]] > -1e-9)
						dp[j] = Math.max(dp[j], dp[j-low[i]] + range[i]);

			// Take the largest valid answer without building off of something larger than p.
			double ans = 0;
			for (int i=0; i<=sum && i<=p; i++) {
				if (dp[i] < 0) continue;
				ans = Math.max(ans, i+dp[i]);
			}

			// But we can't exceed p.
			ans = Math.min(ans, p);

			System.out.println("Case #"+loop+": "+(add+ans));
		}
	}
}