#include <iostream>
#include <fstream>

using namespace std;

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

int r[2][10005], n, g, w[5005], v[5005], maxx, i, j;

int main()
{
    fin>>n>>g;
    for(i=1; i<=n; ++i){
        fin>>w[i]>>v[i];
        for(j=0; j<=g; ++j){
            r[i%2][j]=r[(i-1)%2][j];
            if(j>=w[i])
                r[i%2][j]=max(r[i%2][j], r[(i-1)%2][j-w[i]]+v[i]);
        }
    }
    for(i=1; i<=g; ++i)
        maxx=max(maxx, r[n%2][i]);
    fout<<maxx;
    return 0;
}