Description

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

Input 第一行输入一组正整数序列，元素之间以空格分开，以这组序列构造一颗huffman树，每个叶子结点的权值即为整数的值。

Output 输出以上huffman树的带权路径长度，树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

Sample Input 1

36 2 8 5 6 25 13 19 Sample Output 1

301

class HuffmanNode:
    def __init__(self, weight=0, left=None, right=None):
        self.weight, self.left, self.right = weight, left, right

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return self.weight < other.weight
        if isinstance(other, int):
            return self.weight < other
        if isinstance(other, float):
            return self.weight < other

    def __gt__(self, other):
        if isinstance(other, HuffmanNode):
            return self.weight >= other.weight
        if isinstance(other, int):
            return self.weight >= other
        if isinstance(other, float):
            return self.weight >= other

class HuffmanTree:
    def __init__(self, priority: list):
        if len(priority) == 1:
            self.tree = HuffmanNode(priority[0], None, None)
        while len(priority) > 1:
            priority = sorted(priority)

            left_w = priority.pop(0)
            right_w = priority.pop(0)

            if isinstance(left_w, HuffmanNode):
                left_node = left_w
                left_w = left_node.weight
            else:
                left_node = HuffmanNode(left_w, None, None)
            if isinstance(right_w, HuffmanNode):
                right_node = right_w
                right_w = right_node.weight
            else:
                right_node = HuffmanNode(right_w, None, None)

            root_w = left_w + right_w
            root_node = HuffmanNode(root_w, left_node, right_node)
            priority.append(root_node)
        self.tree = priority[0]

    @property
    def wpl(self):
        result = 0
        if isinstance(self.tree, HuffmanNode):
            queue = [(self.tree.left, 1), (self.tree.right, 1)]
        while queue:
            cur = queue.pop(0)
            if isinstance(cur, tuple):
                if isinstance(cur[0], HuffmanNode):
                    if isinstance(cur[0].left, HuffmanNode):
                        queue.append((cur[0].left, cur[1] + 1))
                        queue.append((cur[0].right, cur[1] + 1))
                    else:
                        result += cur[0].weight * cur[1]
        return result

pri = list(map(int, input().split()))
k = HuffmanTree(pri)
print(k.wpl)