#include <bits/stdc++.h>

using namespace std;
using llong = long long;
llong max_earning()
{
    int N, K;
    cin >> N >> K;

    vector<llong> A(N), B(N);

    for (int i = 0; i < N; i++)
        cin >> A[i] >> B[i];

    int fb_size = *max_element(begin(A), end(A));

    vector<llong> memofb(fb_size + 1, -1);
    function<llong(llong)> fb = [&](llong i)->llong {
        if (i == 0 || i == 1)
            return 1;
        if (memofb[i] != -1)
            return memofb[i];
        return memofb[i] = fb(i - 1) + fb(i - 2);
    };

    vector<llong> memo(K + 1, -1);
    function<llong(llong)> dp = [&](llong l)->llong {
        if (l == 0)
            return 0;

        if (memo[l] != -1)
            return memo[l];

        llong p = 0;
        for (int i = 0; i < N; i++)
            if(l - fb(A[i]) >= 0)
                p = max(p, dp(l - fb(A[i])) + B[i]);

        return memo[l] = p;
    };

    return dp(K);
}

int main()
{
    int T;
    cin >> T;
    vector<int> V;
    for (int i = 0; i < T; i++)
        cout << max_earning() << "\n";
}