#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,maxim, sol;
int d[10005],g[5001],c[5001];
int main(){
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    for(int i=1;i<=G;i++)
        d[i]=-5000000;
    d[0]=0;
    maxim=0;
    for(int i=1;i<=n;i++){
        for(int j=maxim;j>=0;j--){
            if(d[j]>=0&&j+g[i]<=G&&d[j+g[i]]<d[j]+c[i]){
                d[j+g[i]]=d[j]+c[i];
                sol = max(sol, d[j+g[i]]);
                if(maxim<j+g[i])
                    maxim=j+g[i];
            }
        }
    }
    fout<<sol;
    return 0;
}