Description

In Gensokyo, Cirno is an ice fairy known for being a fool.

One day, Cirno was once again playing at flash-freezing frogs, instantly freezing them with ice. But this frog was much smarter than usual and had already run to the other side of the river before Cirno arrived. So Cirno decided to go to the riverbank to chase the frog.

The small river can be viewed as a sequence of cells numbered from $0$ to $N$. Cirno can only move from a cell with a smaller index to one with a larger index. Moreover, she moves in a special way: when she is on cell $i$, she only moves to any cell in the interval $[i+L, i+R]$. Why does she move like this? Simple, because she is a fool.

Each cell has a freeze index $A_i$, and the cell with index $0$ has a freeze index of $0$. When Cirno stays on a cell, she gains that cell’s freeze index $A_i$. Cirno hopes that by the time she reaches the opposite bank, she will have gained the maximum possible freeze index, so she can teach that frog a good lesson.

However, since she is really too foolish, she asks you to help her decide how to move.

At the beginning, Cirno is on cell $0$. As long as the index of her next position is greater than $N$, she is considered to have reached the opposite bank.

Input Format

The first line contains three positive integers $N, L, R$.

The second line contains $N+1$ integers. The $i$-th number represents the freeze index $A_{i-1}$ of the cell with index $i-1$.

Output Format

Output a single integer, the maximum freeze index.

5 2 3
0 12 3 11 7 -2

11

Hint

For $60\%$ of the testdata, $N \le 10^4$.

For $100\%$ of the testdata, $N \le 2\times 10^5$, $-10^3 \le A_i \le 10^3$, $1 \le L \le R \le N$. The testdata guarantees that the final answer does not exceed $2^{31}-1$.

Translated by ChatGPT 5