Степан був на книжковому ярмарку і купив книги. Привабливість ~i~-ї книги — ~k_і~. Степан розташував книги на полиці відповідно до їх привабливості, тому перша книга зліва є найменш привабливою, а кожна наступна праворуч більш або однаково приваблива, ніж попередня.

Після покупок минуло чимало часу і Степан лише зараз знайшов час прочитати книжки. Загалом він витратить на читання ~t~ хвилин.

Кожну книгу він може або прочитати повністю, що займе ~a~ хвилин; або читати лише вміст з обкладинок, що займає у нього ~b~ хвилин.

Він почне з крайньої лівої книги. Закінчивши поточну книгу (повністю або лише вміст обкладинок), він переходить до наступної книги, яка є першою праворуч від книги, яку він щойно прочитав. Натхнення Степана дорівнює сумі привабливих цінностей книг, які він прочитав повністю. Яке максимальне значення натхнення Степана через ~t~ хвилин?

Примітка: якщо Степан починає читати книгу, але не закінчує її до закінчення ~t~ хвилин, ця книга не сприяє його натхненню.

Формат вхідних даних

Перший рядок містить цілі числа ~n~, ~t~, ~a~ і ~b~ (~1 ≤ n ≤ 2 · 10^5~, ~1 ≤ t ≤ 10^9~, ~1 ≤ b < a ≤ 10^9~), кількість книжок, час, який Степан витратить на читання, необхідний час для читання книги та час, необхідний для читання вмісту з обкладинок.

У другому рядку міститься ~n~ цілих чисел ~k_i~ (~1 ≤ k_i ≤ 10^9~, ~k_i ≤ k_{i+1}~), значення привабливості книг.

Формат вихідних даних

У першому й єдиному рядку виведіть максимальне натхнення Степана через ~t~ хвилин читання.

Оцінювання

• тести 1-3 - 0 балів
• тести 4-10 (~k_i=k_{i+1}~)- 20 балів
• тести 11-20 (~n \le 1000~) - 30 балів
• тести 21-28 (без додаткових обмежень) - 50 балів

Приклад вхідних даних

3 5 2 1 
2 2 4

Приклад вихідних даних

6

Приклад вхідних даних

2 10 3 1 
3 3

Приклад вихідних даних

6

Приклад вхідних даних

4 10 3 2
3 4 5 6

Приклад вихідних даних

12