#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,gmax,w[5001],p[5001];
int d[2][10005];

int main()
{

    f>>n>>gmax;

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

    for(int i=1; i<=n; i++)
        for(int j=1; j<=gmax; j++)
            if(w[i]<=j)
                d[i%2][j]=max(d[(i-1)%2][j],d[(i-1)%2][j-w[i]]+p[i]);
            else
                d[i%2][j]=d[(i-1)%2][j];

    g<<d[n%2][gmax];


    return 0;

}