#include <stdio.h>
#include <stdint.h>
#include <time.h>

#define NR_OF_OBJECTS 10005

void read(int *gr, int *n, int g[], int p[])
{
  int i;
  FILE *in;
  in = fopen("rucsac.in", "r");
  fscanf(in, "%d%d", n, gr);
  for(i = 1; i <= *n; ++ i)
    fscanf(in, "%d%d", &g[i], &p[i]);
}

void solve(int gr, int n, int g[], int p[])
{
  int i, j, x = 1, y = 2, profit = 0, dp[3][NR_OF_OBJECTS];
  FILE *out;
  out = fopen("rucsac.out", "w");
  
  dp[1][g[1]] = p[1];
  for(i = 2; i <= n; ++ i)
  {
    for(j = 0; j <= gr; ++ j)
    {
      dp[y][j] = dp[x][j];
      if(j - g[i] >= 0 && dp[y][j] < dp[x][j - g[i]] + p[i])
	dp[y][j] = dp[x][j - g[i]] + p[i];
    }
    x = 3 - x;
    y = 3 - y;
  }

  for(j = 0; j <= gr; ++ j)
    if(profit < dp[x][j])
      profit = dp[x][j];
  
  fprintf(out, "%d\n", profit);
}

int main(void)
{
  int Gr, n, g[NR_OF_OBJECTS], p[NR_OF_OBJECTS];
  double start = clock();
  read(&Gr, &n, g, p);
  solve(Gr, n, g, p);
  double stop = clock();
  //printf("%0.2lf ms\n", (stop - start) / 100.0);
  return 0;
}