#include <iostream>
#include <stdlib.h>
#include <fstream>
using namespace std;

///////////////////////////////////////////////////////////////////Regine & Permutari/////////////////////////////////////////////////////////////
/*           int n,x[10];
void citire()
{
    cin>>n;

}
void afisare()
{
    for(int i=1;i<=n;i++)
        cout<<"("<<i<<","<<x[i]<<")"<<endl;

}
int cont(int k)
{
    int i , ok=1;
        for(i=1;i<=k-1;i++)
            if(x[k]==x[i]||abs(x[k]-x[i]==k-i))
                //Permutari fara abs.
            ok=0;
        return ok;
}
void bt()
{
    int i,k;
    for(i=1;i<=n;i++)
        x[i]=0;
    k=1;
    while(k>0)
    if(k==n+1){afisare();k--;}
    else if(x[k]<n)
    {
        x[k]++;
        if(cont(k))
            k++;}
        else {x[k]=0;k--;}}
int main()
{
    citire();
     bt();

    return 0;
}
*/
/*
///////////////////////////////////////////////////////////////////Aranjamente/////////////////////////////////////////////////////////////
int n ,p, x[10];
void citire()
{
    cin>>n>>p;
}
void afisare()
{
    for(int i=1;i<=p;i++)
        cout<<x[i]<<" "<<endl;
}
int cont(int k)
{
    int i , ok=1;
        for(i=1;i<=k-1;i++)
            if(x[k]==x[i])
                ok=0;
        return ok;

}
void bt()
{
    int i , k;
    for(i=1;i<=p;i++)
        x[i]=0;
    k=1;
    while(k>0)
        if(k==p+1)
    {
        afisare();
        k--;
    }
        else if(x[k]<n)
        {
            x[k]++;
            if(cont(k))
                k++;
            else {x[k]=0; k--;}
        }
}
int main ()
{
    citire();
    bt();
}
*/
///////////////////////////////////////////////////////////////////Suma MONEDE/////////////////////////////////////////////////////////////
/*
int n,x[10],v[21],s;

void citire()
{
    cin>>n>>p;
}
void afisare()
{   int s1=0;
    for(int i=1;i<=n;i++)
        s1+=x[i]*v[i];
    if(s1==s)
            for(int i=1;i<=n;i++)

        cout<<x[i]<<"monede de valoarea "<<v[i]<<endl;
}
int continuare(int k)
{
    int i ,ok=1,s1=0;
        for(i=1;i<=k;i++)
            s1+=x[i]*v[i];
            if(s1>s)
            ok=0;
        return ok;
}
void bt()
{
    int i,k;
    for(i=1;i<=n;i++)
        x[i]=-1;
    k=1;
    while(k>0)
    if(k==n+1){afisare();cout<<endl;k--;}
    else if(x[k]<s/v[k])
    {
        x[k]++;
        if(continuare(k))k++;
    }
        else {x[k]=-1;k--;}
}
int main()
{
    f>>n;
    for(int i=1;i<n;i++)f>>v[i];
    f>>s;
    bt();
    return 0;
}

*/

///////////////////////////////////////////////////////////////////Portionare/////////////////////////////////////////////////////////////

/*
int n,x[10];

void citire()
{
    cin>>n;
}
void afisare()
{   int s1=0;
    for(int i=1;i<=n;i++)
        s1+=(x[i]*i);
    if(s1==n)
            {for(int i=1;i<=n-1;i++)
                if(x[i]==1)

        cout<<i<<" ";
        cout<<endl;}}

int continuare(int k)
{
    int i ,ok=1,s1=0;
        for(i=1;i<=k;i++)
            s1+=(x[i]*i);
            if(s1>n)
            ok=0;
        return ok;
}
void bt()
{
    int i,k;
    for(i=1;i<=n-1;i++)
        x[i]=-1;
    k=1;
    while(k>0)
    if(k==n){afisare();cout<<endl;k--;}
    else if(x[k]<1)
    {
        x[k]++;
        if(continuare(k))k++;
    }
        else {x[k]=-1;k--;}
}
int main()
{
    bt();
    return 0;
}
*/

