#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
// #define int LL
// #define BOOL
const int N = 1024;
#ifdef BOOL
bool solve()
#else
void solve()
#endif
{
    int n, m; cin >> n >> m;
    vector<int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    vector<bitset<N> > f(N);
    f[0][0] = 1;

    for(int i = 1; i <= n; i++)
	{
		// cout << "i = " << i << "---------\n";
        for(int k = 0; k < N; k++)
		{
        	for(int j = m; j >= v[i]; j--)
                f[k] |= (f[k ^ w[i]] >> (j - v[i])) << j;
			// cout << k << ":" << f[k] << "\n";
		}

	}


    for(int i = N - 1; i >= 0; i--)
        if(f[i].count())
        {
            cout << i << '\n';
            break;
        }
}

signed main()
{
	//freopen("D:\\VSC\\00\\in.txt","rt",stdin);
	//freopen("D:\\VSC\\00\\out.txt","wt",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--)
	{
		#ifdef BOOL
		if(solve()) cout << "YES\n";
		else cout << "NO\n";
		#else
		solve();
		#endif
	}
	return 0;
}