#include<fstream>
#include<queue>

using namespace std;

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

typedef int64_t var;

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


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

queue<Node> Q1, Q2;

Node extract_min() {
    if(Q1.empty()) {
        Node rez = Q2.front();
        Q2.pop();
        return rez;
    }
    if(Q2.empty()) {
        Node rez = Q1.front();
        Q1.pop();
        return rez;
    }
    if(Q2.front() < Q1.front()) {
        Node rez = Q2.front();
        Q2.pop();
        return rez;
    } else {
        Node rez = Q1.front();
        Q1.pop();
        return rez;
    }
}

#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]);
        Q1.push(Node(i, V[i]));
    }

    while(Q1.size() + Q2.size() > 1) {
        auto node1 = extract_min();
        auto node2 = extract_min();

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

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

    COMP[n] = 1;
    n = _n;


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

    cout<<sum<<'\n';


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

    return 0;
}