Books

Interview

Time limit1sMemory limit1024 MB

Summary

Pick which books to read in full (a minutes each) and which by cover only (b minutes each) within t minutes to maximize the total attraction of fully read books.

Level: Medium4 of 10
Topics: Greedy, Prefix sum, Array
Solved: No attempts yet

Problem

Marko was at the Interliber book fair, and he bought $n$ books. The attraction of the $i$ -th book is $k_i$ . Marko arranged the books on the shelf according to their attraction values, so the first book from the left is the least attractive, and every next one to the right is at least as attractive as the previous one.

It has been quite some time since Interliber, but Marko has only now found time to read the books. He will spend a total of $t$ minutes reading.

For each book, he can either read it in its entirety, which takes $a$ minutes, or read only the content from the covers, which takes $b$ minutes.

He starts from the leftmost book. After finishing the current book (either entirely or just the content from the covers), he moves on to the next book, which is the first one to the right of the book he just read. Marko's inspiration is the sum of the attraction values of the books he has read in their entirety. What is the maximum value of Marko's inspiration after $t$ minutes?

Note: If Marko starts reading a book but does not finish it before the end of $t$ minutes, that book does not contribute to his inspiration.

Input

The first line contains integers $n$ , $t$ , $a$ , and $b$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le t \le 10^9$ , $1 \le b < a \le 10^9$ ), the number of books, the time Marko will spend reading, the time required to read a book in its entirety, and the time required to read only the content from the covers.

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

Output

Print Marko's maximal inspiration after $t$ minutes on the first and only line.

Examples3

Example 1
Input
```
3 5 2 1
2 2 4
```
Expected output
```
6
```
Example 2
Input
```
2 10 3 1
3 3
```
Expected output
```
6
```
Example 3
Input
```
4 10 3 2
3 4 5 6
```
Expected output
```
12
```