// Arup Guha
// 3/21/2021
// Solution to 2021 UCF HS Contest Problem: Knapsack?

import java.util.*;

public class knapsack {

	public static void main(String[] args) {
	
		// Get # of cases.
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
		
			int n = stdin.nextInt();
			int cap = stdin.nextInt();
			
			// values and weights.
			int sumW = 0, sumV = 0;
			int[] v = new int[n];
			int[] w = new int[n];
			for (int i=0; i<n; i++) {
				v[i] = stdin.nextInt();
				w[i] = stdin.nextInt();
				sumW += w[i];
				sumV += v[i];
			}
			
			// Easy case.
			if (sumW <= cap)
				System.out.println(sumV);
		
			// Interesting case.
			else {
			
				// dp[i] will store minimum value to get to this capacity.
				// for the last index it will be that or more.
				int[] dp = new int[sumW-cap+1];
				Arrays.fill(dp, sumV);
				dp[0] = 0;
				
				// Go through items.
				for (int i=0; i<n; i++) {
				
					// j is the weight of what we are filling.
					for (int j=dp.length-1; j>=0; j--) {
						
						// We only need this item.
						if (j < w[i]) 	dp[j] = Math.min(dp[j], v[i]);
						
						// Knapsack modification with minimum...
						else			dp[j] = Math.min(dp[j], dp[j-w[i]] + v[i]);
					}
				}
				
				// We can get everything BUT the min valued knapsack that weights what we can't have.
				System.out.println(sumV-dp[dp.length-1]);
			}
		}
	}
}