#include <fstream>
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");

int n,g,i,j,v[5005],w[5005],m[5005][10005],maxim;

void citire(){
    fin>>n>>g;
    for (i=1;i<=n;i++)
        fin>>w[i]>>v[i];
}

/*void sortare(){
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
            if (v[i].second<v[j].second)
                swap(v[i],v[j]);
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
            if (v[i].first>v[j].first && v[i].second==v[j].second)
                swap(v[i],v[j]);
}*/

void rucsac(int n,int W){
    for (i=1;i<=n;i++)
        for (j=0;j<=W;j++){
            if (w[i]>j)
                m[i][j]=m[i-1][j];
            else
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
            maxim=max(maxim,m[i][j]);
        }
}

int main(){
    citire();
    //sortare();
    rucsac(n,g);
    fout<<maxim;
    fin.close();
    fout.close();
    return 0;
}