#include <fstream>
#include <algorithm>
using namespace std;

const int G=10005;
int n,g,w,p,maxx,d[G];

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    in>>n>>g;
    d[0]=1;

    for(int k=1;k<=n;k++){
        in>>w>>p;
        for(int j=g-w;j>=0;j--){
            if(d[j+w]<d[j]+p)
                 d[j+w]=d[j]+p;
        }
    }

    for(int i=g;i>=0;i--){
         if(d[i]>maxx)
            maxx=d[i];
    }

    out<<maxx-1<<"\n";

    return 0;
}