Description

Jianjia is planning a trip to Taiwan for the next vacation. During this vacation, Jianjia will travel between cities and visit attractions in those cities.

There are $n$ cities in Taiwan, all located along a single highway. The cities are numbered consecutively from $0$ to $n-1$.

For city $i$ ($0 < i < n-1$), its neighboring cities are $i-1$ and $i+1$. For city $0$, the only neighboring city is $1$. For city $n-1$, the only neighboring city is $n-2$.

Each city has some attractions. Jianjia has $d$ days of vacation and wants to visit as many attractions as possible. He has already chosen the first city to visit at the start of the vacation. On each day of the vacation, Jianjia can either move to a neighboring city, or visit all attractions in the current city, but not both. Even if Jianjia stays in the same city multiple times, he will not visit the attractions of that city again. Please help Jianjia plan this vacation so that he can visit as many attractions as possible.

Input Format

• Line $1$: Three non-negative integers, where $n$ is the number of cities, $\text{start}$ is the index of the starting city, and $d$ is the number of vacation days.
• Line $2$: $n$ non-negative integers $a_0,a_1,\cdots, a_{n-1}$. For $0 \le i \le n-1$, $a_i$ is the number of attractions in city $i$.

Output Format

• One line: the maximum number of attractions that can be visited.

5 2 7
10 2 20 30 1

60

Hint

Subtasks

In all subtasks, $0 \le d \le 2n+\lfloor\frac n2\rfloor$. Also, the number of attractions in each city is a non-negative integer.

Translated by ChatGPT 5