Một dự án phần mềm cần triển khai trong \(𝑛\) tháng đánh số từ 1 tới \(𝑛\). 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).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(𝑆\) 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í \(𝐷\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(𝑖\) cần tối thiểu \(𝑎_𝑖\) nhân công. Kết thúc tháng thứ
  \(𝑛\), 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

• Dòng 1 chứa số tháng \(𝑛\ (1 \leq 𝑛 \leq 4.10^5)\).
• Dòng 2 chứa ba số nguyên dương \(𝐻, 𝑆,𝐷\ (𝐻, 𝑆,𝐷 \leq 10^6)\).
• Dòng 3 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) \((\forall 𝑖: 𝑎_𝑖 \leq 10^6)\).

Output

• Dòng 1: Ghi chi phí tối thiểu tìm được
• Ghi \(𝑛\) số, số thứ \(𝑖\) là số nhân công làm trong dự án tại tháng thứ \(i\).

Scoring

• Subtask \(1\) (\(22.5\%\) số điểm): \(𝑛 \leq 400\).
• Subtask \(2\) (\(40\%\) số điểm): \(𝑛 \leq 10^4\).
• Subtask \(3\) (\(37.5\%\) số điểm): \(𝑛 \leq 4 \times 10^5\).

Example

3
4 5 6
10 9 11 

265
10 10 11