// Arup Guha
// 2/18/2016
// Solution to 2016 FHSPS Playoff Problem: What to Teach?

import java.util.*;

public class teach {

	public static void main(String[] args) {

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

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			// Tead in the basic parameters.
			int n = stdin.nextInt();
			int totalMin = stdin.nextInt();

			// Read in information about teach topic.
			int[] times = new int[n];
			int[] pts = new int[n];
			for (int i=0; i<n; i++) {
				times[i] = stdin.nextInt();
				pts[i] = stdin.nextInt();
			}

			// Run 0-1 Knapsack Algorithm.
			int[] dp = new int[totalMin+1];
			for (int i=0; i<n; i++)
				for (int j=totalMin; j>=times[i]; j--)
					dp[j] = Math.max(dp[j], dp[j-times[i]] + pts[i]);

			// Get maximal # of points for using any number of minutes in class.
			int res = 0;
			for (int i=0; i<dp.length; i++)
				res = Math.max(res, dp[i]);

			// Here is the result!
			System.out.println(res);
		}
	}
}