B - Factory Quality Inspection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は工場の品質管理を担当しています。今日は N 個の製品がベルトコンベアで流れてきます。

それぞれの製品には「内部温度」が測定されており、i 番目の製品の内部温度は W_i です。内部温度が閾値 T 以上である製品は 不良品 です。不良品をそのまま出荷すると、1 個あたり損失 D が発生します。内部温度が T 未満の製品は不良品ではないため、出荷しても損失は発生しません。

高橋君はベルトコンベア上で、任意の個数の製品を選んで「追加冷却処理」を施すことができます。各製品に対して追加冷却処理を施すのは高々 1 回で、1 個あたりコスト 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
  • 1 行目には、製品の個数を表す N 、不良品となる閾値を表す T 、追加冷却処理 1 個あたりのコストを表す C 、不良品 1 個あたりの損失を表す D が、スペース区切りで与えられる。
  • 2 行目には、各製品の内部温度を表す W_1, W_2, \ldots, W_N がスペース区切りで与えられる。

出力

コストの総額と損失の総額の和の最小値を整数で 1 行に出力せよ。

入力例 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

Score : 233 pts

Problem Statement

Takahashi is in charge of quality control at a factory. Today, N products are coming along a conveyor belt.

Each product has a measured "internal temperature", and the internal temperature of the i-th product is W_i. A product whose internal temperature is at least the threshold T is a defective product. If a defective product is shipped as-is, a loss of D is incurred per product. Products with internal temperature less than T are not defective, so no loss is incurred when they are shipped.

Takahashi can select any number of products on the conveyor belt and apply "additional cooling treatment" to them. Each product can receive additional cooling treatment at most once, at a cost of C per product. If a defective product receives additional cooling treatment, it is no longer defective and can be shipped without incurring any loss. Additional cooling treatment can also be applied to non-defective products, but since those products would not have incurred any loss anyway, only the cost C is wasted.

All products will ultimately be shipped. Takahashi wants to minimize the sum of the total cost of additional cooling treatments and the total loss from shipping defective products that did not receive additional cooling treatment. Given that he can freely choose which products to apply additional cooling treatment to, find the minimum value of this sum.

Constraints

  • 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)
  • All inputs are integers.

Input

N T C D
W_1 W_2 \ldots W_N
  • The first line contains N representing the number of products, T representing the threshold for defective products, C representing the cost per additional cooling treatment, and D representing the loss per defective product, separated by spaces.
  • The second line contains W_1, W_2, \ldots, W_N representing the internal temperatures of the products, separated by spaces.

Output

Output the minimum value of the sum of total cost and total loss as an integer on a single line.

Sample Input 1

5 30 10 25
15 30 25 40 35

Sample Output 1

30

Sample Input 2

7 50 100 40
60 30 55 45 80 50 10

Sample Output 2

160

Sample Input 3

10 1000000000 500000000 300000000
999999999 1000000000 500000000 1000000000 999999998 1000000000 200000000 1000000000 999999999 1000000000

Sample Output 3

1500000000