#include <bits/stdc++.h>
#define maxn 5001
#define maxg 10001
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int m[maxn],p[maxn];
int optim[maxg];
int main()
{
    int n,g,i,j,sol;
    in>>n>>g;
    for(i=1;i<=n;i++)
    in>>m[i]>>p[i];
    optim[0]=0;
   sol=0;
   for(i=1;i<=n;i++)
   for(j=g-m[i];j>=0;j--)
   {if(optim[j+m[i]]<optim[j]+p[i])
       optim[j+m[i]]=optim[j]+p[i];
       if(optim[j+m[i]]>sol)
       sol=optim[j+m[i]];
   }
out<<sol;
    return 0;
}