Tóm tắt đề bài

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 → 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 → 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.

Input

Dòng đâu tiên chứa ~4~ số nguyên dương ~n, t, a, b~ (~n \le 2*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~)

Output

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

Test mẫu

3 5 2 1
2 2 4

6

Scoring

Subtask 1 (20%): ~k_i \ge k_{i+1}~ với ~i = 1,..., n-1~

Subtask 2 (40%): ~n, t \le 1000~

Subtask 3 (40%): ~k_i < k_{i+1}~ với ~i = 1,..., n-1~