#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");;
ofstream fout("rucsac.out");
int n, G, out, i, j, W[10005], P[10005], f[10005];

int main(){
    fin >> n >> G;
    for (i = 1; i <= n; i++){
        fin >> W[i] >> P[i];
    }
    for(i = 1; i <= G; i++)
        f[i] = -1;
    for (i = 1; i <= n; i++){
        for (j = G - W[i]; j >= 0; j--){
            if ( f[j] >= 0 ){
                if ( f[ j + W[i] ] < f[j] + P[i] )
                    f[ j + W[i] ] = f[j] + P[i];
            }
        }
    }
    for (i = 1; i <= G; i++){
        out = max(out, f[i]);
    }
    fout << out;
    return 0;
}