#include <fstream>

using namespace std;
int  a[5001], v[5001], 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 (j=0;j+a[i]<=gmax;j++)
            if(b[j]<i && cmax[j+a[i]]<cmax[j]+v[i])
            {
              cmax[j+a[i]]=cmax[j]+v[i];
              b[j+a[i]]=i;

            }
    int vm=0;
    for(g=1;g<=gmax;g++)
        if(cmax[g]>vm)
        vm=cmax[g];

    fout<<vm;

    return 0;
}