#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,line1[10001],sum[5001],gr[5000],line2[10001],minim=2000000000;
int main()
{
    int i,j;
    fin>>n>>g;
    for(i=1;i<=n;i++)
    {
        fin>>gr[i]>>sum[i];
    }


    for(i=1;i<=n;i++)
        {
            for(j=1;j<=g;j++)
             {
                 if(j-gr[i]>=0) line2[j]=max(line1[j],line1[j-gr[i]]+sum[i]);
                else line2[j]=line1[j];
            //  cout<<i<<" "<<j<<" "<<line2[j]<<"\n";
             }
            for(j=1;j<=g;j++)
                line1[j]=line2[j];
        }

        fout<<line2[g];


    return 0;
}



// dp[i][j]=Suma maxima din i obiecte cu greutatea j