#include <fstream>
#include <cstdint>
#include <vector>
#include <queue>
#include <functional>
#include <unordered_map>

struct Huffman {
    struct Encoding {
        uint64_t val;
        uint32_t len;
    };
    using FrequencyType = uint64_t;
    using ElementType = uint32_t;
    using EncodingType = Encoding;
    struct Node {
        struct Children {
            Node* left;
            Node* right;
        };
        enum class NodeType : char {
            Regular,
            Leaf
        };
        union {
            Children children;
            ElementType leafValue;
        };
        NodeType type : 4;
        FrequencyType freq : 60;
        Node(FrequencyType freq)
        : freq(freq), type(NodeType::Regular), children({nullptr, nullptr}) {}
        Node(FrequencyType freq, ElementType element)
        : freq(freq), type(NodeType::Leaf), leafValue(element) {}
    };
private:

    uint64_t numCharacters;
    std::vector<EncodingType> encodings;
    uint64_t totalLength;

    Huffman(uint64_t numCharacters) : numCharacters(numCharacters) {
        encodings.reserve(numCharacters);
    }
    static uint64_t Traverse(Huffman& h, Node* node, uint64_t currMask, uint32_t height) {
        if (node->type == Node::NodeType::Leaf) {
            h.encodings[node->leafValue] = Encoding{currMask, height};
            return height * node->freq;
        } else {
            const auto h1 = Traverse(h, node->children.left, currMask << 1, height + 1);
            const auto h2 = Traverse(h, node->children.right, (currMask << 1) | 1, height + 1);
            return h1 + h2;
        }
    }
public:
    uint64_t NumCharacters() const { return numCharacters; }
    uint64_t TotalLength() const { return totalLength; }
    EncodingType EncodingFor(ElementType el) const { return encodings[el]; }
    static Huffman Construct(std::ifstream& f) {
        std::vector<Node> nodes;
        Node* root = nullptr;
        uint64_t numNodes;
        uint64_t qIdx = 0;
        f >> numNodes;
        nodes.reserve(2 * numNodes);

        std::vector<Node*> q;
        q.reserve(numNodes);

        Huffman h{numNodes};

        auto newNode = [&](FrequencyType freq) -> Node* {
            nodes.emplace_back(freq);
            return &nodes.back();
        };
        auto newLeaf = [&](FrequencyType freq, ElementType element) -> Node* {
            nodes.emplace_back(freq, element);
            return &nodes.back();
        };
        uint64_t currIdx = 0;
        Node* lastReadNode = nullptr;
        auto readNode = [&]() -> void {
            if (currIdx >= numNodes) {
                lastReadNode = nullptr;
                return;
            }
            uint64_t freq;
            f >> freq;
            lastReadNode = newLeaf(freq, currIdx++);
        };
        readNode();
        auto popReadNode = [&]() -> Node* {
            auto ret = lastReadNode;
            readNode();
            return ret;
        };

        auto qEmpty = [&] () -> bool {
            return q.size() == qIdx;
        };

        auto qFront = [&] () -> Node* {
            return q[qIdx];
        };

        auto popQueue = [&] () -> Node* {
            if (qEmpty()) {
                return nullptr;
            }
            return q[qIdx++];
        };

        auto popNode = [&]() -> Node* {
            if (!lastReadNode) {
                if (qEmpty()) {
                    return nullptr;
                }
                return popQueue();
            }
            if (qEmpty()) {
                return popReadNode();
            }
            if (lastReadNode->freq < qFront()->freq) {
                return popReadNode();
            }
            return popQueue();
        };

        while (true) {
            Node* left = popNode();
            Node* right = popNode();
            if (!right) {
                root = left;
                break;
            }
            Node* n = newNode(left->freq + right->freq);
            n->children.left = left;
            n->children.right = right;
            q.push_back(n);
        }
        h.totalLength = Traverse(h, root, 0u, 0);
        return h;
    }
};

int main() {
    std::ifstream fin("huffman.in");
    Huffman h = Huffman::Construct(fin);
    std::ofstream fout("huffman.out");
    fout << h.TotalLength() << '\n';
    for (uint32_t i = 0; i < h.NumCharacters(); ++i) {
        const auto encoding = h.EncodingFor(i);
        fout << encoding.len << ' ' << encoding.val << '\n';
    }
    return 0;
}