#include <iostream>
#include <fstream>

#define MAXN 501
#define MAXG 1001
#define max(x,y) (((x)>(y))?(x):(y))
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main() {

    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]);


    }



    g << a[n-1][g-1];



    return 0;
}