#include<fstream>
#include<queue>

using namespace std;

ifstream cin("huffman.in");
ofstream cout("huffman.out");

typedef int64_t var;

#define MAXN 2000005
var PARENT[MAXN], V[MAXN];
var BIT[MAXN];
var D[MAXN];
bool COMP[MAXN];


var h(var n) {
    if(COMP[n]) return D[n];
    D[n] = h(PARENT[n]) + 1;
    COMP[n] = 1;
    return D[n];
}


struct Node {
    var n, c;
    Node(var a, var b) {
        n = a;
        c = b;
    }
    const bool operator<(const Node &n) const {
        return c > n.c;
    }
};

priority_queue<Node, vector<Node> > Q;

#define DIM 100000
char buff[DIM];
var poz;
void Read(var &a) {
    while(!isdigit(buff[poz]))
        if(++poz == DIM)
            cin.read(buff, DIM), poz=0;
    a = 0;
    while(isdigit(buff[poz])) {
        a = a * 10 + buff[poz] - '0';
        if(++poz == DIM)
            cin.read(buff, DIM), poz=0;
    }
}


int main() {

    var n, v;

    cin.read(buff, DIM);

    Read(n);
    var _n = n;
    for(var i=1; i<=n; i++) {
        Read(V[i]);
        Q.push(Node(i, V[i]));
    }

    while(Q.size() > 1) {
        auto node1 = Q.top();
        Q.pop();
        auto node2 = Q.top();
        Q.pop();

        PARENT[node1.n] = PARENT[node2.n] = ++n;
        BIT[node1.n] = 0;
        BIT[node2.n] = 1;
        Q.push(Node(n, node1.c + node2.c));
    }

    var sum = 0;
    //BIT[n] = 0;
    for(var i=n-1; i>=1; i--) {
        BIT[i] += 2*BIT[PARENT[i]];
    }

    COMP[n] = 1;

    n = _n;


    for(var i=1; i<=n; i++) {
        sum += h(i)*V[i];
    }

    cout<<sum<<'\n';

    for(var i=1; i<=n; i++) {
        cout<<D[i]<<" "<<BIT[i]<<'\n';
    }

    return 0;
}