STACKOFBOXES - Stacks of boxes

There are N stacks of boxes, all boxes have same dimensions as 1 unit. The height of a stack is defined as the number of boxes in it. The initial height of ith stack is given as hi. We need to equalize the heights of stacks by adding, removing or moving the boxes across the stacks.

The cost of each operation is defined as following:

  1. Add a box on top of a stack costs A.
  2. Remove a box from top of a non-empty stack costs R.
  3. Moving a box from top of non-empty stack to top of another stack costs M.

Input

First line contains one integer N.

Second line contains 3 integers the costs A, R, M.

Third line contains the N integers as heights hi for ith stack.

1 <= N <= 105

0 <= A, R, M <= 104

0 <= hi <= 109

Output

One integer in a line - the minimum cost of equalising the heights of all stack by using above operations.

Example

Input:
5
1 2 2
5 5 3 6 5

Output:
3

(Move 1 box from 4th stack to 3rd stack now height are (cost 2) → 5 5 4 5 5 → now add one box on 3rd stack (cost 1), total cost = 3.


Added by:MichaelJ
Date:2021-08-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:online judge, not remember correctly

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.