> #include <stdio.h>
> #define MAXN 4000 + 10
> int W[MAXN],D[MAXN],d[MAXN][MAXN];
> 
> int main()
> {
> 	int i,j,N,M;
> 	while (scanf("%d%d",&N,&M) == 2){
> 		for (i = 1; i <= N; i++) scanf("%d%d",&W[i],&D[i]);
> 		for (j = 0; j <= M; j++) d[0][j] = 0;
> 		for (i = 1; i <= N; i++)
> 			for (j = 0; j <= M; j++){
> 				d[i][j] = d[i-1][j];
> 				if (j >= W[i]) if (d[i][j] < d[i-1][j-W[i]] + D[i])
> 					d[i][j] = d[i-1][j-W[i]] + D[i];
> 			}
> 		printf("%d\n",d[N][M]);
> 	}
> 	return 0;
> }