#include <iostream>

using namespace std;
int v[100], x[100], n, i, s, nr=0;
int sum(int k)
{
int s1=0, i;
for(i=1; i<=k; i++)
s1=s1+x[i]*v[i];
return s1;
}
void Tip()
{
nr++;
cout<<"solutia: "<<nr<<endl;
for(i=1; i<=n; i++)
if(x[i]!=0)
cout<<x[i]<<" monede de valoarea "<<v[i]<<endl;
cout<<endl;
}
int valid(int k)
{
return (sum(k)<=s);
}
int sol(int k)
{
return (k==n && sum(k)==s);
}
void back(int k)
{
int i;
for(i=0; i<=s/v[k]; i++)
{
x[k]=i;
if(valid(k))
if(sol(k))
Tip();
else if(k<n) back(k+1);
}
}
int main()
{
cout<<"dati suma de plata: "; cin>>s;
cout<<"dati numarul tipurilor de monede: "; cin>>n;
for(i=1; i<=n; i++)
{
cout<<"dati valoarea tipului "<<i<<": "; cin>>v[i];
}
back(1);
if(nr==0)
cout<<"nu avem solutii";
}