//NYOJ 289苹果
#include <iostream>
#include <memory.h>
using namespace std;
int dp[100005];
int max(int a, int b){
return a > b ? a:b;
}
int main(){
int n,c;
int *w;
int *v;
int i = 0;
while(1){
cin>>n>>c;
if(n == 0 && c == 0)
return 0;
w = new int[n+1];
v = new int[n+1];
for(int i = 0; i < n; i++){
cin>>w[i]>>v[i];
}
memset(dp,0,sizeof(dp));
for(int i = 0; i < n; i++){
for(int j = c; j >= w[i]; j--){
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout<<dp[c]<<endl;
}
return 0;
}
