Bạn Việt mới tạo ra ~n~ game cho các bạn học sinh tham gia Trại hè Hùng Vương, game thứ ~i~ có độ hấp dẫn là ~k_i~. Bạn Nam dành ~t~ đơn vị thời gian sau ngày thi để chơi các game này. Nam thử lần lượt từng game theo thứ tự từ ~1~ đến ~n~ khi chưa hết thời gian, mỗi game đều là mới với Nam, nên bạn ấy có hai lựa chọn sau:

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

Mỗi game nếu chơi hết thì sẽ nhận được độ hấp dẫn của game đó, nếu 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 ~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 sau khi chơi.

Input

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

Output

Ghi ra 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~.

Sample Input 1

3 5 2 1
2 2 4

Sample Output 1

6

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

Sample Input 2

3 5 2 1
4 3 2

Sample Output 2

7

Chơi game 1, 2 hết 4 đơn vị thời gian. Độ hấp dẫn là ~7~.

Sample Input 3

5 10 3 1
6 1 1 5 5

Sample Output 3

12

Chơi game 1, xem game 2 và chơi game 3, 4. Không làm gì với game 5.

Ràng buộc

• 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~.