import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
//rename class to Main to submit on codechef
public class CHRL1 {
    static long max = 0;
    static long cost = 0;
    static long weight = 0;
    static long[] weights;
    static long[] costs;
    static long N;
    static long K;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Object[][] combinations = generateCombinations(10);

        int T = scanner.nextInt();
        while (T-- > 0) {
            N = scanner.nextLong();
            K = scanner.nextLong();
            weights = new long[(int) N];
            costs = new long[(int) N];

            boolean allOnes = true;
            for (int i = 0; i < N; i++) {
                costs[i] = scanner.nextLong();
                weights[i] = scanner.nextLong();
                if (weights[i] != 1) allOnes = false;
            }
            long max;

            if (allOnes) {
                max = subtask1();
            } else if (N == 5) {
                max = subtask2();
            } else {
                max = subtask3(combinations);
            }
            System.out.println(max);
        }
    }

    private static long subtask3_forloops(Object[][] combinations) {
        max = 0;
        cost = 0;
        weight = 0;
        for (int i = 0; i < N; i++) { //select 1
            process(i);
            for (int j = i + 1; j < N; j++) { //select 2
                process(j);
                for (int k = j + 1; k < N; k++) { //select 3
                    process(k);
                    for (int l = k + 1; l < N; l++) { //select 4
                        process(l);
                        for (int m = l + 1; m < N; m++) { //select 5
                            process(m);
                            for (int n = m + 1; n < N; n++) { // select 6
                                process(n);
                                for (int o = n + 1; o < N; o++) { //select 7
                                    process(o);
                                    for (int p = o + 1; p < N; p++) { // select 8
                                        process(p);
                                        for (int q = p + 1; q < N; q++) { // select 9
                                            process(q);
                                            for (int r = q + 1; r < N; r++) { // select 10
                                                process(r);
                                                reduce(r);
                                            }
                                            reduce(q);
                                        }
                                        reduce(p);
                                    }
                                    reduce(o);
                                }
                                reduce(n);
                            }
                            reduce(m);
                        }
                        reduce(l);
                    }
                    reduce(k);
                }
                reduce(j);
            }
            reduce(i);
        }
        return max;
    }

    private static long subtask1() {
        long max = 0;
        long sum = 0;
        Arrays.sort(costs);
        for (long cost : costs) {
            sum += cost;
            if (sum > K) break;
            max++;
        }
        return max;
    }

    private static long subtask2() {
        max = 0;
        cost = 0;
        weight = 0;
        for (int i = 0; i < 5; i++) { //select 1
            process(i);
            for (int j = i + 1; j < 5; j++) { //select 2
                process(j);
                for (int k = j + 1; k < 5; k++) { //select 3
                    process(k);
                    for (int l = k + 1; l < 5; l++) { //select 4
                        process(l);
                        for (int m = l + 1; m < 5; m++) { //select 5
                            process(m);
                            reduce(m);
                        }
                        reduce(l);
                    }
                    reduce(k);
                }
                reduce(j);
            }
            reduce(i);
        }
        return max;
    }

    private static void process(int i) {
        cost += costs[i];
        weight += weights[i];
        if (cost <= K && weight > max) {
            max = weight;
        }
    }

    private static void reduce(int i) {
        cost -= costs[i];
        weight -= weights[i];
    }

    private static long subtask3(Object[][] combinations) {
        long max = 0;
        for (int i = 1; i <= N; i++) {
            List<String> list = (List<String>) combinations[((int) N)][i];
            for (String s : list) {
                long cost = 0;
                long weight = 0;
                for (int j = 0; j < s.length(); j++) {
                    if (s.charAt(j) == '1') {
                        cost += costs[j];
                        if (cost > K) break;
                        weight += weights[j];
                    }
                }
                if (cost <= K && weight > max) {
                    max = weight;
                }

            }
        }
        return max;
    }

    private static Object[][] generateCombinations(int n) {
        Object[][] result = new Object[n + 1][n + 1];
        StringBuilder sb;
        List<String> iCr;
        for (int i = 0; i <= n; i++) {
            iCr = new ArrayList<String>();
            sb = new StringBuilder();
            for (int j = 0; j < i; j++) {
                sb.append(0);
            }
            iCr.add(sb.toString());
            result[i][0] = iCr;
        }

        for (int i = 1; i <= n; i++) {
            for (int r = 1; r <= i; r++) {
                iCr = new ArrayList<String>();
                //1st bit is 0
                if (i - 1 >= r) {
                    List<String> list = (List<String>) result[i - 1][r];
                    for (String s : list) {
                        sb = new StringBuilder();
                        sb.append(0);
                        sb.append(s);
                        iCr.add(sb.toString());
                    }
                }
                //1st bit is 1
                List<String> list = (List<String>) result[i - 1][r - 1];
                for (String s : list) {
                    sb = new StringBuilder();
                    sb.append(1);
                    sb.append(s);
                    iCr.add(sb.toString());
                }
                result[i][r] = iCr;
            }
        }
        return result;
    }
}