#include <fstream>

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

    for(j=1;j<=gmax;j++)
            cmax[j]=-1;

    vm=0;
    for ( i=1;i<=n;i++)
        for (j=vm;j>=0;j--)
            if(j+a[i]<=gmax && cmax[j+a[i]]<cmax[j]+v[i])
            {
              cmax[j+a[i]]=cmax[j]+v[i];
              if(j+a[i]>vm)
                    vm=j+a[i];
            }
    vm=0;
    for(g=1;g<=gmax;g++)
        if(cmax[g]>vm)
            vm=cmax[g];

    fout<<vm;

    return 0;
}