#include <fstream>

using namespace std;
int  a[10001], v[10001], cmax[10001], n, b[10001],gmax;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    int i,j,g,k;
    fin>>n>>gmax;
    for(i=1; i<=n; i++)
            fin>>a[i]>>v[i];

    for(j=1;j<=gmax;j++)
        {
            cmax[j]=-1;
            b[j]=n+1;
        }

    for ( i=1;i<=n;++i)
        for (g=0;g+a[i]<=gmax;g++)
            if(b[g]<i && cmax[g+a[i]]<cmax[g]+v[i])
            {
              cmax[g+a[i]]=cmax[g]+v[i];
              b[g+a[i]]=i;

            }
    g=gmax;
    int vm=-1;
    /*
    while(b[g]==n+1)
          g--;
    cout<<cmax[g];
    */
    for(i=1;i<=gmax;i++)
        if(vm<cmax[i])
        vm=cmax[i];
            fout<<vm;

    return 0;
}