knjige (COCI CONTEST_#4)
Time limit: 1 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: greedy, prefix sum, array

# Task Knjige

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 more or equally attractive than the previous one.

![](_page_0_Picture_5.jpeg)

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 him $a$ minutes; or read only the content from the covers, which takes him $b$ minutes.

He will start 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 equal to 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 fails to 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, time required for reading a book and the time required to read 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 books.

## Output

In the first and only line print Mirko's maximal *inspiration* after $t$ minutes.

## Scoring

| Subtask | Points | Constraints |
|---------|--------|-------------|
| 1       | 7      | $k_i = k_{i+1}$ for each $i = 1, \dots, n - 1$ |
| 2       | 27     | $n \le 1000$ |
| 3       | 36     | No additional constraints. |

## Examples

| input | input | input |
|---|---|---|
| 3 5 2 1<br>2 2 4 | 2 10 3 1<br>3 3 | 4 10 3 2<br>3 4 5 6 |
| output | output | output |
| 6 | 6 | 12 |

### Clarification of the first example:

For example, Marko can read the first book in its entirety, read only the content from the covers of the second book, and read the third book in its entirety, thus achieving the maximum possible inspiration.

Starter code:

Grader code:

Setup script:

Evaluation script: