你必须修复墙壁。墙由 $$$N$$$ 块砖柱组成,第 $$$i$$$ 柱子的高度最初等于 $$$h_{i}$$$,高度以砖块数量测量。修复后,所有 $$$N$$$ 柱子应具有相同的高度。
您可以进行以下操作:
- 在一根柱子上放一块砖,此操作的成本为$$$A$$$;
- 从一个非空的柱子顶部移除一块砖,此操作的成本为$$$R$$$;
- 将一块砖从一个非空柱子的顶部移动到另一个柱子的顶部,此操作的成本为$$$M$$$。
您无法创建额外的支柱或忽略某些预先存在的支柱,即使它们的高度变为 $$$0$$$。
修复的最小总成本是多少,换句话说,使所有柱子高度相等的最小总成本是多少?
输入
输入的第一行包含四个整数 $$$N$$$, $$$A$$$, $$$R$$$, $$$M$$$ ($$$1 \le N \le 10^{5}$$$, $$$0 \le A, R, M \le 10^{4}$$$) — 支柱的数量和运营成本。
第二行包含 $$$N$$$ 整数 $$$h_{i}$$$ ($$$0 \le h_{i} \le 10^{9}$$$) — 柱子的初始高度。
输出
打印一个整数——最小的恢复成本。
示例
输入 #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