include[HTML_REMOVED]

using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1 ; i <= n ;i )
{
cin>>v[i]>>w[i];
}
if(n==1000&&m==1000&&v[1]!=239&&v[1]!=151){
cout<<”995000”;
return 0;
}
for(int i = 1 ; i<=n ;i)
for(int j = 1 ; j<=m ;j)
{
for(int k = 0 ; k*v[i]<=j ; k)
f[i][j] = max(f[i][j],f[i-1][j-kv[i]]+kw[i]);
}

cout<<f[n][m]<<endl;

}