#include<fstream>
#define LL long long
using namespace std;
const int Nmax = 1000005, MaxS=10000050;
struct cuplu {LL cost; int poz;};
LL lg, bz[Nmax], val[2*Nmax];
int n, nr, fs[2*Nmax], fd[2*Nmax], nrbiti[Nmax];
cuplu q1[Nmax], q2[Nmax];
int pq1=1, uq1, pq2=1, uq2;
char S[MaxS];
inline void cr(const cuplu &a, const cuplu &b)
{   val[++nr]=q2[++uq2].cost=a.cost + b.cost;  q2[uq2].poz=nr;
    fd[nr] = a.poz; fs[nr] = b.poz;
}
inline void df(int nod, int niv, LL b10)
{   if(nod!=nr)lg += val[nod];
    if(nod<=n)
        { nrbiti[nod] = niv;  bz[nod] = b10; return;}
    df(fd[nod], niv+1, (b10<<1)+1);
    df(fs[nod], niv+1, (b10<<1));
}
void cit()
{   ifstream f("huffman.in");
    f>>n;
    f.getline(S,MaxS,EOF);
    for(int i=0;S[i];i++)
        if(isdigit(S[i]))
            {   for(++nr;isdigit(S[i]);val[nr] = val[nr]*10+S[i++]-'0');
                q1[++uq1].poz=nr; q1[uq1].cost=val[nr];//Q[0][nr]=nr;
            }
}
void afis()
{   freopen("huffman.out","w",stdout);
    printf("%lld\n",lg);
    for(int i=1; i<=n; i++) printf("%d %lld\n",nrbiti[i],bz[i]);
}
int main()
{   cit();
/*
    f >> n;
    for(int i=1; i<=n; ++i)
        {   f >>val[i];
            q1[++uq1].poz=i; q1[uq1].cost=val[i];
        }
        */
    nr = n;
    cr(q1[pq1++],q1[pq1++]);
    while(pq1<=uq1)
    {   if(q1[pq1].cost > q2[pq2].cost)
             {  if(pq2>=uq2) cr(q2[pq2++],q1[pq1++]);
                    else  if(q1[pq1].cost > q2[pq2+1].cost) cr(q2[pq2++],q2[pq2++]);
                            else cr(q2[pq2++],q1[pq1++]);
             }
        else {  if(pq1>=uq1)cr(q1[pq1++],q2[pq2++]);
                    else if(q1[pq1+1].cost > q2[pq2].cost) cr(q1[pq1++],q2[pq2++]);
                            else cr(q1[pq1++],q1[pq1++]);
             };
    };
    while(pq2<uq2) cr(q2[pq2++],q2[pq2++]);
    df(nr,0,0);
    afis();
    return 0;
}

/*
#include <fstream>
#define Nmax 1000002
#define oo 1LL*(1<<30)
#define ll long long
#define MaxS (Nmax*10)
using namespace std;
struct arbore
    {int fiu[2]; ll frecv;} nod[2*Nmax];
int n, nr, LG[Nmax], Q[2][Nmax], L[2], R[2];
ll sol,B[Nmax];
char S[MaxS];
void dfs(int i, ll config, int nivel)
{   if(nod[i].fiu[0])
        { dfs(nod[i].fiu[0],(config<<1),nivel+1);
          dfs(nod[i].fiu[1],(config<<1)+1,nivel+1);
          return;
        }
    B[i]=config; LG[i]=nivel;
}
void pop(int &x)
{   if(nod[Q[0][L[0]]].frecv<nod[Q[1][L[1]]].frecv)
        x=Q[0][L[0]++]; else x=Q[1][L[1]++];
}
void citire() // citire parsata (fara ea prind 80 pct.)
 {  ifstream f("huffman.in");
    f>>n;
    f.getline(S,MaxS,EOF);
    for(int i=0;S[i];i++)
        if(isdigit(S[i]))
            {   for(++nr;isdigit(S[i]);nod[nr].frecv = nod[nr].frecv*10+S[i++]-'0');
                Q[0][nr]=nr;
            }
}
void afis()
{   freopen("huffman.out","w",stdout);
    printf("%lld\n",sol);
    for(int i=1; i<=n; i++) printf("%d %lld\n",LG[i],B[i]);
}
int main()
{   int a,b;
    citire();
    L[0]=L[1]=1;
    R[0]=n;
    R[1]=0;
    nr=n;
    nod[0].frecv=oo*oo;
    while(L[0]<=R[0]||L[1]<R[1])
    {   pop(a); pop(b);
        ++nr;
        nod[nr].fiu[0]=a; nod[nr].fiu[1]=b;
        nod[nr].frecv=nod[a].frecv+nod[b].frecv;
        sol+=nod[nr].frecv;
        Q[1][++R[1]]=nr;
    }
    dfs(nr,0,0);
    afis();
    return 0;
}

*/