// Arup Guha
// 5/8/2022
// Solution to 2019 UCF HS Online D2 Contest Problem: Election Fraud

import java.util.*;

public class election {

	final public static int NOWIN = -100000;
	
	public static int n;
	public static vote[] list;
	public static int budget;
	
	public static int[][][] memo;
	public static int[][] precomp;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=1; loop<=nC; loop++) {
		
			n = stdin.nextInt();
			budget = stdin.nextInt();
			list = new vote[n];
		
			// Sort the list to see most votes I could buy.
			for (int i=0; i<n; i++) {
				int me = stdin.nextInt();
				int you = stdin.nextInt();
				list[i] = new vote(me, you);
			}
			Arrays.sort(list);
			
			// Count how much for me to win it.
			int sum = 0;
			for (int i=0; i<(n+2)/2; i++)
				sum += list[i].me;
			
			// Easy case.
			if (sum <= budget)
				System.out.println("Election #"+loop+": -1");
			
			// Run DP here.
			else {
				
				// Now sort by you.
				Arrays.sort(list, new Comparator<vote>() {
					public int compare(vote a, vote b) {
						if (a.you != b.you)
							return a.you - b.you;
						return a.me - b.me;
					}
				});
				
				// precomp[k][z] = sum of minimum z+1 elements in list[k..n-1] of me.
				precomp = new int[n][n];
				for (int i=0; i<n; i++) {
					ArrayList<Integer> tmp = new ArrayList<Integer>();
					for (int j=i; j<n; j++) tmp.add(list[j].me);
					Collections.sort(tmp);
					precomp[i][0] = tmp.get(0);
					for (int j=1; j<tmp.size(); j++) 
						precomp[i][j] = precomp[i][j-1] +tmp.get(j);
				}
				
				// Set up memo table.
				memo = new int[n+1][2*n+2][budget+2];
				for (int i=0; i<n; i++)
					for (int j=0; j<=2*n; j++)
						Arrays.fill(memo[i][j], -1);
					
				// Do it!
				System.out.println("Election #"+loop+": "+go(0, n, budget));
			}
		}
	}
	
	// Returns the best result starting at index k, such that I have diff-n more votes than you, and have cash money left.
	public static int go(int k, int diff, int cash) {
		
		// We're finished.
		if (k == n) {
			if (diff < n) return NOWIN;
			if (diff >= n) return 0;
		}
		
		int res = NOWIN;
		
		// This means I am equal or ahead, so we can do better than NOWIN.
		if (diff >= n) {
		
			// What you need to spend to catch up. Represents me stopping.
			res = 0;
			for (int i=n,j=k; i<diff; i++,j++)
				res += list[j].you;
		}
		
		// See if they stop buying if I can equal them.
		else {
			
			// This is what I need to catch up
			int need = precomp[k][n-diff-1];
		
			// I can't catch up.
			if (need > cash || need == 0) return NOWIN;
			
			// This indicates that we have a valid result on this path.
			else res = 0;
		}
		
		// I try to buy.
		if (list[k].me <= cash) {
			int tmp = go(k+1, diff+1, cash-list[k].me);
			if (tmp != NOWIN) res = Math.max(res, tmp);
		}
		
		// You buy.
		int other = go(k+1, diff-1, cash);
		if (other != NOWIN) {
			res = Math.max(res, other+list[k].you);
		}
		
		// Store and return.
		return memo[k][diff][cash] = res;
	}
}

class vote implements Comparable<vote> {

	public int me;
	public int you;
	
	public vote(int a, int b) {
		me = a;
		you = b;
	}
	
	public int compareTo(vote other) {
		if (this.me != other.me)
			return this.me - other.me;
		return this.you - other.you;
	}
}