#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream u("rucsac.out");
int w[10000],p[10000];
int o[100000],n,g,i,j;
int main()
{
    f>>n>>g;
    for (i=1;i<=n;i++) f>>w[i]>>p[i];
    o[0]=0;
    int sol=0;
    for (i=1;i<=n;i++)
     for (j=g-w[i];j>=0;j--)
    {
        if (o[j+w[i]]<o[j]+p[i])
        {
            o[j+w[i]]=o[j]+p[i];
            if (o[j+w[i]]>sol)
                sol=o[j+w[i]];
        }
    }
    u<<sol;
    return 0;
}