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

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

unsigned i,j,n,G,v[5005]={0},g[5005]={0},x1[10005]={0},x2[10005]={0};

int main(){

    fin>>n>>G;

    for(i=0;i<n;++i){

        fin>>g[i]>>v[i];
    }

    for(i=1;i<=n;++i){

        for(j=1;j<=G;++j){

            x2[j]=x1[j];
            if(j>g[i]){

                x2[j]=max(x1[j],x1[j-g[i]]+v[i]);
            }
        }

        for(j=1;j<=G;++j){

            x1[j]=x2[j];
        }
    }

    fout<<x1[G];
}