分数: 233 分
问题陈述
高桥负责工厂的质量控制。今天, N 产品正在沿着传送带传送。
每个产品都有一个测量的“内部温度”,并且该产品的内部温度 i第一个产品是 W_i。内部温度不低于阈值的产品 T 是 有缺陷的产品。如果有缺陷的产品按原样发货,则造成损失 D 是按产品产生的。内部温度低于 T 没有缺陷,因此发货时不会造成任何损失。
高桥可以选择传送带上任意数量的产品,并对它们进行“额外的冷却处理”。每个产品最多可以接受一次额外的冷却处理,费用为 每个产品 C 。如果有缺陷的产品接受额外的冷却处理,它就不再有缺陷,可以运输而不会造成任何损失。对于无缺陷的产品也可以进行额外的冷却处理,但由于这些产品无论如何都不会产生任何损失,只是成本 C 被浪费了。
所有产品最终都会发货。高桥希望尽量减少 总和 额外冷却处理的总成本以及运输未接受额外冷却处理的缺陷产品的总损失。鉴于他可以自由选择对哪些产品进行额外的冷却处理,请找到该总和的最小值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T \leq 10^9
- 1 \leq C \leq 10^9
- 1 \leq D \leq 10^9
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N T C D W_1 W_2 \ldots W_N
- 第一行包含 N 代表产品数量, T 代表缺陷产品的阈值, C 代表每次额外冷却处理的成本,以及 D 代表每个缺陷产品的损失,以空格分隔。
- 第二行包含 W_1, W_2, \ldots, W_N 代表产品的内部温度,以空格分隔。
输出
在单行上以整数形式输出总成本和总损失之和的最小值。
示例输入 1
5 30 10 25 15 30 25 40 35
示例输出 1
30
示例输入 2
7 50 100 40 60 30 55 45 80 50 10
示例输出 2
160
示例输入 3
10 1000000000 500000000 300000000 999999999 1000000000 500000000 1000000000 999999998 1000000000 200000000 1000000000 999999999 1000000000
示例输出 3
1500000000