Có ~n~ game, game thứ ~i~ có độ hấp dẫn ~k_i~.

Nam có ~t~ đơn vị thời gian để chơi game theo thứ tự từ 1 đến ~n~.

Mỗi game khi đến lượt Nam, cậu có thể:

• Xem + chơi hết game ~\rightarrow~ tốn ~a~ đơn vị thời gian và nhận toàn bộ độ hấp dẫn ~k_i~.
• Chỉ xem mà không chơi ~\rightarrow~ tốn ~b~ đơn vị thời gian và nhận ~0~ độ hấp dẫn.
• Chỉ khi đã chơi hết hoặc bỏ qua mới chuyển sang game tiếp theo.

Mục tiêu: Tính tổng độ hấp dẫn tối đa có thể đạt sau ~t~ đơn vị thời gian.

Dữ liệu

Vào từ luồng nhập chuẩn:

• Dòng đầu tiên chứa 4 số nguyên dương ~n, t, a, b~ (~n \le 2 \cdot 10^5~; ~t \le 10^9~; ~b < a \le 10^9~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~k_i~ (~k_i \le 10^9~).

Kết quả

Đưa ra luồng xuất chuẩn:

• Một số nguyên: độ hấp dẫn tối đa có thể đạt.

Giới hạn & Subtask

• Subtask 1 (20% số điểm): ~k_i \ge k_{i+1}~ với ~i = 1, \dots, n-1~.
• Subtask 2 (40% số điểm): ~n, t \le 1000~.
• Subtask 3 (40% số điểm): ~k_i < k_{i+1}~ với ~i = 1, \dots, n-1~.

Ví dụ

3 5 2 1
2 2 4

6