View Code of Problem 4041

# include<stdio.h>
# include <string.h>
int dp[1110]={0};
int time[1110]={0},value[1110]={0};
int n,m;
 
int max(int a,int b)
{
	return a<b?b:a;
}
 
void go(int time,int value)
{
	for(int i=m;i>=time;i--)
	{
		dp[i] = max(dp[i],dp[i-time]+value);
	}
}
 
int main(){
		while(scanf("%d%d",&n,&m)!=EOF)
		{
			memset(dp,0,sizeof(dp));
			for(int i=0;i<n;i++)
			{
				scanf("%d%d",&time[i],&value[i]);
			}
			for(int i = 0; i < n; i++)
			{
				go(time[i],value[i]);
			}
			printf("%d\n",dp[m]);
		}
 
	return 0;
}