#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

int profit[100][100], aleg[100][100],n,g[100],G,c[100];

void citeste()
{ ifstream f("rucsac10.in");
  f>>G>>n;
  int i,j;
  for(i=1;i<=n;i++)
    f>>g[i];
  for(i=1;i<=n;i++)
    f>>c[i];
}
void calculprofit()
{ int i,j,x;
  for(i=1;i<=n;i++)
     for(j=1;j<=G;j++)
     { if(j<g[i]) //nu e loc pt obiectul i in rucsac
            { profit[i][j]=profit[i-1][j];
              aleg[i][j]=aleg[i-1][j];
            }
          else
          { x=profit[i-1][j-g[i]]+c[i];
            if(x>profit[i-1][j])
               { profit[i][j]=x;aleg[i][j]=i;}
            else
               { profit[i][j]=profit[i-1][j];
                 aleg[i][j]=aleg[i][j-1];
               }
          }
        }
}
void scrie_matr(int a[][100], int n, int m)
{ int i,j;
  for(i=1;i<=n;i++)
    {cout<<endl;
     for(j=1;j<=G;j++)
        cout<<setw(4)<<a[i][j];
    }
}
void obiecte(int i, int j)
{   if(i>0){
     if(aleg[i][j]!=aleg[i-1][j])
       { cout<<j<<" obiect= "<<i<<" greutate= "<<g[i]<<" castig= "<<c[i]<<endl;
         j=j-g[i];
         while(i>1 && aleg[i][j]==aleg[i-1][j])i--;
         obiecte(i,j);}
     else obiecte(i-1,j);}
}
int main()
{   citeste();
    calculprofit();
    cout<<"Matrice profit:\n";
    scrie_matr(profit,n,G);
    cout<<endl<<"\nMatrice alegeri:\n";
    scrie_matr(aleg,n,G);
    cout<<"\n\nProfit maxim = "<<profit[n][G];
    cout<<"\n\nObiecte selectate:\n";
    obiecte(n,G);
    return 0;
}