#include <fstream>
using namespace std;
ifstream c("rucsac.in");
ofstream v("rucsac.out");
int b[10002],n,g,j,x,w,p;
int main(){c>>n>>g;while(n--){c>>w>>p;for(j=g;j>=0;j--)if(j>=w)x=max(x,b[j]=max(b[j],b[j-w]+p));}v<<x<<"\n";}