#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
ll n,sum,dp[100][sz],val[sz],wi[sz];
///
ll solve(ll idx,ll rim)
{if(rim<0) re -oo;
 if(idx>=n)re 0;

 if(dp[idx][rim]!=-1)
    re dp[idx][rim];

 ll fi=0,se=0;
 fi=solve(idx+1,rim-wi[idx])+val[idx];
 se=solve(idx+1,rim);

 re dp[idx][rim]=max(fi,se);
}
///
int main()
{yalla;
cin>>n>>sum;
for(int i=0;i<n;i++)
    cin>>wi[i]>>val[i];
///
memset(dp,-1,sizeof dp);
cout<<solve(0,sum)<<endl;
 re 0;
}
/*#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
ll n1,n2,k1,k2,modd=100000000;
ll dp[101][101][11][11];

int solve(ll rim1,ll rim2,ll k1_now,ll k2_now )
{  ll fi=0,se=0;
   if(rim1==0 && rim2==0)///cause it is must be
     re 1;
 if(dp[rim1][rim2][k1_now][k2_now]!=-1)
    re dp[rim1][rim2][k1_now][k2_now]%modd;

  if(k1_now==k1)
   {  if(rim2>0)
       re se=solve(rim1,rim2-1,1,k2_now+1);
     re 0;
   }
  if(k2_now==k2)
   {   if(rim1>0)
        re fi=solve(rim1-1,rim2,k1_now+1,1);
    re 0;
   }

   if(rim1>0)
    fi=solve(rim1-1,rim2,k1_now+1,k2_now);
   if(rim2>0)
    se=solve(rim1,rim2-1,k1,k2_now+1);

 re dp[rim1][rim2][k1_now][k2_now]=( (fi%modd)+(se%modd) )%modd;
}
///
int main()
{yalla;
 cin>>n1>>n2>>k1>>k2;
 memset(dp,-1,sizeof dp);
 ///
 cout<<solve(n1,n2,1,1)<<endl;

 re 0;
}
*/
/*#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
int n,m,a[101],b[101],c[101],d[101];
///(idx)_rim from(n)
int dp[12][1002];

int main()
{yalla;
  cin>>n>>m>>c[0]>>d[0];
  a[0]=n,b[0]=1;

  for(int i=1;i<=m;i++)
   cin>>a[i]>>b[i]>>c[i]>>d[i];
///
int maxx=0;
for(int idx=0;idx<=m;idx++)
{
 for(int rim=n;rim>=0;rim--)
 {
  for(int y=0;y<a[idx];y++)
  {
   if(a[idx]-(b[idx]*y)>=0 &&rim-(c[idx]*y)>=0 )
    maxx=max(maxx,max(dp[idx-1][rim],dp[idx-1][rim-(c[idx]*y)] ));
  }
  dp[idx][rim]=maxx;
 }
}
cout<<dp[m][n]<<endl;
 re 0;
}*/
/*
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
ll n1,n2,k1,k2,modd=100000000;
ll dp[101][101][11][11];

int solve(ll rim1,ll rim2,ll k1_now,ll k2_now )
{ if(k1_now>k1||k2_now>k2)
    re 0;
   if(rim1==0 || rim2==0)
    re 1;

 if(dp[rim1][rim2][k1_now][k2_now]!=-1)
    re dp[rim1][rim2][k1_now][k2_now]%modd;

 ll fi=0,se=0;

 fi=solve(rim1-k1_now,rim2,k1_now+1,k2_now);
 se=solve(rim1,rim2-k2_now,k1,k2_now+1);

 re dp[rim1][rim2][k1_now][k1_now]=((fi%modd)+(se%modd))%modd;
}
///
int main()
{yalla;
 cin>>n1>>n2>>k1>>k2;
 memset(dp,-1,sizeof dp);
 ///
 cout<<solve(n1,n2,1,1)<<endl;




 re 0;
}
*/

