Marko's Reading Inspiration

Marko has purchased \(n\) books with attractiveness \(k_i\) (for \(1 \le i \le n\)), and arranged them on a shelf in non-decreasing order of attractiveness. After \(t\) minutes have passed since his visit to Interliber, he finally finds time to read these books.

Starting from the leftmost book, for each book he can choose to:

• Read it fully in \(a\) minutes, which adds its attractiveness \(k_i\) to his inspiration value.
• Or quickly skim it (by its cover) in \(b\) minutes, which does not contribute to his inspiration value.

He reads the books in order. If he starts a book but fails to finish it by minute \(t\), that book does not contribute to the inspiration value.

Assuming that he may choose for each book whether to fully read or skim it, determine the maximum achievable inspiration value after exactly \(t\) minutes.

Note: The books are arranged in non-decreasing order. Thus, if he is to gain inspiration from a book, it is always optimal to fully read one of the later (and hence possibly more attractive) books rather than an earlier one.

Hint: If Marko processes \(j\) books and fully reads \(x\) of them (which must be the last \(x\) books among the \(j\) because of the sorted order), then the total time used is \(j\,b + x\,(a - b)\) minutes and the inspiration value is \(\sum_{i=j-x+1}^{j} k_i\).

inputFormat

The first line contains four integers \(n\), \(a\), \(b\), and \(t\) \( (1 \le n \le 10^5,\ 1 \le b \le a \le 10^9,\ 1 \le t \le 10^{18})\).

The second line contains \(n\) integers \(k_1, k_2, \dots, k_n\) in non-decreasing order \((1 \le k_i \le 10^9)\).

outputFormat

Output a single integer: the maximum inspiration value that Marko can achieve.

sample

5 5 2 20
1 2 3 4 5

12