#include <iostream>
#include <fstream>

#define MAXN 5001
#define MAXG 10001
#define max(x,y) (((x)>(y))?(x):(y))
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[MAXN][MAXG];

    f >> n >> g;

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

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

            a[i][j] = a[i-1][j];

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


    }



    h << a[n][g];

    h.close();
    return 0;
}