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