#include <fstream>
#define inf 50000000
using namespace std;

int n, i, g[5004], p[5004],  s, f[10000], j, sol, G;

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

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