#include<fstream>
#include<queue>
#define LL long long
using namespace std;
const int Nmax = 1000001, MaxS=10001000;
ifstream f("huffman.in"); ofstream g("huffman.out");
struct cuplu {LL cost; int poz;};
LL lg, bz[Nmax], val[2*Nmax];
int n, nr, fs[2*Nmax], fd[2*Nmax], nrbiti[Nmax];
queue <cuplu> q1, q2;
char S[MaxS];
inline void cr(const cuplu &a, const cuplu &b)
{   cuplu t;
    t.cost = a.cost + b.cost; t.poz = ++nr;
    fd[nr] = a.poz; fs[nr] = b.poz;
    val[nr] = t.cost;
    q2.push(t);
}
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;}
    LL nrfs=(b10<<1);  LL nrfd=nrfs+1;
    df(fd[nod], niv+1, nrfd);
    df(fs[nod], niv+1, nrfs);
}
int main()
{   cuplu t,t1,t2;
    f >> n;
    /*
    for(int i=1; i<=n; ++i)
        {   f >>val[i];
            t.poz = i; t.cost = val[i]; q1.push(t);
        }
    */
    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');
    for(int i=1; i<=n; ++i)
        {
            t.poz = i; t.cost = val[i]; q1.push(t);
        }
    //nr = n;
    t1=q1.front(); q1.pop();
    t2=q1.front(); q1.pop();
    cr(t1,t2);
    while(!q1.empty())
    {   if(q1.front().cost > q2.front().cost)
             {  t1 = q2.front(); q2.pop();
                if(q2.empty()) {t2 = q1.front(); q1.pop();}
                    else if(q1.front().cost > q2.front().cost) {t2 = q2.front(); q2.pop();}
                            else {t2 = q1.front(); q1.pop();}
             }
        else {  t1 = q1.front(); q1.pop();
                if(q1.empty()) {t2 = q2.front(); q2.pop();}
                    else if(q1.front().cost > q2.front().cost) {t2 = q2.front(); q2.pop();}
                            else {t2 = q1.front(); q1.pop();}
             };
        cr(t1,t2);
    };
    while(q2.size()>1)
    {
        t1 = q2.front(); q2.pop();
        t2 = q2.front(); q2.pop();
        cr(t1,t2);
    }
    df(nr,0,0);
    g << lg << "\n";
    for(int i=1; i<=n; ++i)
        g << nrbiti[i] << " " << bz[i] << "\n";f.getline(S,MaxS,EOF);
    g.close(); return 0;
}
/*
void citire(void)
{
    int nr = 0;

    f >> N;
    f.getline(S,MaxS,EOF);
    for(int i=0;S[i];i++)
        if(isdigit(S[i]))
            for(++nr;isdigit(S[i]);A[nr].info = A[nr].info*10+S[i++]-'0');
}



*/