#ifndef __unix__
#error "OS incompatibility"
#endif

#include <cstdio>
#include <cctype>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>

const int MAX_N(1000001);
const long long MAX_VALUE(1 << 30);

int n;

struct tree
{
	int c;
	int long long f;
	struct tree *left, *right;
} queue [2] [MAX_N], *root;

int push [2];
int length [MAX_N];
long long size, binary [MAX_N];

char s [1000000];

inline void read (void)
{
	int input(open("huffman.in",O_RDONLY));
	read(input,s,sizeof(s));
	close(input);
	char *iterator(s);
	while (std::isdigit(*iterator))
	{
		n *= 10;
		n += *iterator - '0';
		++iterator;
	}
	push[0] = n + 1;
	push[1] = 1;
	int index(1), number;
	while (true)
	{
		if (std::isdigit(*iterator))
		{
			number = 0;
			do
			{
				number *= 10;
				number = *iterator - '0';
				++iterator;
			}
			while (std::isdigit(*iterator));
			queue[0][index].c = index;
			queue[0][index].f = number;
			if (index == n)
				break;
			++index;
		}
		++iterator;
	}
}

inline void print (void)
{
	std::freopen("huffman.out","w",stdout);
	std::printf("%lld\n",size);
	for (int index(1) ; index <= n ; ++index)
		std::printf("%d %lld\n",length[index],binary[index]);
	std::fclose(stdout);
}

inline void merge (struct tree *a, struct tree *b)
{
	queue[1][push[1]].left = a;
	queue[1][push[1]].right = b;
	queue[1][push[1]].c = -1;
	queue[1][push[1]].f = a->f + b->f;
	++push[1];
}

void DepthFirstSearch (struct tree *node, long long code, int s)
{
	if (node->c > 0)
	{
		length[node->c] = s;
		binary[node->c] = code;
		size += s * node->f;
	}
	if (node->left)
		DepthFirstSearch(node->left,code << 1,s + 1);
	if (node->right)
		DepthFirstSearch(node->right,(code << 1) | 0x01,s + 1);
}

inline void Huffman (void)
{
	struct tree *tree1, *tree2;
	int pop [2] = {1, 1};
	int i, j;
	while (true)
	{
		tree1 = tree2 = 0;
		for (i = 0 ; i < 2 ; ++i)
			for (j = 0 ; j < 2 ; ++j)
			{
				if (pop[i] + j < push[i])
				{
					if (!tree1 || queue[i][pop[i] + j].f < tree1->f)
					{
						tree2 = tree1;
						tree1 = &queue[i][pop[i] + j];
					}
					else if (!tree2 || queue[i][pop[i] + j].f < tree2->f)
						tree2 = &queue[i][pop[i] + j];
				}
			}
		if (!tree2)
			break;
		if (tree1->c > 0)
			++pop[0];
		else
			++pop[1];
		if (tree2->c > 0)
			++pop[0];
		else
			++pop[1];
		merge(tree1,tree2);
	}
	root = &queue[1][push[1] - 1];
	DepthFirstSearch(root,0,0);
}

int main (void)
{
	read();
	Huffman();
	print();
	return 0;
}