#include <fstream>

#define MAX_N 5000
#define MAX_G 10000

using namespace std;

//FILE *fin = fopen("rucsac.in", "r");
//FILE *fout = fopen("rucsac.out", "w");

int N, G;

//struct anakin{
//    int Weight, Profit;
//};
//
//anakin Object[MAX_N + 1];

int Sum[MAX_G + 1];

int sol;

int main(){

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

    int i, j;
    int smax;
    int a, b;

    fin>>N>>G;

    Sum[0] = 1;
    smax = 0;

    for (i = 1; i <= N; i++) {
        fin>>a>>b;
        for (j = G - a; j >= 0; j--) {
            if ((Sum[j] != 0) && (Sum[j + a] < Sum[j] + b)) {
                Sum[j + a] = Sum[j] + b;
                if (Sum[j + a] > sol)
                    sol = Sum[j + a];
            }
        }
    }

//    for (i = 1; i <= N; i++) {
//        for (j = smax; j >= 0; j--) {
//            if ((Sum[j] != 0) && (j + Object[i].Weight <= G) && (Sum[j + Object[i].Weight] < Sum[j] + Object[i].Profit)) {
//                Sum[j + Object[i].Weight] = Sum[j] + Object[i].Profit;
//                if(j + Object[i].Weight > smax)
//                    smax = j + Object[i].Weight;
//                if (Sum[j + Object[i].Weight] > sol)
//                    sol = Sum[j + Object[i].Weight];
//            }
//        }
//    }

    fout<<sol - 1;

    fin.close();
    fout.close();
    return 0;
}