#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int main()
{
int n,Gmax,g[1005],v[1005],C[1005][1005],i,j;
fi>>n>>Gmax;
for(i=1;i<=n;i++){
fi>>g[i]>>v[i];
}
for(i=0;i<=n;i++){
C[i][0]=0;
}
for(j=0;j<=Gmax;j++){
C[0][j]=0;
}
for(i=1;i<=n;i++){
for(j=1;j<=Gmax;j++){
if(g[i]>j||C[i-1][j-g[i]]+v[i]<C[i-1][j])
C[i][j]=C[i-1][j];
else
C[i][j]=C[i-1][j-g[i]]+v[i];
}
}
// for(i=1;i<=n;i++){
// cout<<'\n';
// for(j=1;j<=Gmax;j++){
// cout<<C[i][j]<<" ";
// }
// }
fo<<C[n][Gmax];
}