Giám đốc công ty XYZ xây dựng kế hoạch thuê nhân công để làm dự án đường cao tốc kết nối Đông Tây của tỉnh Quảng Ngãi. Dự án cần triển khai trong ~n~ tháng được đánh số từ ~1~ đến ~n~. Biết rằng bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí trả cho nhà tuyển dụng là ~H~. Mỗi tháng, mỗi nhân công được thuê sẽ được trả một khoản lương ~S~ kể cả không làm việc. Kết thúc mỗi tháng, dự án có quyền sa thải nhân công hoặc không. Để sa thải mỗi nhân công cần trả một khoản chi phí ~D~.

Trước khi dự án bắt đầu thì chưa có nhân công nào. Tháng thứ ~i~ của dự án cần tối thiểu ~a_i~ nhân công. Kết thúc tháng thứ ~n~, toàn bộ nhân công bị sa thải.

Yêu cầu: Hãy giúp Giám đốc xây dựng kế hoạch thuê nhân công để dự án hoàn thành với chi phí thuê nhân công ít nhất có thể.

Input

Dòng thứ nhất chứa số nguyên ~n~ (~1 \le n \le 4 \times 10^5~).

Dòng thứ hai chứa ba số nguyên ~H, S, D~ (~H, S, D \le 10^6~).

Dòng thứ ba chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6~).

Output

Một số nguyên là chi phí tối thiểu tìm được.

Subtasks

Subtask 1 (~40 \%~ số điểm): ~n \le 10^3~.

Subtask 2 (~30 \%~ số điểm): ~n \le 10^5~.

Subtask 3 (~30 \%~ số điểm): Không có ràng buộc nào thêm.

Sample Input

4
7 8 9
22 24 29 34

Sample Output

1416