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

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

    for (i = 1; i <= N; i++) {
        fscanf(fin, "%d %d", &Object[i].Weight, &Object[i].Profit);
    }

    Sum[0] = 1;
    smax = 0;
    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;
            }
        }
    }

    fprintf(fout, "%d", Sum[smax] - 1);

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