#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#define nmax 1000100
#define inf 1LL*1e18

using namespace std;

ifstream f("huffman.in");
ofstream g("huffman.out");

struct nod {
    long long next[2], v;
}arb[2*nmax];
int n, i, j,s, k, lg[2*nmax],nr;
long long cd[2*nmax];
long long sol;
char tmp[100];
vector <pair<long long, int> > heap;
pair<long long, int> pak;

void df(int poz, int cod, int niv) {
    if (arb[poz].next[0]) {
        df(arb[poz].next[0], 2*cod, niv+1);
        df(arb[poz].next[1], 2*cod+1, niv+1);
        return;
    }
    lg[poz]=niv;
    cd[poz]=cod;
    sol+= lg[poz]*arb[poz].v;
}

void calc() {
    k = n;
    make_heap(heap.begin(), heap.end());
    while (heap.size() > 1) {
        k++;
        for (i = 0; i < 2; i++) {
            pak = (*heap.begin());
            pop_heap(heap.begin(), heap.end());
            heap.pop_back();
            arb[k].next[i] = pak.second;
            arb[k].v += (-pak.first);
        }
        heap.push_back(make_pair(-arb[k].v, k));
        push_heap(heap.begin(), heap.end());
    }
    df(k,0,0);
}

int main() {
    f >> n;f.get();
    for (i = 1; i <= n; i++) {
        f.getline(tmp,sizeof(tmp));
        nr = 0;j=0;while(tmp[j]>='0'&&tmp[j] <= '9')nr=nr*10+tmp[j++]-'0';
        arb[i].v=nr;
        heap.push_back(make_pair(1LL*-arb[i].v,i));
    }
    calc();
    g << sol << '\n';
    for (i = 1; i <= n; i++)
        g << lg[i]<<' '<<cd[i] << '\n';
    return 0;
}