#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,Max,Pmax,Wi,Pi,a[5001],b[5001],i,j,d[100000];
int main()
{
    fin >>n>>g;
    int m=n;
    while (m!=0)
        {
            fin>>Wi>>Pi;
            i++;j++;
            a[i]=Wi;
            b[j]=Pi;
            m--;
        }

    for (i=1;i<=n;i++)
        d[i]=-1;
    d[0]=0 ;
        for (i=1;i<=n;i++)
            for (j=g-a[i];j>=0;j--)
                if (d[j]!=-1 && d[j+a[i]]<d[j]+b[i])
                    d[j+a[i]]=d[j]+b[i];
    for (i=1;i<=g;i++)
        if (Pmax < d[i])
            Pmax=d[i];
   fout<<Pmax;
    return 0;
}