#include <stdio.h>
using namespace std;

#define Nmax 5005
#define Gmax 100005

int n, g, greutate[Nmax], profit[Nmax], mat[3][Gmax];

inline int maxim(int i, int j){
    if(i > j) return i;
    return j;
}

void citire(){
    char cc[100];
    int x, j = 0;
    scanf("%i %i", &n, &g);
    fgets(cc, 100, stdin);
    for(register int i = 1; i <= n; ++i){
        fgets(cc, 100, stdin);
        x = j = 0;
        while(cc[j] != ' ') x = x * 10 + cc[j] - '0', ++j;
        greutate[i] = x;
        ++j; x =0;
        while(cc[j] != '\n') x = x * 10 + cc[j] - '0', ++j;
        profit[i] = x;
    }
    fclose(stdin);
}

void rezolva(){
    for(register int i = 1; i <= n; ++i)
        for(register int j = 0; j <= g; ++j){
            mat[i%3][j] = mat[(i-1)%3][j];
            if(greutate[i] <= j)
               mat[i%3][j] = maxim( mat[(i-1)%3][j], mat[(i-1)%3][j-greutate[i]] + profit[i] );
        }
}

int main(){
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    citire();
    rezolva();
    printf("%i\n", mat[n%3][g]);
    fclose(stdout);

    return 0;
}