← 返回题目列表

Codeforces · 1355/E

E. 恢复器距离

中文机器翻译题面 查看原题

你必须修复墙壁。墙由 $$$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