//problema rucsacului 100p pe infoarena
//http://www.infoarena.ro/job_detail/1872120
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int i, n, j,g,m= 0, w[5020], p[5020], a[10050];
a[0]=0;
cin>>n>>g;
for(i=1; i<=n; i++) cin>>w[i]>>p[i];
for(i=1; i<=n; i++) 
for(j=g; j>=w[i]; j--){
if(a[j-w[i]]+p[i]>a[j]) a[j]=a[j-w[i]]+p[i];
if(m<a[j]) m=a[j];
}
cout<<m;
return 0;
}