Trong kỳ thi Olympic Tin học Sinh viên, đàn chim cánh cụt tổ chức đại hội xây tháp bánh cá. Mỗi con phụ trách một tháp, nhưng khâu kiểm kê cho thấy các tháp cao thấp lộn xộn: con thì xây quá hăng, con thì có vẻ đã ăn mất vài tầng.

Có N tháp, tháp thứ i hiện cao hᵢ tầng. Ban tổ chức muốn chỉnh sửa để tất cả các tháp có cùng chiều cao. Họ có thể thực hiện các thao tác sau:

• Thêm một tầng vào một tháp, chi phí A.
• Bỏ tầng trên cùng của một tháp không rỗng, chi phí R.
• Chuyển tầng trên cùng từ một tháp không rỗng sang một tháp khác, chi phí M.

Hãy tính chi phí nhỏ nhất để các tháp có cùng chiều cao. Chim cánh cụt rất kiên nhẫn, nhưng ngân sách bánh cá thì không vô hạn.

Input

Dòng đầu gồm bốn số nguyên N, A, R, M: số tháp, chi phí thêm tầng, chi phí bỏ tầng và chi phí chuyển tầng.

Dòng thứ hai gồm N số nguyên h₁, h₂, …, hₙ: chiều cao ban đầu của các tháp.

Đảm bảo:

• 1 ≤ N ≤ 10⁵.
• 1 ≤ A, R, M ≤ 10⁴.
• 0 ≤ hᵢ ≤ 10⁹.

Output

In ra một số nguyên là chi phí nhỏ nhất để đưa tất cả các tháp về cùng chiều cao.

Ví dụ

Input:

3 1 100 100
1 3 8

Output:

12

Giải thích

Cách tốt nhất là thêm 1 tầng vào tháp 1 và 2 cho đến khi bằng tháp 3.

Chấm điểm

• N ≤ 100 và max(hᵢ) ≤ 100: 25%.
• max(hᵢ) - min(hᵢ) ≤ 2000: 25%.
• M ≥ A + R: 25%.
• Không có giới hạn: 25%.