#include<stdio.h>
int main(){
int a,b,dp[102][10002],i,j,v[102],w[102];
scanf("%d %d\n",&a,&b);
for(i=1;i<=a;i++){
scanf("%d %d\n",&v[i],&w[i]);
}
for(i=0;i<=b;i++){
dp[0][i]=0;
}
for(i=1;i<=a;i++){
for(j=0;j<=b;j++){
if(j>=w[i]){
if(dp[i-1][j]>dp[i-1][j-w[i]]+v[i]){
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j]=dp[i-1][j-w[i]]+v[i];
}
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
printf("%d\n",dp[a][b]);
return 0;
}
