#include <fstream>
#include <vector>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int dp1[10010],dp2[10010],n,i,j,cap,val,cnt,x,y;

vector <pair<int, int>>v;

int main()
{
    cin>>n>>cap;
    for(i=1; i<=n; i++)
    {
        cin>>x>>y;
        v.push_back(make_pair(x,y));
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<=cap; j++)
        {
            dp2[j]=dp1[j];
            if(j-v[i].first>=0)
            {
                val=v[i].second+dp1[j-v[i].first];
                dp2[j]=max(dp2[j],val);
            }
        }
        for(j=0; j<=cap; j++)
            dp1[j]=dp2[j];
    }
    cout <<max(dp1[cap],dp2[cap])<< endl;
    return 0;
}