#include<iostream>
using namespace std;

char sp[]="   ";

int x[20], n, nrsol=0, nr[20], val[20], sum[20], S;


int Valid(int k)
{sum[k]=sum[k-1]+val[k]*x[k];
 if (sum[k]>S) return 0;
 if (k==n && sum[k]!=S) return 0;
 return 1;
}

void Afisare()
{int i,j;
 cout<<sp;
 for(i=1;i<=n;i++)
   if (x[i]!=0) cout<<x[i]<<"*"<<val[i]<<" lei + ";
 cout<<char(8)<<char(8)<<"   "<<endl;
 nrsol++;
 if (nrsol%22222==0) cin.get();
}

void Back()
{int k=1, cand;
 x[1]=-1;
 while (k>0)
    {cand=0;
     while (cand==0 && x[k]<nr[k])
      {x[k]++;
       cand=Valid(k);
      }
     if (cand==0) k--;
     else if (k==n) Afisare();
          else {k=k+1; x[k]=-1;
               }
    }
}


int main()
{int i;
 cout<<endl<<endl<<sp<<"Plata unei sume de bani"<<endl;
 cout<<endl<<sp<<" Numarul tipuri monezi: "; cin>>n;
 cout<<sp<<" Dati suma de plata: "; cin>>S;
 cout<<endl;
 for (i=1;i<=n;i++)
    {cout<<sp<<" Valoare moneda tip "<<i<<": "; cin>>val[i];
     cout<<sp<<" Numar monezi tip "<<i<<"  : "; cin>>nr[i];
    }
 Back();
 cout<<endl<<sp<<"Numar solutii: "<<nrsol;
 return 0;
}