Problem Description

Marko is at the Interliber book fair and has purchased a total of $n$ books. The attractiveness of the $i$-th book is $k_i$. Marko has arranged all the books on a shelf in non-decreasing order of their attractiveness from left to right.

A long time has passed since the Interliber, but Marko only recently found time to read these books. He spent a total of $t$ minutes reading.

For each book, he can spend $a$ minutes to read it completely, or spend $b$ minutes to understand the content through the cover.

He will start reading from the leftmost book and, after finishing the current book (either by reading it completely or understanding it through the cover), he will move on to the next book to the right. Marko's inspiration value is equal to the sum of the attractiveness of the books he reads completely. What is the maximum inspiration value Marko can achieve after $t$ minutes?

Note: If Marko starts reading a book but does not finish it before the $t$-th minute, this book will not contribute to Marko's inspiration value.

Input Format

The first line of input contains four integers $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$), representing the number of books, the time Marko has for reading, the time required to read a book completely, and the time required to understand a book through the cover, respectively.

The second line contains $n$ integers $k_i$ ($1 \le k_i \le 10^9$, $k_i \le k_{i+1}$), representing the attractiveness of the books.

Output Format

Output a single integer, which is the maximum inspiration value Marko can achieve after $t$ minutes.

Sample Input and Output

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/Hints

Sample Explanation 1

For example, Marko can achieve the maximum inspiration value by reading the $1$st and $3$rd books completely and understanding the $2$nd book through the cover.

Subtasks

见题面 Input 部分

见题面 Output 部分