#include<fstream>
#include<vector>

int main(){
    std::ifstream fin("rucsac.in");
    std::ofstream fout("rucsac.out");
    unsigned short N,G;
    fin>>N>>G;
    std::vector<unsigned short> w(N),p(N);
    for(unsigned short i=0;i<N;++i) fin>>w[i]>>p[i];

    std::vector<unsigned> m1(G+1,0),m2(G+1,0);
    for(unsigned short i=1;i<=N;++i){
        for(int j=0;j<=G;++j)
            //if(j>w[i-1]&&m[j]<(m[j-w[i-1]]+p[i-1])) m[j]=m[j-w[i-1]]+p[i-1];
            if(j>=w[i-1])
                m2[j]=m1[j]>(m1[j-w[i-1]]+p[i-1])?m1[j]:(m1[j-w[i-1]]+p[i-1]);
            else m2[j]=m1[j];
    m1.swap(m2);
    }
    fout<<m1[G]<<'\n';
}