// Arup Guha
// 7/24/2013
// Solution to 2013 SI@UCF Contest Problem: Monkey Madness

import java.util.*;
import java.io.*;

public class monkeys {
	
	public static void main(String[] args) throws Exception {
		
		Scanner stdin = new Scanner(new File("monkeys.in"));
		int numCases = stdin.nextInt();
		
		// Go through each case.
		for (int loop=0; loop<numCases; loop++) {
			
			// Get input and set up DP.
			int n = stdin.nextInt();
			int W = stdin.nextInt();
			int[] dp = new int[W+1];
			
			// Run knapsack.
			for (int i=0; i<n; i++) {
				int monkeys = stdin.nextInt() + 1;
				int bananas = stdin.nextInt();
				
				for (int j=W; j>=monkeys; j--)
					if (dp[j-monkeys] + bananas > dp[j])
						dp[j] = dp[j-monkeys] + bananas;
			}
			
			// Find the best, since the real answer might not take W monkeys...
			int ans = 0;
			for (int i=0; i<=W; i++)
				if (dp[i] > ans)
					ans = dp[i];
				
			// Print out...
			System.out.println(ans);
		}
		
	}
}