Tí đã tham gia Ngày Sách và Văn hóa đọc Việt Nam 21/4 và mua được ~n~ cuốn sách. Mỗi cuốn sách ~i~ có một giá trị hấp dẫn là ~k_i~. Anh ấy đã sắp xếp các cuốn sách lên kệ từ trái qua phải sao cho giá trị hấp dẫn không giảm.

Sau một thời gian dài, Tí mới có thời gian đọc sách. Anh ấy có tổng cộng ~t~ phút để đọc. Với mỗi cuốn sách, Tí có hai lựa chọn:

• Đọc toàn bộ cuốn sách, tốn ~a~ phút;

• Chỉ đọc nội dung từ bìa sách, tốn ~b~ phút.

Tí sẽ bắt đầu từ cuốn sách đầu tiên (bên trái nhất) và đọc lần lượt sang phải. Nếu không đủ thời gian để hoàn thành một cuốn sách, cuốn đó không được tính vào cảm hứng. Cảm hứng của Tí là tổng giá trị hấp dẫn ~k_i~ của các cuốn sách mà anh ấy đọc toàn bộ.

Yêu cầu: Tính giá trị cảm hứng tối đa mà Tí có thể đạt được sau ~t~ phút.

Input

• Dòng đầu tiên chứa bốn 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_1, k_2, \dots, k_n~ ~(k_i \le 10^9; k_i \le k_{i+1})~.

Hai số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Output

Ghi một số nguyên là giá trị cảm hứng tối đa mà Tí có thể đạt được sau ~t~ phút.

Scoring

Sample Input 1

3 5 2 1
2 2 4

Sample Output 1

6

Sample Input 2

2 10 3 1
3 3

Sample Output 2

6

Sample Input 3

4 10 3 2
3 4 5 6

Sample Output 3

12

Notes

• Ở ví dụ 1, Tí có thể đọc toàn bộ cuốn sách đầu tiên (~k_1 = 2~, mất ~2~ phút), đọc nội dung bìa của cuốn thứ hai (mất ~1~ phút), đọc toàn bộ cuốn thứ ba (~k_3 = 4~, mất ~2~ phút). Tổng thời gian: ~2 + 1 + 2 = 5~ phút. Tổng cảm hứng: ~2 + 4 = 6~.

• Ở ví dụ 2, Tí có thể đọc toàn bộ cả hai cuốn sách (~k_1 = 3, k_2 = 3~), mất ~3 + 3 = 6~ phút. Tổng cảm hứng: ~3 + 3 = 6~.

• Ở ví dụ 3, Tí có thể đọc toàn bộ cuốn sách đầu tiên (~k_1 = 3~, mất ~3~ phút), đọc toàn bộ cuốn thứ hai (~k_2 = 4~, mất ~3~ phút), đọc toàn bộ cuốn thứ ba (~k_3 = 5~, mất ~3~ phút). Tổng thời gian: ~3 + 3 + 3 = 9~ phút (vẫn còn dư ~1~ phút). Tổng cảm hứng: ~3 + 4 + 5 = 12~.