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

void readInput (){
    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]);

    }
}
int main()
{
    readInput();
        int i, j, k;
    FILE *g= fopen("rucsac.out","w");
    for ( i = 0; i <= GT; i++)
        v[0][i] = 0;

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

        for ( k = 1; k <= GT; k++)
            v[0][k]=v[1][k];
    }

    fprintf(g,"%d", v[1][GT]);
    return 0;
}