#include <fstream>
using namespace std;

ifstream f("rucsac.in");
ofstream q("rucsac.out");

int n,g,greut[5005],prof[5005],opt[50005];

int main()
{
    f>>n>>g;
    for (int i=0;i<n;i++)
    {
        f>>greut[i]>>prof[i];
    }
    int sum_max=0,ind_max=0;
    for (int i=0;i<n;i++)
    {
        for (int j=ind_max;j>=0;j--)
        {
            if ((opt[j]!=0 or j==0) and (j+greut[i]<=g) and (opt[j+greut[i]]<opt[j]+prof[i]))
            {
                opt[j+greut[i]]=opt[j]+prof[i];
                if (j+greut[i]>ind_max)
                {
                    ind_max=j+greut[i];
                }
                if (opt[j+greut[i]]>sum_max)
                {
                    sum_max=opt[j+greut[i]];
                }
            }
        }
    }
    q<<sum_max;
    f.close();
    q.close();
    return 0;

}