#include <stdio.h>
#include <stdlib.h>
#define MAX(x,y) (x > y ? x : y)
typedef long long int lld;
typedef unsigned long long int llu;

int main(void) {
  int n, w, vs[100], ws[100], t[100][10001];

  scanf("%d%d", &n, &w);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &vs[i], &ws[i]);
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= w; j++) {
      if (ws[i] <= j) {
        t[i][j] = i ? MAX(t[i - 1][j - ws[i]] + vs[i], t[i - 1][j]) : vs[i];
      } else {
        t[i][j] = i ? t[i - 1][j] : 0;
      }
    }
  }
  printf("%d\n", t[n - 1][w]);
  return 0;
}
