{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou might have heard about Huffman encoding - that is the coding system that minimizes the\nexpected length of the text if the codes for characters are required to consist of an integral number of\nbits.\u003c/p\u003e\n\n\u003cp\u003eLet us recall codes assignment process in \u003ci\u003eHuffman encoding\u003c/i\u003e. First the Huffman tree is constructed.\nLet the alphabet consist of N characters, \u003ci\u003ei\u003c/i\u003e-th of which occurs P\u003csub\u003ei\u003c/sub\u003e times in the input text. Initially all\ncharacters are considered to be active nodes of the future tree, \u003ci\u003ei\u003c/i\u003e-th being marked with P\u003csub\u003ei\u003c/sub\u003e. On each step\ntake two active nodes with smallest marks, create the new node, mark it with the sum of the considered\nnodes and make them the children of the new node. Then remove the two nodes that now have parent\nfrom the set of active nodes and make the new node active. This process is repeated until only one active\nnode exists, it is made the root of the tree.\u003c/p\u003e\n\n\u003cp\u003eNote that the characters of the alphabet are represented by the leaves of the tree. For each leaf node\nthe length of its code in the Huffman encoding is the length of the path from the root to the node. The\ncode itself can be constrcuted the following way: for each internal node consider two edges from it to its\nchildren. Assign 0 to one of them and 1 to another. The code of the character is then the sequence of 0s\nand 1s passed on the way from the root to the leaf node representing this character.\u003c/p\u003e\n\n\u003cp\u003eIn this problem you are asked to detect the length of the text after it being encoded with Huffman\nmethod. Since the length of the code for the character depends only on the number of occurences of this\ncharacter, the text itself is not given - only the number of occurences of each character. Characters are\ngiven from most rare to most frequent.\u003c/p\u003e\n\n\u003cp\u003eNote that the alphabet used for the text is quite huge - it may contain up to 500 000 characters.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cb\u003e\u003cp\u003eThis problem contains multiple test cases!\u003c/p\u003e\u003c/b\u003e\n\u003cp\u003eThe first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.\u003c/p\u003e\n\u003cp\u003eThe output format consists of N output blocks. There is a blank line between output blocks.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eThe first line of the input file contains N - the number of different characters used in the text\n(2 \u0026lt;\u003d N \u0026lt;\u003d 500 000). The second line contains N integer numbers P\u003csub\u003ei\u003c/sub\u003e - the number of occurences of each\ncharacter (1 \u0026lt;\u003d P\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 10\u003csup\u003e9\u003c/sup\u003e, P\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d P\u003csub\u003ei+1\u003c/sub\u003e for all valid \u003ci\u003ei\u003c/i\u003e).\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eOutput the length of the text after encoding it using Huffman method, in bits.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n1\u003cbr\u003e\n\u003cbr\u003e\n3\u003cbr\u003e\n1 1 4\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n8\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cbr\u003e\n"}}]}