#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 {
        Node* left = nullptr;
        Node* right = nullptr;
        FrequencyType freq;
        Node(FrequencyType freq)
        : freq(freq) {}
    };
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, const std::unordered_map<Node*, ElementType>& leaves, uint64_t currMask, uint32_t height) {
        if ((node->left == nullptr) && (node->right == nullptr)) {
            h.encodings[leaves.at(node)] = Encoding{currMask, height};
            return height * node->freq;
        } else {
            const auto h1 = Traverse(h, node->left,leaves, currMask << 1, height + 1);
            const auto h2 = Traverse(h, node->right,leaves, (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;
        f >> numNodes;
        nodes.reserve(2 * numNodes);
        std::queue<Node*> q;
        Huffman h{numNodes};
        std::unordered_map<Node*, ElementType> leaves;
        leaves.reserve(numNodes);

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

        auto popQueue = [&] () -> Node* {
            if (q.empty()) {
                return nullptr;
            }
            auto ret = q.front();
            q.pop();
            return ret;
        };

        auto popNode = [&]() -> Node* {
            if (!lastReadNode) {
                if (q.empty()) {
                    return nullptr;
                }
                return popQueue();
            }
            if (q.empty()) {
                return popReadNode();
            }
            if (lastReadNode->freq < q.front()->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->left = left;
            n->right = right;
            q.push(n);
        }
        h.totalLength = Traverse(h, root, leaves, 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;
}