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

#define MAXW 10010

int main(){

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

  int N, maxW, val, W, i, j;
  //int *A, *B, *aux, MEM1[MAXW], MEM2[MAXW];
  int D[2][MAXW], l=0;

  //A=MEM1; B=MEM2;
  //memset(MEM1, 0, sizeof(MEM1));
  memset(D[0], 0, sizeof(D[0]));

  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];
	D[1-l][j]=D[l][j];
      else
	//B[j]=max(A[j], A[j-W]+val);
	D[1-l][j]=max(D[l][j], D[l][j-W]+val);
	}

    //aux=A; A=B; B=aux;
    l=1-l;

  }

  printf("%d\n", /*A[maxW]*/ D[l][maxW]);

  return 0;

}