#include <fstream>

using namespace std;
int n,G,sol[10001],g[5001],p[5001],max0=0;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int main(){
    fin>>n>>G;
    for(int  i=1;i<=n;i++){
        fin>>g[i]>>p[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=G-g[i];j>=0;j--)
        if(sol[j]+p[i]>sol[j+g[i]]){
            sol[j+g[i]]=sol[j]+p[i];
            if(sol[j+g[i]]>max0)
                max0=sol[j+g[i]];
        }
    fout<<max0;
    return 0;
}