#include <fstream>

using namespace std;
int n,g,i,j,wi,gi,d[2][10005],ok;
int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    fin>>n>>g;
    ok=0;
    for(i=1;i<=n;i++,ok=1-ok)
    {fin>>wi>>gi;
        for(j=0;j<=g;j++)
    {


        d[1-ok][j]=d[ok][j];
        if(wi<=j)
            d[1-ok][j]=max(d[1-ok][j],d[ok][j-wi]+gi);

    }
    }
    fout<<d[ok][g];
    return 0;
}