/* ナップザック問題 */

#include <stdio.h>

int main(void)
{
	int n, W;
	int value[100];
  int weight[100];
  int nap_value[10001] = {0};
  int i, j, new_value;

  scanf("%d %d", &n, &W);
  for (i = 0; i < n; i++) {
    scanf("%d %d", &value[i], &weight[i]);
  }

  /* 扱う品物を１つずつ増やしていく */
  for (i = 0; i < n; i++) {
    /* ナップザックの重さがjのものに対して
       品物i番を入れてみる */
    for (j = weight[i]; j < W + 1; j++) {
      /* 品物iを入れてみた場合、新しい価値はどうなるか */
      new_value = nap_value[j - weight[i]] + value[i];

      if (new_value > nap_value[j]) {
        nap_value[j] = new_value;
      }
    }
  }

  printf("%d\n", nap_value[W]);

  return 0;
}