#include <stdio.h>
#include <stdlib.h>
#define MAX 21
#define CAP_MAX 200
int n, GT;
int castig[MAX], greutate[MAX];
int v[CAP_MAX][MAX];

void readInput (void){
    int i;

    FILE *f= fopen("rucsac.in","r");

    ///printf("Numarul de obiecte: ");
    fscanf(f,"%d", &n);
   /// printf("Capacitatea rucsacului: ");
    fscanf(f,"%d", &GT);


    for (i = 1; i <= n; i++){
        ///printf("Greutate[%d] = ", i);
        fscanf(f,"%d", &greutate[i]);
        ///printf("Castig[%d] = ", i);
        fscanf(f,"%d", &castig[i]);

    }
}
void run ( void ){
    int i, j;

    for ( i = 0; i <= GT; i++)
        v[0][i] = 0;
    for ( i = 0; i <= n; i++)
        v[i][0] = 0;
    for ( i = 1; i <= n; i++)
        for ( j = 1; j <= GT; j++){
            v[i][j] = v[i-1][j];
            if ( (j - greutate[i] >= 0 )&&(v[i][j] < v[i - 1][j - greutate[i]]+ castig[i]))
                v[i][j] = v[i - 1][j - greutate[i]]+ castig[i];

    }
    FILE *g= fopen("rucsac.out","w");
    fprintf(g,"%d", v[n][GT]);

}
int main()
{
    readInput();
    run();
    return 0;
}
/*
10 6
7 3
4 3
2 1
9 1
4 2
5 1
*/