#include <fstream>
#define MXG 10000
#define MXN 5000
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
long V[MXG];
int n,gr;
int w[MXN],p[MXN];
int rucsac()
{
    int i,j;
    for (i=1;i<=n;i++)
        for(j=gr;j>=w[i];j--)
            V[j]=max(V[j],V[j-w[i]]+p[i]);
    return V[gr];
}

int main()
{
    f >> n >> gr;
    for (int i=1; i<=n; ++i)
        f >> w[i] >> p[i];
    g << rucsac();
    return 0;
}