#include <iostream>
#include <fstream>

#define MAXN 5001
#define MAXG 10001

#define max(x,y) (((x)>(y))?(x):(y))
#define swap(x,y) {int aux = (x);(x) = (y);(y) = aux;}
using namespace std;

int main() {

    ifstream f("rucsac.in",ios::in);
    ofstream h("rucsac.out",ios::out);


    int i,j,n,g,w[MAXN],p[MAXN],a[2][MAXG];

    f >> n >> g;

    for( i=1; i<= n ; i++)
        f >> w[i] >> p[i];

    int old = 0;
    int nou = 1;


    // initial (0 obiecte)
    for(i=0;i<=g;i++)
        a[0][i] = 0;

    for(i=1;i<=n;i++) {
        for(j=0;j<=g;j++) {

            a[nou][j] = a[old][j];

            if( w[i] <= j)
                a[nou][j] = max(a[nou][j], a[old][j-w[i]]+p[i]);

        }

        swap(old,nou);

    }

    h << a[old][g];

    h.close();
    return 0;
}