Một dự án phần mềm cần triển khai trong \(n\) tháng đánh số từ \(1\) tới \(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í \(H\) (trả cho nhà tuyển dụng).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(S\) mỗi tháng kể cả khi không làm việc.
• Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí \(D\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(i\) 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 phải bị sa thải.

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

Input

Vào từ file văn bản PROJECT.INP

• Dòng 1 chứa số tháng \(n\) \((1 \leq n \leq 4 \cdot 10^5)\).
• Dòng 2 chứa ba số nguyên dương \(H,S,D\) \((H,S,D \leq 10^6)\).
• Dòng 3 chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((∀i:a_i \leq 10^6 )\).

Output

Ghi ra file văn bản PROJECT.OUT một số nguyên duy nhất là chi phí tối thiểu tìm được.

Example

3
4 5 6
10 9 11

265

Nguồn: Thầy Lê Minh Hoàng