/* DIT/06/c1/0087
   Exercise 3_b
*/
#include<stdio.h>
int knapsack(int w[5],int p[5],int c,int n);
int MaxValue(int x,int y);
int main()
{
	int w[5],p[5],c,result,n;
	int i;
	
	//get the maximum capacity
	printf("Please Enter the Maximum Capacity:\n");
	scanf("%d",&c);
	
	//get the item no
	printf("Please Enter the number of Item:\n");
    scanf("%d",&n);

	//get the Item Weight
    printf("Please Enter the Weights of Items:\n");
	for(i=0;i<n;i++)
	  {
	       scanf("%d",&w[i]);
	  }

	//get the Item profit
	printf("Please Enter the Profits of Items:\n");
        for(i=0;i<n;i++)
          {
               scanf("%d",&p[i]);
          }
      
	 //calling the knapsack function
     result = knapsack(w,p,c,n);

     printf("The maximum Capacity is = %d\n",result);
}


int knapsack(int w[],int p[],int c,int n)
{
	int knap[n+1][c];
	int i,k,y;

	for(i=0;i<c;i++)
	{
	   knap[0][i] = 0;
	}	

	for(k=1;k<=n;k++)
	{
	    for(y=1;y<=c;y++)
	     {
			if(y<w[k-1])
			 knap[k][y-1] = knap[k-1][y-1];
			else
				if(y>w[k-1])
					knap[k][y-1] = MaxValue((knap[k-1][y-1]),(knap[k-1][y-1-w[k-1]]+p[k-1]));
				else
					knap[k][y-1] = MaxValue((knap[k-1][y-1]),p[k-1]);
	     }		

	}

      return knap[n][c-1];
}

//The funtion to get Maximum value
int MaxValue(int x,int y)
{
    if(x<y)
      return y;
    else
       return x;
}