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

///-----------------------------------FILES
ifstream in("rucsac.in");
ofstream out("rucsac.out");

///-----------------------------------GLOBAL VARIABLES
#define NMAX 10000
int P[NMAX], W[NMAX], Optim[NMAX], sol;
int n, g;

///-----------------------------------READING THE INPUT
void ReadInput()
{
    in >> n >> g;
    for(int i=1;i<=n;++i)
        in >> W[i] >> P[i];
}

///-----------------------------------SOLUTION
void Solution()
{
    Optim[0] = 0;
    for(int i=1;i<=n;++i)
    {
        for(int j=g-W[i];j>=0;--j)
            if(Optim[j+W[i]] < Optim[j] + P[i])
            {
                Optim[j+W[i]] = Optim[j] + P[i];
                if(Optim[j+W[i]] > sol)
                    sol = Optim[j+W[i]];
            }
    }
}

///-----------------------------------OUTPUT
void Output()
{
    out << sol;
}

///-----------------------------------MAIN
int main()
{
    ReadInput();
    Solution();
    Output();
}