{"raw_statement":[{"iden":"statement","content":"You have to restore the wall. The wall consists of $N$ pillars of bricks, the height of the $i$-th pillar is initially equal to $h_i$, the height is measured in number of bricks. After the restoration all the $N$ pillars should have equal heights.\n\nYou are allowed the following operations:\n\nYou cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $0$.\n\nWhat is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?\n\nThe first line of input contains four integers $N$, $A$, $R$, $M$ ($1 <= N <= 10^5$, $0 <= A, R, M <= 10^4$) — the number of pillars and the costs of operations.\n\nThe second line contains $N$ integers $h_i$ ($0 <= h_i <= 10^9$) — initial heights of pillars.\n\nPrint one integer — the minimal cost of restoration.\n\n"},{"iden":"input","content":"The first line of input contains four integers $N$, $A$, $R$, $M$ ($1 <= N <= 10^5$, $0 <= A, R, M <= 10^4$) — the number of pillars and the costs of operations.The second line contains $N$ integers $h_i$ ($0 <= h_i <= 10^9$) — initial heights of pillars."},{"iden":"output","content":"Print one integer — the minimal cost of restoration."},{"iden":"examples","content":"Input3 1 100 100\n1 3 8\nOutput12\nInput3 100 1 100\n1 3 8\nOutput9\nInput3 100 100 1\n1 3 8\nOutput4\nInput5 1 2 4\n5 5 3 6 5\nOutput4\nInput5 1 2 2\n5 5 3 6 5\nOutput3\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of pillars.  \nLet $ A, R, M \\in \\mathbb{R}_{\\geq 0} $ be the costs per brick for adding, removing, and moving a brick, respectively.  \nLet $ H = (h_1, h_2, \\dots, h_N) $ be the initial height vector of the pillars, where $ h_i \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ x \\in \\mathbb{Z}_{\\geq 0} $ be the target uniform height of all pillars after restoration.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 0 \\leq A, R, M \\leq 10^4 $  \n3. $ 0 \\leq h_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nMinimize the total cost:  \n$$\n\\min_{x \\in \\mathbb{Z}_{\\geq 0}} \\left( A \\cdot \\sum_{i=1}^N \\max(0, x - h_i) + R \\cdot \\sum_{i=1}^N \\max(0, h_i - x) + M \\cdot \\min\\left( \\sum_{i=1}^N \\max(0, x - h_i), \\sum_{i=1}^N \\max(0, h_i - x) \\right) \\right)\n$$","simple_statement":"You have N pillars with different heights. You can make all pillars the same height using three operations:\n\n- Add a brick to any pillar: cost A  \n- Remove a brick from any pillar: cost R  \n- Move a brick from one pillar to another: cost M  \n\nFind the minimum total cost to make all pillars have equal height.","has_page_source":false}