#include <stdio.h>

#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(){
    int i, j;
    int smax;
    int a, b;

    fscanf(fin, "%d %d", &N, &G);

    Sum[0] = 1;
    smax = 0;

    for (i = 1; i <= N; i++) {
        fscanf(fin, "%d %d", &a, &b);
        for (j = smax; j >= 0; j--) {
            if ((Sum[j] != 0) && (j + a <= G) && (Sum[j + a] < Sum[j] + b)) {
                Sum[j + a] = Sum[j] + b;
                if(j + a > smax)
                    smax = j + a;
                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];
//            }
//        }
//    }

    fprintf(fout, "%d", sol - 1);

    fclose(fin);
    fclose(fout);
    return 0;
}