///////////////////////////////////////////////////////////////////Produsul Cartezian/////////////////////////////////////////////////////////////
/*
int n,x[10];

void citire()
{
    cin>>n>>m;
}
void afisare()
{   for(int i=1;i<=n;i++)
        cout<<x[i]<<" ";
        cout<<endl;}

int continuare(int k)
{
return 1;
}
void bt()
{
    int i,k;
    k=1;
    while(k>0)
    if(k==n+1){afisare();cout<<endl;k--;}
    else if(x[k]<m)
    {
        x[k]++;
        if(continuare(k))k++;
    }
        else {x[k]=0;k--;}
}
int main()
{
    bt();
    return 0;
}
*/

///////////////////////////////////////////////////////////////////Colorarea/////////////////////////////////////////////////////////////

/*
int n,m,a[10][10],x[10];

void citire()
{
    int i,y,x;
    ifstream..
    f>>n>>m;
    while(f>>x>>y)
    {
        a[x][y]=1;
        a[y][x]=1;
    }
}
void afisare()
{   for(int i=1;i<=n;i++)
        cout<<x[i]<<" ";
        cout<<endl;}

int continuare(int k)
{
int i,k,ok=1;
for(i=1;i<=k=1;i++)
    if(x[k]==x[i]&&a[i][k]==1)
    ok=0;
return ok;
}
void bt()
{
    int i,k;
    k=1;
    while(k>0)
    if(k==n+1){afisare();cout<<endl;k--;}
    else if(x[k]<m)
    {
        x[k]++;
        if(continuare(k))k++;
    }
        else {x[k]=0;k--;}
}
int main()
{
    bt();
    return 0;
}
*/

///////////////////////////////////////////////////////////////////PROBLEMA CHESTIE CONVOIAJOR/////////////////////////////////////////////////////////////
/*
 int n,m,a[10][10],x[10];

void citire()
{
    int i,y,x;
    ifstream..
    f>>n>>m;
    while(f>>x>>y)
    {
        a[x][y]=1;
        a[y][x]=1;
    }
}
void afisare()
{   int i;
    if(a[x[n]][m]==1)
    for(i=1;i<=n;i++)
        cout<<x[i]<<" ";
        cout<<m;
        cout<<endl;}

int continuare(int k)
{
int i,k,ok=1;
for(i=1;i<=k-1;i++)
    if(x[k]==x[i]||a[x[k]][x[k-1]]==0)
    ok=0;
return ok;
}
void bt()
{
    int i,k;
    for(i=2;i<=n;i++)
        x[i]=0;
    k=1;
    x[1]=m;
    while(k>1)
    if(k==n+1){afisare();cout<<endl;k--;}
    else if(x[k]<n)
    {
        x[k]++;
        if(continuare(k))k++;
    }
        else {x[k]=0;k--;}
}
int main()
{
    bt();
    return 0;
}
*/
///////////////////////////////////////////////////////////////////Combinari/////////////////////////////////////////////////////////////
/*
int n ,p, x[10];
void citire()
{
    cin>>n>>p;
}
void afisare()
{
    for(int i=1;i<=p;i++)
        cout<<x[i]<<" "<<endl;
}
int cont(int k)
{
    int i , ok=1;
        for(i=1;i<=k-1;i++)
            if(x[k]==x[i])
                ok=0;
                if(k>1&&x[k]<x[k-1])
                    ok=0;
        return ok;

}
void bt()
{
    int i , k;
    for(i=1;i<=p;i++)
        x[i]=0;
    k=1;
    while(k>0)
        if(k==p+1)
    {
        afisare();
        k--;
    }
        else if(x[k]<n)
        {
            x[k]++;
            if(cont(k))
                k++;
            else {x[k]=0; k--;}
        }
}
int main ()
{
    citire();
    bt();
}
*/
///////////////////////////////////////////////////////////////////Generarea sub mult./////////////////////////////////////////////////////////////
/*
int n ,x[20];
void citire();
{
    cin>>n;

}
void afisare()
{
    cout<<"{";
    for(int i=1 ; i<=n;i++)
        if(x[i]==1)
        cout<<i<<" ";
    cout<<"}"<<endl;
}
int continuare(int k)
{
    return 1;
}
void bt()
{
    int i,k;
    for(i=1;i<=n;i++)
        x[i]=-1;
    k=1;
    while(k>0)
        if(k==n+1)
    {afisare();
    k--;
    }
        else if(x[k]<1)
        {
            x[k]++;
            if(continuare(k)==1)
                k++;

        }
        else{x[k]=-1;
                k--;
                }
}
int main()
{
    citire();
    bt();
    return 0;
}
*/




                                                                                GREEDY


