#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,g1,maxi,i,j,v[5001],gr[5001],a[10001];
int max(int x,int y)
{
    if(x>y)
        return x;
        return y;
}
int main()
{
f>>n>>g1;
for(i=1;i<=n;i++)
    f>>gr[i]>>v[i];
a[0]=1;
for(i=1;i<=n;++i)
    {if(maxi+gr[i]>g1)
        maxi=g1-gr[i];
    for(j=maxi;j>=0;--j)
        if(a[j])
        {if(j==0)
            a[j+gr[i]]=max(a[j+gr[i]],a[j]-1+v[i]);
        else
            a[j+gr[i]]=max(a[j+gr[i]],a[j]+v[i]);
		
	
		}
	maxi=maxi+gr[i];
    }

for(i=g1;i>=1;i--)
    if(a[i])
        {g<<a[i]<<'\n';
        break;
        }
f.close();
g.close();
return 0;
}