#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int m[2][10005], i, j, n, G, w, p;

int main()
{   f>>n>>G;
    while(n--)
    {   f>>w>>p;
        for(j=1;j<=G;j++)
            if(w<=j)
                m[n%2][j]=max(m[!(n%2)][j],m[!(n%2)][j-w]+p);
            else m[n%2][j]=m[!(n%2)][j];
    }
    g<<m[0][G];
    return 0;
}