Vacation

Jianjia is planning a vacation in Taiwan. $n$ cities lie along one highway, numbered $0$ through $n-1$. City $i$ is adjacent only to $i-1$ and $i+1$, except the endpoints, which have one neighbor.

City $i$ has $a_i$ attractions. Jianjia has $d$ vacation days and chooses a starting city before the trip begins. Each day, exactly one of these actions is allowed.

• Move to an adjacent city.
• Visit every attraction in the current city that has not been visited yet.

Attractions in a city are never counted twice. Find the maximum number of distinct attractions Jianjia can visit.

• Line 1: $n$, starting city $start$, and vacation length $d$
• Line 2: $a_0$ through $a_{n-1}$, the attraction counts in order

Print the maximum number of attractions that can be visited.