#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
using namespace std;


const string file = "huffman";

const string infile = file + ".in";
const string outfile = file + ".out";


#define MAXN 1000003
#define INF 1LL << 62

struct HNod
{
	long long sum;
	int l;
	int r;

};

long long totalLg;
unsigned int lg[MAXN];
long long codes[MAXN];

HNod nods[MAXN*2];
int N;
int alloc;

int q1[MAXN];
int q2[MAXN];

int l1;
int l2;
int r1;
int r2;


int extractMin()
{

	long long min1 = l1 != r1 ? nods[q1[l1]].sum : INF;
	long long min2 = l2 != r2 ? nods[q2[l2]].sum : INF;
	int result;
	if(min1 < min2)
	{
		result = q1[l1++];
	}
	else
	{
		result = q2[l2++];	
	}
	return result;
}


void citire()
{
	fstream fin(infile.c_str(), ios::in );

	char buffer[6 * 1024];

	int i = -1 ;
	int currentNumber = 0;
	while(fin.good())
	{
		fin.read(buffer, 6 * 1024);
		int count = fin.gcount();


		for(int j = 0; j < count; j++)
		{

			if (isdigit(buffer[j]) != 0)
			{
				currentNumber *= 10;
				currentNumber += buffer[j] - '0';
			}
			else
			{
				if(i == -1)
				{
					N = currentNumber;
					currentNumber = 0;
					i++;
				}
				else
				{   


					nods[i].sum = currentNumber;
					q1[i] = i;

					i++;
					currentNumber = 0;
				}

			}
		}
	}
	if(currentNumber != 0)
	{
		nods[i].sum = currentNumber;
		q1[i] = i;
		i++;
	}


	r1 = N;
	alloc = N;

	fin.close();
}


void DFS(int root, long long code, int level)
{
	if(root < N)
	{
		lg[root] = level;
		totalLg += (unsigned int)(nods[root].sum) * lg[root];
		codes[root] = code;
	}
	else
	{
		DFS(nods[root].l, code << 1 , level + 1);
		DFS(nods[root].r, (code << 1) + 1, level + 1);
	}
}

void solve()
{
	
	while(r1 - l1 + r2 - l2 != 1)
	{
		int min1 = extractMin();
		int min2 = extractMin();

		nods[alloc].sum = nods[min1].sum + nods[min2].sum;
		nods[alloc].l = min1;
		nods[alloc].r = min2;
		q2[r2++] = alloc;
		alloc++;
	}

	DFS(q2[l2], 0, 0);

}

void afisare()
{
	ofstream fout(outfile.c_str());

	fout << totalLg << "\n";

	for(int i = 0; i < N; i++)
	{
		fout << lg[i] << " " << codes[i] << "\n";
	}

	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();
}