#include<fstream>
#define maxn 5005
#define maxg 10004
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");

int i,j,n,w,g[maxn],p[maxn];
int a[3][maxg];

inline int max(int a,int b){
       if(a>b) return a; else return b;
}

int main(){
    fi>>n>>w;
    
    for(i=1;i<=n;i++) fi>>g[i]>>p[i];
    
    for(i=1;i<=n;i++){
      for(j=1;j<=w;j++)
      if(j>=g[i]) a[2][j]=max(a[2][j],p[i]+a[1][j-g[i]]);
      for(j=0;j<=w;j++)a[1][j]=a[2][j];
      }
    
    fo<<a[2][w];
    
    fi.close();
    fo.close();
    return 0;
}