#include <iostream>
using namespace std;
int Castig[50][50],Alege[50][50],Gr[100],C[100],i,j,n,G,Obiect;
int main()
{
	cout<<"G=";cin>>G;
	cout<<"n=";cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"Gr["<<i<<"]=";
		cin>>Gr[i];
		cout<<"C["<<i<<"]=";
		cin>>C[i];
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=G;j++)
			if(Gr[i]<=j)
				if(C[i]+Castig[i-1][j-Gr[i]]>Castig[i-1][j])
				{
					Castig[i][j]=C[i]+Castig[i-1][j-Gr[i]];
					Alege[i][j]=i;
				}
			else
			{
				Castig[i][j]=Castig[i-1][j];
				Alege[i][j]=Alege[i-1][j];
			}
			else
			{
				Castig[i][j]=Castig[i-1][j];
				Alege[i][j]=Alege[i-1][j];
			}
	i=n;
	j=G;
	cout<<"Castig total"<<Castig[i][j]<<endl;
	while(Alege[i][j])
	{
		Obiect=Alege[i][j];
		cout<<"Produsul "<<Alege[i][j]<<" Greutate"<<Gr[Alege[i][j]]<<" Castig"<<C[Alege[i][j]]<<endl;
		while(Obiect==Alege[i][j])
		{
			j-=Alege[i][j];
			i--;
		}
	}
	return 0;
}