Minh đã đến hội chợ sách và mua ~n~ cuốn sách. Độ hấp dẫn của cuốn sách thứ ~i~ là ~k_i~, và những cuốn sách đã được Minh sắp xếp trên kệ theo độ hấp dẫn của chúng, sao cho cuốn đầu tiên từ bên trái là ít hấp dẫn nhất, còn mỗi cuốn tiếp theo bên phải đều hấp dẫn hơn hoặc như cuốn trước.

Đã khá lâu Minh bây giờ mới có thời gian để đọc sách. Anh ấy sẽ dành tổng cộng ~t~ phút để đọc.

Đối với mỗi cuốn sách, anh ấy có thể đọc toàn bộ cuốn sách đó, việc này khiến anh ấy mất ~a~ phút; hoặc chỉ đọc nội dung trên trang bìa, việc này khiến anh ấy mất ~b~ phút.

Anh ấy sẽ bắt đầu từ cuốn sách ngoài cùng bên trái. Sau khi đọc xong cuốn sách hiện tại (toàn bộ hoặc chỉ nội dung trên bìa), anh ấy chuyển sang cuốn sách tiếp theo, là cuốn đầu tiên bên phải cuốn sách anh ấy vừa đọc. Cảm hứng của Minh tương đương với tổng độ hấp dẫn của những cuốn sách anh đã đọc toàn bộ. Giá trị lớn nhất của cảm hứng của Minh sau ~t~ phút là bao nhiêu?

Lưu ý: Nếu Minh bắt đầu đọc một cuốn sách nhưng không đọc hết trước khi hết ~t~ phút thì cuốn sách đó không góp phần tạo cảm hứng cho anh ấy.

Input

• Dòng đầu tiên chứa các số nguyên ~n~, ~t~, ~a~ và ~b~ ~(1 \leq n \leq 2 \times 10^5, 1 \leq t \leq 10^9, 1 \leq b < a \leq 10^9)~ là số sách, thời gian Minh dùng để đọc, thời gian để đọc cả quyển sách và thời gian để đọc bìa sách.
• Dòng tiếp theo gồm ~n~ số nguyên ~k_i~ ~(1 \leq k_i \leq 10^9, k_i \leq k_{i+1}~ với mọi ~1 \le i < n)~, là độ thu hút của mỗi cuốn sách.

Output

Trong một dòng, đưa ra giá trị lớn nhất của cảm hứng của Minh sau ~t~ phút.

Scoring

Subtask	Score	Constraints
1	~7~	~k_i = k_{i+1}~ với mọi ~i= 1,2,...,n-1~
2	~27~	~n \leq 10^3~
3	~36~	Không có ràng buộc gì thêm

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

Explanation

Ở ví dụ đầu tiên, Minh có thể đọc cả cuốn sách đầu tiên, đọc bìa cuốn sách thứ hai và đọc cả cuốn sách thứ ba.