#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
struct Item{
  int value;
  int weight;
};
 
int max(int x ,int y)
{
  if(x>=y)
    return x;
  else return y;
}
 
int main()
{
  int N,W;
  int i,w;
  struct Item *item;
  scanf("%d %d",&N,&W);
  int C[N+1][W+1];
  item=malloc(sizeof(item)*(N+1));
  for(i=1;i<=N;i++)
    scanf("%d %d",&item[i].value,&item[i].weight);
 
  for(w=0;w<=W;w++)
    C[0][w]=0;
 
  for(i=1;i<=N;i++)
    C[i][0]=0;
 
  for(i=1;i<=N;i++)
    for(w=1;w<=W;w++)
      if(item[i].weight<=w){
     
    C[i][w]=max(C[i-1][w],max(item[i].value+C[i-1][w-item[i].weight],item[i].value+C[i][w-item[i].weight]));
      }
      else{
    C[i][w]=C[i-1][w];
      }
 
  printf("%d\n",C[N][W]);
 
  return 0;
}