#include <fstream>

using namespace std;

int m[5001][10001],n,G,g[10001],p[5001];


int max(int a,int b)
{
    if(a>b)return a;
    return b;
}


int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	
    int i,j;
    fin>>n>>G;

    for(i=1;i<=n;i++)
    {
        fin>>g[i];
        fin>>p[i];
    }

    for(i=n;i>=1;i--)
    {
       for(j=0;j<=G;j++)
       {
           if(j>=g[i])
           {
              m[i][j]=max(m[i+1][j],m[i+1][j-g[i]]+p[i]);
         //    cout<<"da,este"<<endl;
           }
           else
           {
              m[i][j]=m[i+1][j];
           }

          // cout<<"Am calculat m["<<i<<"]["<<j<<"], egal cu "<<m[i][j]<<endl;
       }
    }

    fout<<m[1][G]<<endl;

    fin.close();
	fout.close();

    return 0;
}