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