//***************************************************************************************************||
//**********************~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*************************************||
//******************||||      AUTHOR: GUNJAN KUMAR BISWAS       ||||*********************************||
//******************||||      INSTITUTION : JGEC               ||||*********************************||
//******************||||~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~||||*********************************||
//***************************************************************************************************||



#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;



#define f(i,a,b)        for(ll i=a;i<b;i++)
#define f0(i,n)         f(i,0,n)
#define fr(i,a,b)       for(ll i=a;i>=b;i--)
#define for1(i,n)       for(ll i=1;i<=n;i++)
#define pb              push_back
#define tc(t)           int t;cin >>t;while(t--)
#define lol             std::ios::sync_with_stdio(false); cin.tie(NULL);
#define endl            "\n"
#define mp              make_pair
#define ss              second
#define ff              first
#define ll              long long
#define int             long long
#define pii             pair< int,int >
#define pll             pair< ll,ll >
#define sz(a)           a.size()
#define inf             (1000*1000*1000+5)
#define all(a)          a.begin(),a.end()
#define arr(a,n)        int a[n];f0(i, n) cin >> a[i];
#define ini(a,n)        memset(a,n,sizeof(a))
#define printArr(a,n)   f0(i,n) cout<<a[i]<<" ";
#define in              cin>>
#define rr              return 0;
#define vint            vector< int >
#define l_b             lower_bound
#define u_b             upper_bound
#define mod             1000000007
#define pi              3.141592653589793238
#define fmap(m)         for(auto i=m.begin();i!=m.end();i++)
#define deb(x)          cout<< #x <<"=" <<x<<endl;
#define deb2(x,y)       cout<<#x<<"="<<x <<"," <<#y<<"="<<y<<endl;

void input_File()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

///////////// FUNCTIONS//////////


bool isPrime(ll n)          //checks for prime
{
    if (n <= 1)
        return false;
    for (ll i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}


ll sumofdigits(ll n)        //returns sum of digit of a no.
{
    ll c = 0;
    while (n > 0)
    {
        c++;
        n /= 10;
    }
    return c;
}


int MaxSubArraySumReturn(int a[], int  n)  //negative thakle o kaaj korbe in O(n)
{

    int sum = 0, best = 0;
    f0(i, n)
    {
        sum = max(a[i], a[i] + sum);
        best = max(best, sum);
    }
    return best;

}




int fact(int n)
{
    int res = 1;
    for (int i = 2; i <= n; i++)
        res = res * i;
    return res;
}


int nCr(int n, int r)
{
    return fact(n) / (fact(r) * fact(n - r));
}


bool sortinrev(const pair<int, int> &a,
               const pair<int, int> &b)
{
    return (a.first > b.first);
}


int countDivisors(int n)
{
    int cnt = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            // If divisors are equal,
            // count only one
            if (n / i == i)
                cnt++;

            else // Otherwise count both
                cnt = cnt + 2;
        }
    }
    return cnt;
}


int setBitCount(int n)   //Brian Kerinigham algo.... time complexity::O(no of set bits)
{
    int ans = 0;
    while (n)
        n &= n - 1   ,  ans++;
    return ans;
}


int power(int a, int b) //a^b korte hobe   (binary exponentiation)
{
    int result = 1;
    while (b)
    {
        if (b & 1)
        {
            result *= a;
            b--;
        }
        else
        {
            a *= a;
            b >>= 1;
        }
    }
    return result;
}

vector <long long> nextLargerElementUsingStack(long long a[], int n)
{
    stack<ll>s;
    vector<ll>ans;
    ans.pb(-1);
    s.push(a[n - 1]);
    for (int i = n - 2; i >= 0; i--)
    {
        if (a[i] > s.top())
        {
            while (!s.empty() and a[i] > s.top())
                s.pop();
            if (s.empty())  ans.pb(-1);  //khali hoye gele kono big element nei
            else           ans.pb(s.top());  // ekta ba besi boro ache

            s.push(a[i]);
        }
        else if (a[i] < s.top())
        {
            ans.pb(s.top());
            s.push(a[i]);  //smaller element take push kore dilam
        }
    }
    reverse(ans.begin() , ans.end());
    return ans;
}

//*************************************************************************************************//
//*************************************************************************************************//
//*************************************************************************************************//





//***//solver function//***
int n;
int a[1001] , w[1001];
int dp[100001][101] ;
int sack(int sum , int ind  )
{
    if (sum == 0)    return 0;
    if (ind >= n)     return 0;
    if (dp[sum][ind] != -1)    return dp[sum][ind];
    if (sum < w[ind])
        return dp[sum][ind] = sack(sum , ind + 1);
    else
        return dp[sum][ind] = max (a[ind] + sack(sum - w[ind] , ind + 1 ) , sack(sum , ind + 1));
}

void solve()
{
    int s;
    cin >> n >> s;
    f0(i, n)     cin >> w[i] >> a[i];
    ini(dp, -1);
    //int dp[10001][101];
    cout << sack(s, 0);


}//solve end




/////////////////////DRIVER FUNCTION/////////////////
signed main()
{

    input_File();

    lol


    //0 mane no test case......1 mane test case ache

    int isTestCasePresent = 0 ;
    if (isTestCasePresent == 0)
    {
        int t = 1;
        while (t--)
        {
            solve();
        }
    }
    else
    {
        tc(t)
        {
            solve();


        }
    }


    /*

                             _________
                            /         \
                           /  _     _  \
                          /   0     0   \
                         |       ||     |
                         |              |
                          \     -----   /
                           \           /
                            \_ _ _ _ _/

    */


    rr


}


Measured memory_bytes: 82584