#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int gr[5001],p[5001],n,gg,a[10001],i,j,b[10001],k;
int main()
{
    f>>n>>gg;
    for(i=1;i<=n;i++)
        f>>gr[i]>>p[i];
   for(i=1;i<=n;i++)
   {
       for(j=1;j<=gg;j++)
        if(j-gr[i]>=0)
        b[j]=max(a[j],a[j-gr[i]]+p[i]);
       else
        b[j]=a[j];
        for(k=1;k<=gg;k++)
            a[k]=b[k];
   }
    g<<b[gg];
    return 0;
}