#include <stdio.h>
#include <time.h>

#define MAX(a,b) (((a)>(b))?(a):(b))

FILE *fin;
FILE *fout;

#define NMAX 5005
#define GMAX 10005

int n, p[NMAX], g[NMAX], gMax, dp[NMAX][GMAX], mmax_cur = 0, mmax_global = 0;
int freq[NMAX];
struct timespec start, end;

void bkt(int pos, int gCur){
    mmax_global = MAX(mmax_global, mmax_cur);
    for(int i = 1; i <= n; i++){
        if(gCur - g[i] >= 0 && freq[i] == 0){
            freq[i] = 1;
            gCur -= g[i];
            mmax_cur += p[i];
            bkt(pos + 1, gCur);
            freq[i] = 0;
            gCur += g[i];
            mmax_cur -= p[i];
        }
    }
}

int main(){
    //clock_gettime(CLOCK_MONOTONIC, &start);
    //clock_t start = clock();
    fin = fopen("rucsac.in", "rt");
    fscanf(fin, "%d %d", &n, &gMax);
    for(int i = 1; i <= n; i++){
        fscanf(fin, "%d %d", &g[i], &p[i]);
    }
    bkt(1, gMax);
    fout = fopen("rucsac.out", "wt");
    fprintf(fout, "%d\n", mmax_global);
    fclose(fin);
    fclose(fout);
    //clock_t end = clock();
    //double time_taken = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
    //double time_taken = (double)(end - start) / CLOCKS_PER_SEC;
    //printf("Problema rucsacului discreta a fost rezolvata cu backtracking in %lf secunde.\n", time_taken);
    return 0;
}