Bài 4. Trò chơi

Ban tổ chức giải đấu lập trình game tạo ra ~n~ game cho các thí sinh, game thứ ~i~ (~1 ≤ i ≤ n~) có độ hấp dẫn là ~k_i~. Nam là một thí sinh tham gia giải đấu. Nam được ~t~ đơn vị thời gian để chơi các game này.

Khi còn thời gian, Nam lần lượt xét các game theo thứ tự từ 1 đến ~n~. Mỗi game đều là mới với Nam, nên bạn ấy có hai lựa chọn:

• Xem tựa game và chơi hết game đó, tốn ~a~ đơn vị thời gian.
• Chỉ xem tựa game mà không chơi, tốn ~b~ đơn vị thời gian.

Mỗi game nếu được chơi hết thì Nam nhận được độ hấp dẫn của game đó. Nếu chỉ xem tựa game hoặc chơi chưa xong thì không nhận được độ hấp dẫn nào. Chỉ khi đã xem tựa game thứ ~i~ hoặc chơi game thứ ~i~ thì Nam mới có thể chuyển sang game thứ ~i + 1~.

Yêu cầu

Tính độ hấp dẫn tối đa mà Nam nhận được.

Dữ liệu vào

Từ file văn bản BAI4.INP có cấu trúc như sau:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, t, a, b~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~k_1, k_2, ..., k_n~.

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản BAI4.OUT một số nguyên là giá trị độ hấp dẫn tối đa của Nam đạt được sau thời gian ~t~.

Ví dụ

Ví dụ 1

BAI4.INP
3 5 2 1
2 2 4

BAI4.OUT
6

Giải thích: Chơi game 1 hết 2 đơn vị thời gian, xem game 2 hết 1 đơn vị thời gian, chơi game 3 hết 2 đơn vị thời gian. Độ hấp dẫn đạt được là ~2 + 4 = 6~.

Ví dụ 2

BAI4.INP
3 5 2 1
4 3 2

BAI4.OUT
7

Giải thích: Chơi game 1 và game 2 hết 4 đơn vị thời gian. Độ hấp dẫn đạt được là 7.

Ví dụ 3

BAI4.INP
5 10 3 1
6 1 1 5 5

BAI4.OUT
12

Giải thích: Chơi game 1, xem game 2 và chơi game 3, 4. Không làm gì với game 5. Độ hấp dẫn đạt được là 12.

Giới hạn

• ~n, t, a, b~ là các số nguyên dương.
• ~n ≤ 2 × 10^5~, ~t ≤ 10^9~, ~b < a ≤ 10^9~.
• ~k_i~ là số nguyên dương và ~k_i ≤ 10^9~ với ~1 ≤ i ≤ n~.