/*
///مهمممممممممممممممممممم
#include<bits/stdc++.h>
#define ll long long
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
ll l,r,ans;
ll get_num_dig_in_bin(ll xoor)
{
  re (log2(xoor)+1);
}
///
int main()
{yalla;///therom wrote in book

 cin>>l>>r;
ll xoor=(l^r),two=1;
ll tot_num_ones=get_num_dig_in_bin(xoor);

for(int i=0;i<tot_num_ones;i++)
 ans+=two,two*=2;

cout<<ans<<endl;
 re 0;
}
/*
5 5 3 9
1 1 1
1 2 1
1 3
1
2 1
1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1

////
5 5 3 25
1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
2 1 1
2 2 1
2 3 1
2 4 1
2 5 1
3 1 1
3 2 1
3 3 1
3 4 1
3 5 1
4 1 1
4 2 1
4 3 1
4 4 1
4 5 1
5 1 1
5 2 1
5 3 1
5 4 1
5 5 1
*/
/*
#include<bits/stdc++.h>
#define ll long long
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
ll l,r,c=1;
int main()
{yalla;
 //for(int i=1;i<=63;i++)
   // cout<<c<<endl,c*=2;

while(true)
{cin>>l>>r;
 ll maxx=0,fi=0,se=0;
vector< pair<int,pair<int,int> > >v;
 for(int i=l;i<=r;i++)
 {
   for(int y=i;y<=r;y++)
    {ll val=(i^y);
     if( val>=maxx )
      maxx=val,fi=i,se=y,v.push_back({ maxx,{fi,se} } );
    }
 }
 sort(v.rbegin(),v.rend());
 for(int i=0;i<v.size();i++)
 cout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<endl;
}

 re 0;
}

*/
/*
#include<bits/stdc++.h>
#define ll long long
#define OO 2e18
#define oo 1e9
#define yalla ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sz  100005
#define re return
#define mod  1000000007
#define pi acos(-1)
using namespace std;
int grid[505][505],cnt[505][505],n,m,k,q,x,y,c,mini=oo;
vector<pair<int,pair<int,int> > >v;
vector<pair<int,int> >p;
///
void calc()
{for(int c=1;c<=m;c++)
  {for(int r=1;r<=n;r++)
     cnt[r][c]+=cnt[r-1][c];
  }
///
 for(int r=1;r<=n;r++)
 {for(int c=1;c<=m;c++)
    cnt[r][c]+=cnt[r][c-1];
 }
}
///
bool valid(int fi,int se)
{
 if(fi>=1&&fi<n&&se>=1&&se<m)re 1;
 re 0;
}
///
void check()
{
 for(int i=1;i<=n;i++)
 {for(int y=1;y<=m;y++)
   {if(valid(i-(k-1),y-(k-1) ))
    {int last_r=i-(k-1)-1;
     int last_c=y-(k-1)-1;
     int tot_points=cnt[i][y]-(cnt[last_r][y]+(cnt[i][last_c]-cnt[last_r][last_c] ) );

     if(tot_points==k*k)
      p.push_back({i,y});
    }
   }
 }
}
///
int main()
{yalla;
cin>>n>>m>>k>>q;
while(q--)
{cin>>x>>y>>c;
 v.push_back({c,{x,y}});
 cnt[x][y]=1;
 grid[x][y]=c;
}
///
calc();/*
for(int i=1;i<=n;i++)
 {for(int y=1;y<=m;y++)
     cout<<cnt[i][y]<<" ";
 cout<<endl;
 }
check();
for(int i=0;i<p.size();i++)
{int fi=p[i].first,se=p[i].second;
 for(int c=se;c>=(se-k+1);c--)
     mini=min(mini,grid[fi][c]);
 for(int c=se;c>=(se-k+1);c--)
     mini=min(mini,grid[fi-k+1][c]);
  cout<<mini<<endl;
   for(int r=fi-1;r>(fi-k+1);r--)
     mini=min(mini,grid[r][se]);
    for(int r=fi-1;r>(fi-k+1);r--)
     mini=min(mini,grid[r][se-k+1]);
}
cout<<mini<<endl;
 re 0;
}
*/


Measured memory_bytes: 78464