// John Boswell
// 7/18/2012
// Solution to BHCSI Contest Question: Help

import java.util.*;
import java.io.*;
public class help {
	int N;
	int M;
	int[] time;
	int[] value;
	int[][] memo;

	//Run the dp (the state is which question we are on and how much time is left).
	int dp(int n, int m) {

		//If there is no time left, we can't get any more value.
		if (m==0)
			return 0;

		//If we have made our decision about every question, there is no more value to get.
		if (n==N)
			return 0;

		//Check the memo to see if we already know the answer to this state.
		if (memo[n][m] >= 0)
			return memo[n][m];

		//Try not answering this question.
		int answer = dp(n+1,m);

		//If it is possible to answer this question, try it.
		if (m>=time[n])
			answer = Math.max(answer,dp(n+1,m-time[n])+value[n]);

		//Save the answer and return it.
		return memo[n][m] = answer;
	}

	help(Scanner in) {
		int T = in.nextInt();
		for (int t=0; t<T; t++) {

			//Input.
			N = in.nextInt();
			M = in.nextInt();
			time = new int[N];
			value = new int[N];
			for (int i=0; i<N; i++) {
				time[i] = in.nextInt();
				value[i] = in.nextInt();
			}

			//Declare the memo array for the dp, and fill it with an impossible value.
			memo = new int[N][M+1];
			for (int i=0; i<memo.length; i++)
				Arrays.fill(memo[i],-1);

			//Run the dp, starting at question 0 with all the time left.
			int answer = dp(0,M);

			//Output the answer.
			System.out.printf("Day #%d: %d\n",t+1,answer);
		}
	}

	public static void main(String[] args) throws Exception {
		new help(new Scanner(new File("help.in")));
	}
}