#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++)
    {
        cnt=(cnt+1)%2;
        if(cnt==1)
        {
            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);
                }
            }
        }
        if(cnt==0)
        {
            for(j=0;j<=cap;j++)
            {
                dp1[j]=dp2[j];
                if(j-v[i].first>=0)
                {
                    val=v[i].second+dp2[j-v[i].first];
                    dp1[j]=max(dp1[j],val);
                }
            }
        }
    }
    cout <<max(dp1[cap],dp2[cap])<< endl;
    return 0;
}