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 i^th stack is given as h_i. 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 h_i for i^th stack.

1 <= N <= 10⁵

0 <= A, R, M <= 10⁴

0 <= h_i <= 10⁹

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.