#include<stdio.h>
#include<stdlib.h>

int sell_recursive(int* price, int* family, int* output, int m,int n)
{	
	if(m==1)
	{ 
		output[m-1]=(n/family[m-1])*family[m-1];
		return output[m-1]*price[m-1];
	}
	else
	{	
		int earning=0, *opt;
		opt = (int*)malloc(m*sizeof(int));
		for(int i=0; n>=0;i++)
		{
			int temp = sell_recursive(price, family, output, m-1,n);
			if(temp + i*price[m-1]*family[m-1] > earning)
			{
				opt[m-1]=i*family[m-1];
				for(int j=0;j<m-1;j++)
					opt[j]=output[j];
				earning = temp + i*price[m-1]*family[m-1];
			}
			n = n - family[m-1];
		}
		for(int i=0;i<m;i++)
			output[i]=opt[i];
		return earning;
	}
}

int sell_dynamic(int* price, int* family, int* output, int m,int n)
{
	int **dp, *temp, **sol, i, j, k, temp1;
	temp = (int*)malloc(m*(n+1)*sizeof(int));
	dp = (int**)malloc(m*sizeof(int*));
	
	for(i=0;i<m;i++)
		dp[i]=temp+i*(n+1);
		
	temp = (int*)malloc(m*(n+1)*sizeof(int));
	sol = (int**)malloc(m*sizeof(int*));
	
	for(i=0;i<m;i++)
		sol[i]=temp+i*(n+1);
		
	for(j=0;j<n+1;j++)
	{
		dp[0][j] = (j/family[0])*family[0]*price[0];
		sol[0][j] = (j/family[0])*family[0];
	}
	
	for(i=1;i<m;i++)
		for(j=0;j<n+1;j++)
		{
			dp[i][j]=-1;
			for(k=0;k<=j;k++)
				if(dp[i][j]<dp[i-1][j-k]+(k/family[i])*family[i]*price[i])
				{
					dp[i][j] = dp[i-1][j-k]+(k/family[i])*family[i]*price[i];
					sol[i][j] = (k/family[i])*family[i];
				}
		}
	
	for(i=m-1,temp1=n;i>=0;i--)
	{
		output[i]=sol[i][temp1];
		temp1 = temp1-sol[i][temp1];
	}
	
	return dp[m-1][n];
}

int main()
{
	int i,n,m,*family,*price,*output, earning;

	printf("Write the number of apples that Ramu has: ");
	scanf("%d",&n);

	printf("Write the number of buyers: ");
	scanf("%d",&m);

	family=(int*)malloc(m*sizeof(int));
	price=(int*)malloc(m*sizeof(int));
	output=(int*)malloc(m*sizeof(int));

	printf("Write family sizes: \n");
	for(i=0;i<m;i++)
		scanf("%d",&family[i]);
		
	printf("Write prices: \n");
	for(i=0;i<m;i++)
		scanf("%d",&price[i]);

	for(i=0;i<m;i++)
		output[i]=0;
		
	printf("Output of recursive implementation\n");
		
	earning=sell_recursive(price,family,output,m,n);
	
	printf("Maximum earning is %d. Selling pattern is\n",earning);
	for(i=0;i<m;i++)
		printf("%d, ",output[i]);

	printf("\n");	
	
	printf("Output of dynamic programming implementation\n");
		
	earning=sell_dynamic(price,family,output,m,n);
	
	printf("Maximum earning is %d. Selling pattern is\n",earning);
	for(i=0;i<m;i++)
		printf("%d, ",output[i]);

	printf("\n");		
	return 0;
}