///////////////////////////////////////////////////////////////////SUMA///////////////////////////////////////////////////////////////////

/*
int n,v[101];
void citire()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
}
void rez();
{
    for(int i=1;i<=n;i++)
        if(v[i]>0)
        cout<<v[i]<<" ";
    cout<<endl;

}
int main()
{
    citire();
    rez();
    return 0;
}
*/


/////////////////////////////////////////////////////////RUCSAC OBOSIT///////////////////////////////////////////////////////////////////////
/*
int G,m,gr[21],c[21];
float e[21];

void citire()
{
    int i;
    ifstream f("date.in");
        f>>G>>n;
        for(i=1;i<=n;i++)
            f>>gr[i];
        for(i=1;i<=n;i++)
        {
            f>>c[i];
            e[i]=(float)c[i]/gr[i];
        }
    f.close();
}
void Greedy()
{
    int ok , aux1,i;
    float aux2;
        do{ok=0;
        for(i=0;i<n;i++)
        {
            if(e[i]<e[i+1])
                {
                    aux1=gr[i];
                    gr[i]=gr[i+1];
                    gr[i+1]=aux1;
                    aux2=c[i];
                    c[i]=c[i+1];
                    c[i+1]=aux2;
                    aux2=e[i];
                    e[i]=e[i+1];
                    e[i+1]=aux2;
                    ok=1;
        }
        }
            }while(ok==1);

    float G1=0;s=0;
        while(G1<G && i<=n)
        {
            if(G1+gr[i]<=G)
            {
                cout<<gr[i]<<" "<<c[i];
                G1=gr[i];
                s+=c[i];
                i++;
                cout<<"Se ia obiectul cu greutate " <<gr[i]<<"  si castigul "<<c[i]<<endl;

            }
            else {float p;
                    p=(G-G1)/gr[i];
                    G1=G;
                    s=s+c[i]*p;
                    i++;
                    cout<<"Se iau obiectele cu greutate " <<p*gr[i]<<" din cele cu greutate "<<gr[i]<<"  si castigul "<<c[i]<<endl;
            }
        }
        cout<<"castigul total "<<s<<endl;
        return 0;
}
main..
*/
/////////////////////////////////////////////////////////SPECTACOLE///////////////////////////////////////////////////////////////////////
/*
int n,nr[101],inceput[101],sf[101];
void citire()
{ ifstream..
    int i , ora , min;
    f>>n;
    for(i=1;i<=n;i++)
        inceput[i]=ora*60+min;
        f>>ora>>min;
        sf[i]=ora*60+min;
        nr[i]=i;
}
void ordonare()
{
    int aux , ok;
     do{ok=0;
     for(i=1;i<n;i++)
            if(sf[nr[i]]>sf[nr[i+1]])
     {
         aux=nr[i];
         nr[i]=nr[i+1];
         nr[i+1]=aux;
         ok=1;
     }
         }while(ok==1);
}
void spectacole()
{
    ofstream..
    int i;
    int ultim;
    g<<nr[i]<<" ";
    ultim=nr[i];
    for(i=2;i<=n;i++)
    {
        if(inceput[nr[i]]>sf[ultim])
            {g<<nr[i]<<" ";
        ultim=nr[i];
    }}
    g.close();
}
int main
..
*/
///////////////////////////////////////////////////////////////////////TIMP DE ASTEPTARE////////////////////////////////////////////////////////
/*
 struct pacient{int o,t}v[101],aux;
  void citire()
  {
      int i
      ifstream..
      f>>n;
      for(i=1;i<=n;i++)
        v[i].o=i;
      f>>v[i].t;
      f.close();
  }
 void ordonare()
 {
     int i,ok;
     do{ok=0;
        for(i=1;i<n;i++)
            if(v[i].t>v[i+1].t)
        {
            aux=v[i];
            v[i]=v[i+1];
            v[i+1]=aux;
            ok=1;
        }
     }while(ok==1);
 }
int main()
{
    citire();
    ordonare();
    int i,s=0;
    for(i=1;i<=n;i++)
    {
    cout<<v[i].o<<" ";}
    for(i=1;i<=n;i++)
        s+=v[i].t*(n-1);
    cout<<"timpul mediu de asteptare este : " <<(float)s/n;
    return 0;
}
 */