1 / 1
Aug 2015

#include<cstdio>
#include<iostream>
using namespace std;
int price[102];
int fun[102];
int dp[502][102];
int keep[502][102];
int bud[502][102];
int main()
{
	int parties,budget;
    scanf("%d" "%d",&budget,&parties);

while(!(parties == 0 && budget == 0))
{
	

	for(int i=1;i<=parties;i++)
	{
		scanf("%d" "%d",&price[i],&fun[i]);
	}


	for(int j =0;j<=budget;j++)
		{
			dp[0][j]=0;
			bud[0][j]=0;
	}
	
	for(int i=0;i<=parties;i++)
	{
		dp[i][0]=0;
		bud[i][0]=0;
	}

	for(int i =1;i<=parties;i++)
	{
		int x,y,m,n;
		for(int j=1;j<=budget;j++)
		{
			if(price[i]<=j)
			{
				   x = fun[i] + dp[i-1][j-price[i]];
				   m= price[i] + bud[i-1][j-price[i]];
				   n=bud[i-1][j];
				   y= dp[i-1][j];

				if(x>y)
				{
					dp[i][j]=x;
					keep[i][j]=1;
					bud[i][j]=m;
				}

				else if(x==y)
				{
					dp[i][j]=x;
					bud[i][j] = m<n?m:n;
					if(m>n)
						keep[i][j]=0;
					else
						keep[i][j]=1;
					
				}

				else
				{
					
					dp[i][j]=y;
					keep[i][j]=0;
					bud[i][j]=n;
				}
			}

			else
			{
				y=dp[i-1][j];
				n=bud[i-1][j];
				dp[i][j]=y;
				keep[i][j]=0;
				[quote][quote][quote][/quote][/quote][/quote]bud[i][j]=n;
			}
		}
	}
	

	printf("%d %d\n",bud[parties][budget],dp[parties][budget]);

	scanf("%d" "%d",&budget,&parties);
}
return 0;
}