#include<fstream>

using namespace std;
int D[10010]; ///D[i] = profitul maxim prin care pot obtine greutatea i
int g[5001], p[5001];
int sol, i, j, n, G;
int main () {
    ifstream fin ("rucsac.in");
    ofstream fout("rucsac.out");
    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] );
                sol = max(sol, D[j+g[i]]);
            }
    fout<<-1 + sol;
    return 0;
}