#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXW 10010

int MEM1[MAXW], MEM2[MAXW];
int main(){

  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);

  int N, maxW, val, W, i, j;
  int *A, *B, *aux;

  A=MEM1; B=MEM2;
  memset(MEM1, 0, sizeof(MEM1));
  scanf("%d%d", &N, &maxW);

  for(i=1; i<=N; i++){
    scanf("%d%d", &W, &val);

    for(j=0; j<=maxW; j++)
	{
      if(W > j)
		B[j]=A[j];
      else
		B[j]=max(A[j], A[j-W]+val);
    }
    aux=A; A=B; B=aux;
  }
  printf("%d\n", A[maxW]);

  return 0;

}