#include <iostream>
#include <fstream>
using namespace std;
int n,G,g[5002],v[5002],d[10002],da[10002],i,j,mx;
int main()
{
    ifstream fin ("rucsac.in");
    ofstream fout ("rucsac.out");
    fin>>n>>G;
    for(i=1;i<=n;i++)
    {
        fin>>g[i]>>v[i];
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=G;j++)
        {
            da[j]=max(da[j],d[j]);
            if(j+g[i]<=10000)da[j+g[i]]=max(da[j+g[i]],d[j]+v[i]);
            if(da[j]>mx)mx=da[j];
        }
        for(j=0;j<=G;j++)
        {
            d[j]=da[j];
            da[j]=0;
        }
    }
    fout<<mx;
    return 0;
}