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.
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.

Subtask 1 (7 points): \(k@@RISE_MATH_BLOCK_0@@i+1\) for each \(i = 1\), . . . , \(n - 1\)

Subtask 2 (27 points): \(n \le 1\,000\)

Subtask 3 (36 points): No additional constraints.

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@@RISE_MATH_BLOCK_0@@i \le 10^{9}\), k\(i \le k\)\(i+1\)), the attraction values of books.

In the first and only line print Mirko’s maximal inspiration after \(t\) minutes.

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Contest 4