#include<stdio.h>

#include<string.h>

#define max(a,b) a>b?a:b

int c[1001],w[1001],dp[1001][1001];

int main()

{

　　int n,v,i,j;

　　while(scanf("%d%d",&n,&v) && n && v)

　　{

　　　　memset(dp,0,sizeof(dp));

　　　　for(i=1;i<=n;i++)

　　　　　　scanf("%d%d",&c[i],&w[i]);

　　　　for(i=1;i<=n;i++)

　　　　for(j=1;j<=v;j++)

　　　　{

　　　　　　if(j<c[i])

　　　　　　　　dp[i][j]=dp[i-1][j];

　　　　　　else

　　　　　　　　dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

　　　　}

　　　　printf("%d\n",dp[n][v]);

　　}

}