Sản xuất gỗ

WoodPro là một nhà máy nổi tiếng chuyên sản xuất các sản phẩm về gỗ. Do nhu cầu thị trường ngày càng cao, nhà máy quyết định nhập khẩu một dây chuyền thông minh sản xuất ra hàng loạt những thanh gỗ. Mỗi một lượt sản xuất, dây chuyền sẽ nhận vào $N$ thanh gỗ dạng hình trụ có cùng kích thước đáy. Các thanh gỗ được đánh số từ $1$ đến $N$, thanh gỗ thứ $i$ có độ dài $A_i$ xăng-ti-mét. Thứ tự các thanh gỗ đưa vào dây chuyền là $1,2,\dots ,N$. Khi dây chuyền bắt đầu hoạt động, các thanh gỗ được xếp nối đuôi nhau trên một băng chuyền, theo đúng thứ tự nhận vào. Băng chuyền này sẽ di chuyển các thanh gỗ đi theo một chiều qua hai công đoạn xử lý, trước tiên là công đoạn cắt và sau đó là công đoạn dán, mà vẫn giữ nguyên thứ tự các thanh gỗ trên băng chuyền.

Ở công đoạn cắt, có một lưỡi cắt được cố định phía trên băng chuyền. Mỗi khi có thanh gỗ di chuyển qua, hệ thống có thể điều khiển lưỡi cắt hạ xuống để cắt thanh gỗ thành hai thanh có tổng độ dài bằng độ dài của thanh gỗ trước khi cắt. Sau khi cắt, vị trí hai thanh gỗ trên băng chuyền vẫn được giữ nguyên. Chi phí cho mỗi lần cắt như vậy là $C$.

Ở công đoạn dán, có một máy dán được đặt cố định trên băng chuyền. Mỗi khi có hai thanh gỗ kề nhau di chuyển qua, hệ thống có thể điều khiển máy dán hạ xuống để dán hai thanh gỗ này thành một thanh gỗ có độ dài bằng tổng độ dài hai thanh gỗ trước khi dán. Sau khi dán, vị trí của thanh gỗ trên băng chuyền vẫn được giữ nguyên. Chi phí cho mỗi lần dán như vậy là $D$.

Tuấn là một lập trình viên của nhà máy đảm nhận nhiệm vụ lập trình cho hệ thống đối với yêu cầu của mỗi đơn hàng. Do mới nhận được một đơn hàng yêu cầu các thanh gỗ thành phẩm chỉ gồm loại độ dài $L_1$ xăng-ti-mét hoặc loại độ dài $L_2$ xăng-ti-mét, nhà máy giao cho Tuấn lập trình cho hệ thống để sản xuất ra các thanh gỗ thành phẩm như vậy từ $N$ thanh gỗ đầu vào mà không để thừa thanh gỗ nào có độ dài khác $L_1$ và $L_2$.

Yêu cầu: Biết rằng luôn tồn tại một phương án sản xuất ra các thanh gỗ thành phẩm độ dài $L_1$ và $L_2$ từ $N$ thanh gỗ đầu vào mà không để thừa thanh gỗ nào có độ dài khác $L_1$ và $L_2$, hãy tính tổng chi phí ít nhất có thể dùng cho việc cắt và dán, để dây chuyền sản xuất có thể hoàn thành được đơn hàng.

Dữ liệu vào

• Dòng đầu tiên chứa năm số nguyên $N,L_1,L_2,C,D$ lần lượt là số lượng thanh gỗ, hai loại độ dài các thanh gỗ thành phẩm đầu ra, chi phí cho một lần cắt và chi phí cho một lần dán ($1\le N\le {10}^4$; $1\le L_1,L_2\le {10}^9$; $1\le C,D\le {10}^5$).
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$ là độ dài của $N$ thanh gỗ đầu vào ($1\le A_i\le {10}^9$, $\forall i=1,2,\dots ,N$).

Dữ liệu đảm bảo luôn có phương án giải quyết theo yêu cầu đề bài. Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên là tổng chi phí dùng cho việc cắt và dán tìm được.

Ràng buộc

• $1\le N\le {10}^4$.
• $1\le L_1,L_2\le {10}^9$; $1\le C,D\le {10}^5$.
• $1\le A_i\le {10}^9$.
• Luôn tồn tại phương án sản xuất thỏa mãn yêu cầu.

Subtasks

• Subtask 1 ($16\%$ số điểm): $L_1=L_2$.
• Subtask 2 ($16\%$ số điểm): ${\sum }_{i=1}^N{A}_i\le 20$.
• Subtask 3 ($16\%$ số điểm): $N,L_1,L_2\le 100$ và $A_i\le 100$, $\forall i=1,2,\dots ,N$.
• Subtask 4 ($16\%$ số điểm): $A_i\le 2024$, $\forall i=1,2,\dots ,N$.
• Subtask 5 ($12\%$ số điểm): $L_1,L_2\le 2024$.
• Subtask 6 ($12\%$ số điểm): $L_1\le 2024$.
• Subtask 7 ($12\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