Restorer Distance

题意翻译

你要修理一堵墙，这堵墙由 $N$ 个宽度为一的砖块构成，其中第 $i$ 块砖的高度为 $h_i$ 。你需要执行下列操作让这 $N$ 块砖的高度变得全部相等。 1、使一块砖的高度加一，这需要花费 $A$ 的代价。 2、使一块高度为正的砖的高度减一，这需要花费 $R$ 的代价。 3、使一块高度为正的砖的高度减一，另一块砖的高度加一，这需要花费 $M$ 的代价。 给定 $N,A,R,M$ ，你需要求出使所有砖的高度变得相同的最小代价。

题目描述

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. You are allowed the following operations: - put a brick on top of one pillar, the cost of this operation is $ A $ ; - remove a brick from the top of one non-empty pillar, the cost of this operation is $ R $ ; - move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is $ M $ . You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $ 0 $ . What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?

输入输出格式

输入格式

The first line of input contains four integers $ N $ , $ A $ , $ R $ , $ M $ ( $ 1 \le N \le 10^{5} $ , $ 0 \le A, R, M \le 10^{4} $ ) — the number of pillars and the costs of operations. The second line contains $ N $ integers $ h_{i} $ ( $ 0 \le h_{i} \le 10^{9} $ ) — initial heights of pillars.

输出格式

Print one integer — the minimal cost of restoration.

输入输出样例

输入样例 #1

3 1 100 100
1 3 8

输出样例 #1

12

输入样例 #2

3 100 1 100
1 3 8

输出样例 #2

9

输入样例 #3

3 100 100 1
1 3 8

输出样例 #3

4

输入样例 #4

5 1 2 4
5 5 3 6 5

输出样例 #4

4

输入样例 #5

5 1 2 2
5 5 3 6 5

输出样例 #5

3