#include<stdio.h>
int DP[101][10001],N,W,v[101],w[101];
int max(int x,int y)
{
  return x > y ? x : y;
}
int dp(int n,int weight)
{
  if(DP[n][weight] != -1)
    return DP[n][weight];
  else if ( weight - w[n] >= 0)
    return DP[n][weight] = max(dp(n-1,weight),dp(n-1,weight-w[n])+v[n]);
  else
    return DP[n][weight] = dp(n-1,weight);

}
int main()
{
  int i,j;
  scanf("%d %d",&N,&W);
  for(i=1;i<=N;i++)
    scanf("%d %d",&v[i],&w[i]);
  for(i=0;i<=W;i++)
    DP[0][i] = 0;
  for(i=1;i<=N;i++)
    for(j=0;j<=W;j++)
      DP[i][j] = -1;
  printf("%d\n",dp(N,W));
  return 0;
}

