#include <iostream>
#include <cassert>
#include <cstdio>
#include <algorithm>
using namespace std;

#define maxn 10

int tn, n, k, i, j, a[maxn], b[maxn], ret, weight, cost;

int main (int argc, char * const argv[]) {
	scanf("%d", &tn); // reading the number of the test cases
	assert(1 <= tn && tn <= 250); // input validation
	while (tn--) {
		scanf("%d %d", &n, &k); // reading the number of oranges and the amount of money we have
		assert(1 <= n && n <= 10); // input validation
		assert(1 <= k && k <= 100000000); // input validation
		for(i = 0; i < n; i++) {
			scanf("%d %d", &a[i], &b[i]); // reading the information about the i-th orange
			assert(1 <= a[i] && a[i] <= 100000000); // input validation
			assert(1 <= b[i] && b[i] <= 100000000); // input validation
		}
		for(i = 0, ret = 0; i < (1 << n); i++) { // checking all the possible subsets
			weight = 0; cost = 0; 
			for(j = 0; j < n; j++) if (i & (1 << j)) { // find all the oranges that are in the subset
				weight += b[j]; // add the j-th orange's weight
				cost += a[j]; // and cost
			}
			if (cost <= k) ret = max(ret, weight); // if this set is affordable, we can consider it
		}
		printf("%d\n", ret); // output an answer
	}
    return 0;
}