#include <iostream>
#include <fstream>
//#include <windows.h>
#include <iostream>
#define MAXN 1000005
using namespace std;
char fisier [3000002], c;
struct nod{
    int64_t lu;
    nod * st = NULL;
    nod * dr = NULL;
    int pos=0;
};
const bool operator < (const nod n1, const nod n2)
{
    return n1.lu<n2.lu;
}
nod Q[MAXN];
nod Q2[MAXN];
uint64_t lg [MAXN], b[MAXN], n=0, T;
void DF (nod * curr, int64_t cod, int lvl)
{
    //cout<<"FAC DEFEU PE NODUL "<<curr<<"("<<curr->lu<<") CU FIII "<<curr->st<<" "<<curr->dr<<"\n";
    if(curr->dr!=NULL && curr->st!=NULL)
    {
        DF(curr->st, cod<<1, lvl+1);
        DF(curr->dr, cod<<1 | 1, lvl+1);
        return;
    }
    lg[curr->pos+1]=lvl;
    b[curr->pos+1]=cod;
}
int main()
{
    nod * x[2];
    nod cv;
    int cnt=0, q1=0, q2=0, j=0, nr=0;
    ifstream in ("huffman.in");
    ofstream out ("huffman.out");
    ofstream debug("debug.txt");
    //parsam plm
    in.read(fisier, 3000000);
    while (c!='\n')
    {
        c=fisier[j];
        if('0'<=c && c<='9')
        {
            n*=10;
            n+=(c-'0');
        }
        ++j;
    }
    while(fisier[j]>'9' || fisier[j]<'0')
        ++j;
    while(c!=0)
    {
        c=fisier[j];
        if('0' <= c && c <='9')
        {
            nr*=10;
            nr+= (c - '0');
            ++j;
        }
        else
        {
            if(j==3000000 && !in.eof())
            {
                //cout<<"Reading continuation...\n";
                j=0;
                c=fisier[j];
                in.read(fisier, 3000000);
            }
            else
            {
            cv.lu=nr;
            cv.pos=cnt;
            Q[cnt]=cv;
            ++cnt;
            ++j;
            nr=0;
            }
        }
    }
    //cout<<j;
    //debug<<n<<"\n";
    //for(int i=0;i<n;++i)
        //debug<<Q[i].lu<<"\n";
    cnt=0;
    while(cnt<n-1)    //mai avem noduri neprocesate
    {
        x[0]=NULL;
        x[1]=NULL;
        for(int i=0;i<2;++i)
        {
            if(n-q1==0)
            {
                x[i]=&Q2[q2];
                //cout<<"IAU ELEMENTUL "<<x[i]->lu<<"("<<q2<<") DIN COADA Q2\n";
                ++q2;
            }
            else if(cnt-q2==0)
            {
                x[i]=&Q[q1];
                //cout<<"IAU ELEMENTUL "<<x[i]->lu<<"("<<q1<<") DIN COADA Q1\n";
                ++q1;

            }
            else //if(!Q.empty() && !Q2.empty())
            {
                if(Q[q1].lu<Q2[q2].lu)
                {

                    x[i]=&Q[q1];
                    //cout<<"IAU ELEMENTUL "<<x[i]->lu<<"("<<q1<<") DIN COADA Q1\n";
                    ++q1;
                }

                else
                {
                    x[i]=&Q2[q2];
                    //cout<<"IAU ELEMENTUL "<<x[i]->lu<<"("<<q2<<") DIN COADA Q2\n";
                    ++q2;
                }


            }
        }
        cv.st=x[0];
        cv.dr=x[1];
        cv.lu=x[0]->lu+x[1]->lu;
        cv.pos=cnt;
        //cout<<p->st<<" "<<p->dr<<"\n";
        T=T+cv.lu;
        Q2[cnt]=cv;
        ++cnt;
    }
    out<<T<<"\n";
    DF(&Q2[q2], 0, 0);
    for(int i=1;i<=n;++i)
        out<<lg[i]<<" "<<b[i]<<"\n";
    in.close();
    out.close();
    //system("pause");
    return 0;
}