#include <fstream>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>

#define forRange(a, b) for(int it = a; it < b; it++)

using namespace std;

class Vertex {
public:
    virtual uint64_t getFreq() = 0;
    virtual uint64_t getChar() = 0;
    virtual Vertex* getLeftChild() = 0;
    virtual Vertex* getRightChild() = 0;
};

class Nil : public Vertex {
public:
    uint64_t getFreq() override;
    uint64_t getChar() override;
    Vertex* getLeftChild() override;
    Vertex* getRightChild() override;
};

class Node : public Vertex {
private:
    uint64_t info;
    uint64_t freq;
    Vertex* left, *right;
public:
    Node(uint64_t info, uint64_t freq);
    Node(uint64_t info, uint64_t freq, Vertex* left, Vertex* right);
    Vertex* getLeftChild() override;
    Vertex* getRightChild() override;
    uint64_t getFreq() override;
    uint64_t getChar() override;
};

uint64_t Node::getFreq() {
    return this->freq;
}

Node::Node(uint64_t info, uint64_t freq) {
    this->info = info;
    this->freq = freq;
    this->left = new Nil;
    this->right = new Nil;
}

Node::Node(uint64_t info, uint64_t freq, Vertex* left, Vertex* right) {
    this->info = info;
    this->freq = freq;
    this->left = left;
    this->right = right;
}

uint64_t Node::getChar() {
    return this->info;
}

Vertex* Node::getLeftChild() {
    return this->left;
}

Vertex* Node::getRightChild() {
    return this->right;
}

uint64_t Nil::getFreq() {
    return 0;
}

uint64_t Nil::getChar() {
    return '\0';
}

Vertex* Nil::getLeftChild() {
    return nullptr;
}

Vertex* Nil::getRightChild() {
    return nullptr;
}

class CodesMachine {
public:
    static unordered_map<uint64_t, string> getPrefixCodes(Vertex *root);
};

unordered_map <uint64_t, string> CodesMachine::getPrefixCodes(Vertex* root) {
    queue < pair < Vertex*, string > > q;
    unordered_map<uint64_t, string> prefixCodes;

    q.push(make_pair(root, ""));
    while(!q.empty()) {
        pair<Vertex*, string> head = q.front();
        q.pop();
        if(head.first->getChar() == -1) {
            try {
                q.push(make_pair(head.first->getLeftChild(), head.second + "0"));
                q.push(make_pair(head.first->getRightChild(), head.second + "1"));
            }
            catch(...) {
                exit(-1);
            }
        } else {
            prefixCodes[head.first->getChar()] = head.second;
        }
    }

    return prefixCodes;
}

Vertex* getHuffmanTree(const unordered_map<uint64_t, uint64_t>& frequences) {
    auto comp = []( Vertex* a, Vertex* b ) { return  a->getFreq() > b->getFreq(); };
    priority_queue< Vertex* , vector <Vertex*>, decltype( comp ) > heap( comp );

    for(auto it : frequences) {
        Node* node = new Node(it.first, it.second);
        heap.push(node);
    }

    forRange(1, frequences.size()) {
        Vertex* first = heap.top();
        heap.pop();
        Vertex* second = heap.top();
        heap.pop();
        Node* father = new Node(-1, first->getFreq() + second->getFreq(), first, second);
        heap.push(father);
    }
    return heap.top();
}

unordered_map <uint64_t, uint64_t> readFile(const string& fileName) {
    unordered_map<uint64_t, uint64_t> frequences;

    ifstream in(fileName);
    uint64_t n; in >> n;

    forRange(0, n) {
        uint64_t x; in >> x;
        frequences[it] = x;
    }
    return frequences;
}

uint64_t binToDec(string binary) {
    uint64_t result = 0, p2 = 1;
    reverse(binary.begin(), binary.end());
    for(auto c : binary) {
        if(c == '1')
            result = result + p2;
        p2 = p2 * 2;
    }
    return result;
}

void writeFile(unordered_map<uint64_t, uint64_t> frequences, const unordered_map<uint64_t, string>& prefixCodes, const string& fileName) {
    ofstream out(fileName);
    uint64_t sum = 0;
    for(const auto& it : prefixCodes) {
        sum += frequences[it.first] * it.second.size();
    }
    out << sum << '\n';
    for(const auto& it : prefixCodes) {
        out << it.second.size() << " " << binToDec(it.second) << '\n';
    }
    out.close();
}

int main() {
    // Read input into a hashmap
    unordered_map<uint64_t, uint64_t> frequences = readFile("huffman.in");

    // Generate Huffman codes
    Vertex* root = getHuffmanTree(frequences);
    unordered_map<uint64_t, string> prefixCodes = CodesMachine::getPrefixCodes(root);

    // Write to file informations
    writeFile(frequences, prefixCodes, "huffman.out");
    return 0;
}