Background

Translated from COCI 2023/2024 Contest #4 T2 “Knjige”.

Problem Description

Marko is at the Interliber book fair. He bought $n$ books in total, and the attractiveness of the $i$-th book is $k_i$. Marko placed all the books on a shelf in non-decreasing order of attractiveness from left to right.

Marko will spend $t$ minutes reading these books. For each book, he can either spend $a$ minutes to read it completely and gain inspiration, or spend $b$ minutes to only learn about it from the cover.

He will start reading from the leftmost book. After he finishes the current book (either completely or by looking at the cover), he starts reading the next book immediately to its right. The inspiration Marko gains is equal to the sum of the attractiveness values of the books he read completely. Determine the maximum inspiration Marko can have after $t$ minutes.

Note: If Marko starts reading a book but does not finish it before minute $t$ ends, then that book will not contribute to Marko’s inspiration.

Input Format

The first line 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 spends reading, and the time required for complete reading and for reading 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 values.

Output Format

Output one integer, the maximum inspiration value after $t$ minutes.

3 5 2 1
2 2 4

6

2 10 3 1
3 3

6

4 10 3 2
3 4 5 6

12

Hint

Sample Explanation 1

For example, Marko can achieve the maximum inspiration by reading books $1$ and $3$ completely, and reading only the cover of book $2$.

Subtasks

Translated by ChatGPT 5