using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace MadMonkeys
{
    // A simple Scanner class meant to be similar to java's scanner.
    // Author: Daniel Wasserman
    // Date: 2013-05-30
    class Scanner
    {
        TextReader Reader;
        public Scanner(TextReader reader)
        {
            Reader = reader;
        }

        static int Index = 0;
        static string[] CurrentLine = { };

        public bool HasNext()
        {
            if (CurrentLine.Length == Index)
            {
                try
                {
                    CurrentLine = Reader.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                    Index = 0;
                    return HasNext();
                }
                catch (System.IO.IOException e)
                {
                    return false;
                }
            }
            return true;
        }

        public String Next()
        {
            if (HasNext()) return CurrentLine[Index++];
            return null;
        }

        public int NextInt()
        {
            return int.Parse(Next());
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public float NextFloat()
        {
            return float.Parse(Next());
        }

        public double NextDouble()
        {
            return double.Parse(Next());
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Scanner input = new Scanner(new StreamReader("monkeys.in"));
            int cases = input.NextInt();
            for (int caseOn = 1; caseOn <= cases; caseOn++)
            {
                int stands = input.NextInt();
                int monkeys = input.NextInt();

                int[] sacrifice = new int[stands];
                int[] gain = new int[stands];

                for (int i = 0; i < stands; i++)
                {
                    sacrifice[i] = input.NextInt() + 1;
                    gain[i] = input.NextInt();
                }

                int[] memo = new int[monkeys + 1];
                for (int i = 1; i < memo.Length; i++)
                    memo[i] = -1;
                int ans = 0;
                for (int i = 0; i < stands; i++)
                {
                    for (int size = monkeys - sacrifice[i]; size >= 0; size--)
                    {
                        if (memo[size] != -1)
                        {
                            memo[size + sacrifice[i]] = Math.Max(memo[size + sacrifice[i]], memo[size] + gain[i]);
                            ans = Math.Max(ans, memo[size + sacrifice[i]]);
                        }
                    }
                }

                Console.WriteLine(ans);
            }
            //Console.ReadLine();
        }
    }
}