#include <stdio.h>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
  int N, W;
  scanf("%d %d", &N, &W);

  int w[N + 1], v[N + 1];
  for (int i = 1; i <= N; ++i)
    scanf("%d %d", &w[i], &v[i]);

  /*
  // O(NW) space
  int b[N + 1][W + 1]
  for (int i = 0; i <= W; ++i)
    b[0][i] = 0;

  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= W; ++j) {
      if (w[i] <= j)
        b[i][j] = max(b[i-1][j],
                      b[i-1][j - w[i]] + v[i]);
      else
        b[i][j] = b[i - 1][j];
    }
  }
  */

  // O(W) space
  int b[W + 1];
  for (int i = 0; i <= W; ++i) {
    b[i] = 0;
  }

  for (int i = 1; i <= N; ++i) {
    for (int j = W; j >= 0; --j) {
      if (w[i] <= j) {
        b[j] = max(b[j],
                   b[j - w[i]] + v[i]);
      }
    }
  }

  printf("%d\n", b[W]);
  return 0;
}