Bạn được cho \(n\) cuốn sách với các mức độ hấp dẫn \(a_1, a_2, \dots, a_n\), trong đó \(a_i \le a_{i+1}\) với mọi \(1 \le i < n\) (dãy không giảm). Bạn sẽ đọc lần lượt các cuốn sách từ \(1\) tới \(n\), mỗi cuốn sách bạn có thể đọc toàn bộ trong \(a\) phút, hoặc chỉ đọc lướt qua trong \(b\) phút, nhưng không được phép bỏ qua cuốn sách nào, và phải đọc theo đúng thứ tự.

Bạn chỉ có tối đa \(t\) phút để đọc sách, hãy lập ra chiến lược đọc sao cho tổng mức độ hấp dẫn của những cuốn sách mà bạn đã đọc toàn bộ là lớn nhất.

Input

• Dòng đầu tiên chứa bốn số nguyên \(n, t, a, b\) (\(1 \le n \le 2 \cdot 10^5, 1 \le t \le 10^9, 1 \le b < a \le 10^9\)).
• Dòng tiếp theo chứa \(n\) số nguyên, số nguyên thứ \(i\) là giá trị của \(a_i\) (\(1 \le a_i \le 10^9, a_i \le a_{i+1}\)).

Output

• Một dòng duy nhất là tổng mức độ hấp dẫn lớn nhất.

Example

3 5 2 1
2 2 4

6

Scoring

• Subtask 1 (27% số điểm): \(a_i = a_{i+1}\) với mọi \(i = 1, 2, \dots, n-1\).
• Subtask 2 (37% số điểm): \(n \le 1000\).
• Subtask 3 (36% số điểm): Không có ràng buộc gì thêm.