/*
    Algrotimul backtracking este mai lent decat cel cu greedy pentru problema rucsacului discreta
deoarece genereaza toate variantele posibile ale obiectelor luate o singura data, in timp ce algoritmul
facut de mine cu greedy (rezolvat cu dinamica) rezolva problema in complexitatea O(n*gMax).
Pentru problema cu backtracking am reprezentat grafic datele pentru valori ale lui n de la 5 a 15

n=5=>0.000795 secunde
n=6=>0.000933 secunde
n=7=>0.001116 secunde
n=8=>0.001230 secunde
n=9=>0.001413 secunde
n=10=>0.001782 secunde
n=11=>0.001929 secunde
n=12=>0.002089 secunde
n=13=>0.002464 secunde
n=14=>0.006550 secunde
n=15=>0.012835 secunde

*/

#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);
    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_gettime(CLOCK_MONOTONIC, &end);
    //double time_taken = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
    //printf("Problema rucsacului discreta a fost rezolvata cu backtracking in %lf secunde.\n", time_taken);
    return 0;
}